What is the complexity of the log function?

Question

What is the complexity of the log base 10 function?

Solution 1

This really depends on the domain of what values you want to compute a logarithm of.

For IEEE doubles, many processors can take logarithms in a single assembly instruction; x86 has the FYL2X and FYL2XP1 instructions, for example. Although typically instructions like these will only take the logarithm in some fixed base, they can be used to take logarithms in arbitrary bases by using the fact that

log_a b = log_c b / log_c a

by simply taking two logarithms and finding their quotient.

For general integers (of arbitrary precision), you can use repeated squaring combined with a binary search to take logarithms using only O(log log n) arithmetic operations (each time you square a number you double the exponent, which means you can only square the number log log n times before you've exceeded its value and can do a binary search). Using some cute tricks with Fibonacci numbers, you can do this in only O(log n) space. If you're computing the binary logarithm, there are some cute tricks you can use with bit shifts to compute the value in less time (though the asymptotic complexity is the same).

For arbitrary real numbers the logic is harder. You can use Newton's method or the Taylor series to compute logarithms to within a certain precision, though I confess that I'm not familiar with the methods for doing this. However, you rarely actually need to do this because most real numbers are IEEE doubles and there are better algorithms (or even hardware instructions) in that case.

Hope this helps!

Solution 2

To do log(n) in O(1) ( where n is an integer )

int log(long long x)
{
    return 64 - __builtin_clzl(x) - 1;
}

for __builtin_clzl(x) refer here

Comments

[harold]

For integers there's often also an instruction (or a short sequence, to do CTZ(x & (x - 1)) or wordsize - LZC(x)) - but AFAIK that doesn't help with the time complexity at all (just actual speed)

[Nick Johnson]

@templatetypedef Which you can multiply by a constant factor to get logarithms in any other base, as you just demonstrated. :)

[templatetypedef]

This will compute the binary logarithm of the number, assuming the number is an integer. But if you wanted to compute log base 10, I think you'd need to use a different strategy.

[Rustam A.]

@NickJohnson Yes, and thought it is fast indeed, we should note, that multiplication operation itself has higher that logarithmic complexity: en.wikipedia.org/wiki/…

[Abhay Gupta]

This code actually returns log on the base of 2.

[taurus05]

@iamakshatjain, you can update the code so that it works with any base value specified by the user.