28

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

Chris Andrews
  • 1,881
  • 3
  • 21
  • 31
uda27
  • 281
  • 1
  • 3
  • 7
  • 1
    Complexity is a measure of growth when a function (e.g., sorting) is applied to a larger number of inputs. Given that `pow` always has exactly the same number of inputs, complexity (at least as the term is normally used) simply doesn't apply. You can apply complexity measures based on the size of a single input, but that doesn't generally apply to something like `pow` in the standard library that takes only a fixed-size input. It could/would apply to computing powers when dealing with arbitrary precision numbers. – Jerry Coffin Nov 16 '12 at 15:33
  • 2
    @JerryCoffin: Won't number of bits in the exponent count? It isn't entirely unreasonable to consider complexity of `f(x)` in terms of `x` and to assume that it is unbounded (the number of inputs is also bounded by practical limits). – Dietmar Kühl Nov 16 '12 at 16:10
  • 1
    @DietmarKühl: There is sometimes measurable variation between values withing a type like double, but at least when I've measured, the relationship wasn't to something as simple as the magnitudes of the numbers. IOW, yes there may be an `O(f(x))`, but it's not entirely clear what `x` is, not to mention what `f(x)` is. I say "may be", because it's also unclear that the concept of `x` approaching infinity applies in this case. It's ultimately more about precision than the magnitudes of the numbers though. – Jerry Coffin Nov 16 '12 at 17:22
  • Not a dup, but related: [https://stackoverflow.com/q/4638473/4594973](https://stackoverflow.com/q/4638473/4594973). – code_dredd Aug 09 '17 at 15:02

3 Answers3

20

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

Community
  • 1
  • 1
Magnus Hoff
  • 21,529
  • 9
  • 63
  • 82
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)

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
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

Community
  • 1
  • 1
Chris Andrews
  • 1,881
  • 3
  • 21
  • 31