This note considers computation of the integer logarithm, i.e., the logarithm truncated down to the nearest integer. If the base of the logarithm is two, the integer logarithm is easily obtained by counting the number of bits right to the most significant set bit of the number. We thus focus on the case with the base greater than two.

Let and be natural numbers such that . We treat them number as constants in our analysis unless otherwise stated. Also, write In this note, we investigate computation of the integer logarithm with base : by using where is a suitably chosen natural number, . This approach is motivated by the simple identity: We attempt to approximate by and by . Chapter 11 of (Henry S. Warren 2013) studies this very approach for the case with . This note provides a natural extension to arbitrary bases along with some detailed mathematical analysis.

The sequence is bounded and nondecreasing, because and It actually converges to , since Thus, we can approximate by arbitrarily well by using a sufficiently large. Nevertheless, and can still disagree even with a very large . For example, consider the case with . Then for any , where the strong inequality holds because . For this reason, we only aim to formulate that delivers either or for each .

Fix . Because it holds that

Define Then it also holds that where is defined by It follows that Combining () and (), we obtain that

Note that and are integers. If , it is guaranteed that or that . Because is nondecreasing in , we have that for each , It follows by () that The sequence converges to , which is less than one, provided that . It follows that converges to one uniformly in as . Thus, there always exists such that for every .

Once we choose a suitable , we need to determine which is equal to, or . To this end, we can use the fact that if and only if . To avoid the relatively expensive computation of , we can use a table lookup scheme. That is, we make in our code an array that maps to for each in in an array in the code. This allows us to quickly obtain the value of . When , we are sure that , because .

Here is a sample implementation for the case with and written in C.

unsigned int uint32__log10(unsigned int x) {
  static const unsigned int threshold[] = {
    10, 100, 1000, 10000, 100000, 1000000,
    10000000, 100000000, 1000000000
  };
  unsigned int floor_log2 = 31 - __builtin_clz(x);
  unsigned int y = (floor_log2 * 9) >> 5;
  return y + (x >= threshold[y]);
}

When we need to calculate the logarithm with various bases, we could not employ the table lookup scheme. We can, however, still use an efficient algorithm for computing such as the exponentiation by squaring.

References