22

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.

13
  • 6
    In the words of Donald Knuth: "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil"
    – You
    Commented Jul 11, 2011 at 20:09
  • 18
    @You "mindless mantras are anethema to productive thought" Commented Jul 11, 2011 at 20:15
  • 20
    @You - I've always felt that quote is over utilized. Certainly there are a circumstances where you can spend a lot of effort, reduce the readability of the code, and end up not noticing the difference. There are plenty of other cases where you can spend very little effort, not affect the readability at all, and make a huge improvement. Knowing which case is which comes with practice, unless you stop considering the prospect altogether. Commented Jul 11, 2011 at 20:18
  • 4
    @You: multiply, add, and subtract are all much faster than log, exp, and trig. Sqrt and divide are in between. (Intel Skylake has a very fast FP divide unit, but it's still a factor of 8 worse throughput, and a factor of ~3 worse latency than FP mul. sqrt is only slightly slower). It's a lot faster to check a geometric mean as (x^2+y^2) < maxdistance^2 instead of sqrt(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.) Commented Jan 31, 2016 at 4:16
  • 11
    @You That is a partial and indeed selective quotation. I suggest you read the rest of it, particularly the final sentence. The full quotation is as follows: 'Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.'
    – user207421
    Commented Jan 31, 2016 at 23:21

5 Answers 5

15

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).

8
  • +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
  • 1
    That'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
  • 1
    I'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
  • 2
    The 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.
    – zwol
    Commented Jan 30, 2016 at 14:19
11

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.

3
  • 4
    Cool 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 support lzcnt, which is defined for 0. AVX512CD will introduce VPLZCNTD, which does it on every element in a vector of integers. Commented Jan 31, 2016 at 4:29
  • 1
    Also, 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
4

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.

1

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.

3
  • 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 measure log2( ) 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
0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.