C/C++ fastest cmath log operation

Question

I'm trying to calculate log_ab (and get a floating point back, not an integer). I was planning to do this as log(b)/log(a). Mathematically speaking, I can use any of the cmath log functions (base 2, e, or 10) to do this calculation; however, I will be running this calculation a lot during my program, so I was wondering if one of them is significantly faster than the others (or better yet, if there is a faster, but still simple, way to do this). If it matters, both a and b are integers.

Answer 1

First, precalculate 1.0/log(a) and multiply each log(b) by that expression instead.

Edit: I originally said that the natural logarithm (base e) would be fastest, but others state that base 2 is supported directly by the processor and would be fastest. I have no reason to doubt it.

Edit 2: I originally assumed that a was a constant, but in re-reading the question that is never stated. If so then there would be no benefit to precalculating. If it is however, you can maintain readability with an appropriate choice of variable names:

const double base_a = 1.0 / log(a);
for (int b = 0; b < bazillions; ++b)
    double result = log(b) * base_a;

Strangely enough Microsoft doesn't supply a base 2 log function, which explains why I was unfamiliar with it. Also the x86 instruction for calculating logs includes a multiplication automatically, and the constants required for the different bases are also available via an optimized instruction, so I'd expect the 3 different log functions to have identical timing (even base 2 would have to multiply by 1).

Answer 2

Since b and a are integers, you can use all the glory of bit twiddling to find their logs to the base 2. Here are some:

• Find the log base 2 of an integer with the MSB N set in O(N) operations (the obvious way)
• Find the integer log base 2 of an integer with an 64-bit IEEE float
• Find the log base 2 of an integer with a lookup table
• Find the log base 2 of an N-bit integer in O(lg(N)) operations
• Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup

I'll leave it to you to choose the best "fast-log" function for your needs.

Answer 3

On the platforms for which I have data, log2 is very slightly faster than the others, in line with my expectations. Note however, that the difference is extremely slight (only a couple percent). This is really not worth worrying about.

Write an implementation that is clear. Then measure the performance.