I'm trying to calculate logab (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.
5 Answers
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).
-
+1 Nice observation. Although the other answer has a point since these operations are so fast anyway optimizing it is a little much. Commented Jul 11, 2011 at 20:11
-
1That's true but optimization by newer compilers almost removes the need to do some of these things which is kind of sad. Although most people still write out optimizations like these. Commented Jul 11, 2011 at 20:14
-
1I'm pretty sure that the logarithm to base 2 is the fastes, since its the only one to have its own assembler instruction (at least in 8087 instruction set). Commented Jul 11, 2011 at 20:15
-
3@Mark: exactly correct. Unless a flag like
fast-math
is set, the compiler cannot replace division with a reciprocal multiply (not only because it changes rounding, but also because it can cause spurious overflows and NaNs). And yes, divide is much slower than multiplication on most current processors. Commented Jul 11, 2011 at 20:56 -
2The log instructions are unlikely to be used by modern compilers, as they are inaccurate (relative to what you can do in software) and only available in the deprecated x87 instruction set.– zwolCommented Jan 30, 2016 at 14:19
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.
-
4Cool link. I wonder if any of those methods are faster than the straight-forward ones on modern processors? Commented Jul 11, 2011 at 20:24
-
1@MarkRansom: They'll all be much slower than using a hardware instruction to count leading zeros, which all modern architectures have, because the looping methods will branch-mispredict with different inputs. The hw insn is very cheap. x86's original
bsr
is clunky (undefined if input is 0), but does give the log2 result directly, instead of 32-log2(a). Only quite recent CPUs supportlzcnt
, which is defined for0
. AVX512CD will introduceVPLZCNTD
, which does it on every element in a vector of integers. Commented Jan 31, 2016 at 4:29 -
1Also, I thought the OP was looking for a solution that didn't round / truncate intermediate results to integer. Sure the starting values are integer, but
integer_log2(uint32_t)
only has a range of 0..32, so the fractional part makes a big difference. There's a huge range of numbers between 2^30 and 2^31, but they all have the same ilog2. Commented Jan 31, 2016 at 4:33
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.
In the 8087 instruction set, there is only an instruction for the logarithm to base 2, so I would guess this one to be the fastest.
Of course this kind of question depends largely on your processor/architecture, so I would suggest to make a simple test and time it.
-
On modern x86 processors, it turns out that good software log implementations are faster than the hardware log instruction, so the base used in that instruction is really of no consequence to the question. Commented Jul 11, 2011 at 20:15
-
2@Stephen Canon, if you have a link to some timing results this would be a great place to trot it out. Commented Jul 11, 2011 at 20:26
-
7@Mark Ransom, the Intel Optimization Manual lists
fyl2x
as having a throughput of 1 result every 85 cycles, and a latency of between 140 and 190 cycles. By contrast, using the system math library on OSX on my MacBook Pro, I measurelog2( )
as having a latency of ~72 cycles and throughput of 1 result every 46 cycles. So the software implementation is approximately twice as fast here. Commented Jul 11, 2011 at 21:12
The answer is:
- it depends
- profile it
You don't even mention your CPU type, the variable type, the compiler flags, the data layout. If you need to do lot's of these in parallel, I'm sure there will be a SIMD option. Your compiler will optimize that as long as you use alignment and clear simple loops (or valarray if you like archaic approaches).
Chances are, the intel compiler has specific tricks for intel processors in this area.
If you really wanted you could use CUDA and leverage GPU.
I suppose, if you are unfortunate enough to lack these instruction sets you could go down at the bit fiddling level and write an algorithm that does a nice approximation. In this case, I can bet more than one apple-pie that 2-log is going to be faster than any other base-log
(x^2+y^2) < maxdistance^2
instead ofsqrt(x^2+y^2) < maxdistance
, esp. if you're doing this check repeatedly (like in a Mandelbrot inner loop), or with integers. (x86 scalar integer division is slower than SIMD FP division.)