Search code examples
c++clogarithmmath.hcmath

C/C++ fastest cmath log operation

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.

Solution

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