Pearls of Computer Arithmetic: The Binary Logarithm

Abstract

Do you remember this conversion of decimal numbers into their binary representations at the beginning of your Computer Science class? This procedure of consecutive divisions or multiplications producing unwieldy long sequences of ones and zeros even for rather small numbers is nothing you must fall in love with. (This is the very reason why we are using hexadecimal.) But did you know that you can tweak this process to determine the binary representation of a number that you do not really know yet? This short post will show you how you can easily compute the binary representation of the binary logarithm (i.e. base 2) through a procedure closely resembling the base conversion.

Base Conversion

We typically write down numbers using positional number systems. Each digit in a number has a constant individual value and a weight determined by its position relative to the fractional point. These weights are powers of the base of the number system. In our everyday lives, we are most accustomed to using base 10, i.e. decimal numbers. Digital computers use base 2, i.e. binary numbers. Higher coherent radixes that are powers of two are common for internal representation, storage or just for the sake of simplification by eliminating rather long binary representations.

Regularly, number representations must undergo a base conversion so as to become compatible with the digital ecosystem or with our own expectations. The conversion process may exploit the fact that we expect the number to be a sum of this form:

For the sake of concreteness assume you wanted to compute the binary representation of some number Z. Taking its integer part and dividing it by B=2 will leave you with z_0 as the remainder and a quotient that represents the value within the first-level parentheses. Decomposing this value in the same way yields z_1 and the next level of parentheses. Continue this iteration until your quotient turns zero. Then, you have computed all digits from the fractional point leftwards.

Computing the fractional digits works very similar but uses multiplication. So, multiply the fractional part of Z by B=2. This will make the number of contained halves the integer part of the result and yield z_-1. Again, repeat this step with the new fractional part to determine z_-2, the quarter digit, and continue for more. This process will not terminate automatically for most fractions. So, quit when you have reached an appropriate precision.

Computing the Binary Logarithm

So what about the binary logarithm? Assume you wanted to compute the binary logarithm of X as Y=ld X. At first, you would determine the position of the most significant (leftmost) one digit in the binary representation of X. Move the binary point just behind this digit. Now you have normalized your input argument X and have computed the integer part of your result Y:

Having normalized your input to X', you have obtained a value in the range [1,2) whose binary logarithm obviously is in the range [0,1). Computing this logarithm will deliver the still missing fractional part Y' of the sought result.

Do you remember how the fractional digits of the binary representation where computed in the base conversion? Consecutive doubling of the fractional part and stripping off its integer part. Well, we cannot do this directly with Y' simply because we do not have it. But we do have its exponential X'=2^Y'. Doubling Y' corresponds to squaring its exponential. Can we now infer the integer part of the doubled Y' just having its corresponding exponential? Yes, we can! If the squared exponential is still smaller than 2, the next fractional result digit is zero. Otherwise, it is a number in the range [2,4), which corresponds to a logarithm in [1,2) and makes the next result digit one. Stripping this integer part from Y' could be modeled as a conditional subtraction of zero or one. Also this operation easily maps two X' asking for a conditional division by two - or a bit shift if you like. Bringing everything together yields this neat algorithm for the computation of the binary logarithm:

Input: 1 <= x < 2

y := 0;
for i in 1 .. m do
  x := x*x;  # Squaring x doubles its logarithm.
  if x >= 2 then
    # The following two operations would
    #   ideally be implemented as bit shifts.
    y := y + 2**(-i); # Append a one digit to the result.
    x := x / 2;       # Subtract one from the logarithm to
                      #  strip off its integer part.
  fi
done

Ouput: y = ld x

Do not forget to add the integer part obtained by the input normalization. After that, you are done and have computed the binary logarithm of X up to the m-th fractional binary digit. And recall: if you have one logarithm, you've got them all.