Computing Logarithm Bit-by-Bit: Reversing an Exponentiation Algorithm

[This page is auto-generated; please prefer to read the article’s PDF Form.]

Reversing an Exponentiation Algorithm

Since f = log ₂x is equivalent to 2^f = x, we can say that ﬁnding logarithm is reverse of doing exponentiation. In an earlier article titled Some Algorithms for Exponentiation [2], we discussed Binary (Left-to-Right) algorithm for computing a^b where a and b are positive integers.

Can we create a similar algorithm to compute 2^f where f is not an integer, but a real number with 0 ≤ f < 1. That is, can we iteratively process the bits of f = (0.b₁b₂b₃…)₂ to build-up 2^f, as we did in the Binary (Left-to-Right) algorithm to build-up a^b? Below we see how this can be done; note that it processes bits of f in right-to-left order:

float binary_exp(float f)
{
  float x, y;
  int m = 8, p, bit = 0;

  /* say f = (0.b{-1} b{-2} b{-3} ... b{-m}) in binary (m bits) */

  p = -(m+1);
  y = 0;
  x = 1;

  /* loop-invariants:
       Y: y consists of suffix bits of f from position p to -m;
          thus y = 0.(bp b[p-1] ... b{-m}) (implies 0 <= y < 1).
       X: x = 2^y (implies 1 <= x < 2) */

  while(p < -1)
  {
    p = p + 1;

    /* bit = {read the next bit of f, from position p} */

    /* maintain Y */
    y = (y + bit)/2;

    /* maintain X */
    if(bit)
      x = x * 2;

    x = sqrtf(x); /* sqrtf() computes the square-root */
  }
  /* p = -1 */
  /* y = f */
  /* x = 2^f */

  return x;
}

It need not be an eﬃcient way to compute 2^f. But we wish to see if this exponentiation algorithm, where f is given and 2^f is computed, can help us create an algorithm to compute f if 2^f is given. Can we reverse the execution of the loop in this method so that we can start with x = 2^f (x known, f unknown) and generate the bits of f one by one?

Suppose we know x at the end of an iteration, call it x_e. Note that each iteration maintains 1 ≤ x < 2. The value of x at the start of this iteration must be x_s = x_e² or x_e²∕2 depending upon the bit processed. But x_s too must follow 1 ≤ x_s < 2. So, x_s = x_e² iﬀ 1 ≤ x_e² < 2. And x_s = x_e²∕2 iﬀ 1 ≤ x_e²∕2 < 2, i.e. 2 ≤ x_e² < 4. So, x_s and hence the bit can be deduced based on whether x_e² ≥ 2 or not.

Thus we have found a way to reach at the starting state of an iteration from its end; to reverse the execution of an iteration. Starting with the ﬁnal value of x(= 2^f), we can now execute all iterations in the reverse order, with each iteration itself reversed as above. Below we see the loop eﬀecting such reversal:

  p = -1;
  /* variable y is not shown */
  /* x = 2^f is given, 1 <= x < 2 */

  while(p > -(m+1))
  {
    x = x * x;

    if(x >= 2)
    {
      bit = 1;
      x = x/2;
    }
    else
      bit = 0;

    /* ’bit’ is the bit of f at position p */

    p = p - 1;
  }
  /* p = -(m+1) */

Thus we could ﬁnd a method to generate the bits of f one by one. Notice that this algorithm is same as the Bit-by-Bit algorithm we discussed earlier, but we have arrived at it by reversing an exponentiation algorithm.

References

[1] D. R. Morrison. A Method for Computing Certain Inverse Functions.
Math. Comp. (AMS), Vol 10 (1956), 202–208. https://www.ams.org/
journals/mcom/1956-10-056/S0025-5718-1956-0083821-9.

[2] Nitin Verma. Some Algorithms for Exponentiation.
https://mathsanew.com/articles/
algorithms_for_exponentiation.pdf (2021).