Time complexity of c++ math library pow() function?

Question

I wanted to know what is the worst case time-complexity of the pow() function that's built in c++?

Answer 1

You don't mention what system/architecture you're on, so we are left guessing.

However, if you're not looking for specifics and just want to browse the code of a freely available implementation See http://www.netlib.org/fdlibm/, specifically http://www.netlib.org/fdlibm/w_pow.c

See this question's answer for more background: https://stackoverflow.com/a/2285277/25882

Answer 2

Here is one implementation, take a look. To be sure, it is a rather complex piece of code, with some 19 special cases. The time complexity does not appear to be dependent on the values passed in.

Here is a short description of the method used to compute pow(x,y):

Method:  Let `x =  2 * (1+f)`

• Compute and return log2(x) in two pieces: log2(x) = w1 + w2, where w1 has 53-24 = 29 bit trailing zeros.

• Perform y*log2(x) = n+y' by simulating muti-precision arithmetic, where |y'|<=0.5.

• Return x**y = 2**n*exp(y'*log2)

Answer 3

That depends on the underlying architecture. On the most common desktop architecture, x86, this is a constant time operation.

See this question for more details on how it could be implemented on x86: How to: pow(real, real) in x86