What is the complexity of the log function?

Question

What is the complexity of the log base 10 function?

Answer 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!

Answer 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