I recently started reading Complex Digital Circuits by Jean-Pierre Deschamps and ran into a mathematical curiosity that has stalled me on making progress.

For context, the author is describing the underlying theory needed to design a circuit that can compute the base-2 logarithm of a real number with an accuracy of $p$ fractional bits.

The input, $x$, is an n-bit normalized fractional number:

$x = 1.x_{-1}x_{-2}...x_{-n}$

As such, $x$ will be bounded within the interval $[1,2)$.

With $x$ properly bounded, the base-2 logarithm can then be computed:

$y = log_2(x)$

As $x$ is restricted to the interval $[1,2)$, $y$, with an accuracy of $p$ fractional bits, will then be restricted to the interval $[0,1)$. In other words:

$y = 0.y_{-1}y_{-2}...y_{-p}$

Solving the base-2 logarithm equation for $x$:

$y = log_2(x)$

$x = 2^{y}$

$x = 2^{0.y_{-1}y_{-2}...y_{-p}...}$

However, the author next squares both sides of the above equation:

$x^2 = (2^{0.y_{-1}y_{-2}...y_{-p}...})^2$

And then states the following:

$x^2 = 2^{y_{-1}y_{-2}...y_{-p}...}$

I don't understand how he arrived at this conclusion and why the decimal point goes away. Also, I don't understand why the ellipsis, ..., appears after the base-2 logarithm equation is solved for $x$. Could someone please explain this to me?

For a bit more context, after this step, the author reasons the following:

  • if $x^2 \geq 2: y_{-1} = 1, x' = \frac{x^2}{2} = 2^{0.y_{-2}...y_{-p}...}$
  • if $x^2 < 2: y_{-1} = 0, x' = x^2 = 2^{0.y_{-2}...y_{-p}...}$

Unless there is a typo in the text, it should say $$x^2 = 2^{y_{-1}\color{red}{.}y_{-2}...y_{-p}...}$$ This is because $$(2^{0.y_{-1}y_{-2}...y_{-p}...})^2= 2^{2\cdot0.y_{-1}y_{-2}...y_{-p}...}= 2^{y_{-1}.y_{-2}...y_{-p}...}\tag{1}$$

The first equal sign in $(1)$ is just $(a^b)^2=a^{2b}$ and the second because we're using binary. As for the ellipsis, he jsut means that we can't solve for the logarithm exactly. It will have infinitely many bits, in general.

| cite | improve this answer | |
  • $\begingroup$ It appears that there is a typo in the text. I believe that the expression that you provided is correct. I'll remember that notational trick to denote infinite precision. Thank you! $\endgroup$ – CatsInSpace May 17 '19 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.