Why isn't there Math.Pow that takes an int as the exponent?

Question

I read that the Math.Pow implementation is pretty complicated to be able to handle fractional powers. Why isn't there a version that takes an int for the exponent to make a faster version when you don't need fractional powers?

Check out this link on SO: http://stackoverflow.com/questions/383587/how-do-you-do-integer-exponentiation-in-c — paulsm4, Aug 02 '11 at 21:49
Thanks but would it be fast as a MS' version? Because they use an external call for their Pow method. — Joan Venge, Aug 02 '11 at 21:53
Thanks Henk, I assumed they wanted to write it in C++ to make it faster. What other reasons would there be to do that for this case? — Joan Venge, Aug 02 '11 at 21:57
I was talking to a graphics programmer here and he said the implementation to handle fractional powers is much more complicated than just multiplying values, so I assumed I get hit by the same performance penalty even when my exponent is not fractional. — Joan Venge, Aug 02 '11 at 22:00
http://stackoverflow.com/questions/2398442/why-isnt-int-powint-base-int-exponent-in-the-standard-c-libraries — phuclv, Apr 22 '15 at 05:07

score 6 · Accepted Answer · edited Nov 02 '20 at 21:04

6

Because you'd just need to convert it back into a float to multiply it against the logarithm of the base.

n^m = e^{m × ln n}

edited Nov 02 '20 at 21:04

Zombo

1
62
391
407

answered Aug 02 '11 at 21:47

Ignacio Vazquez-Abrams

776,304
153
1,341
1,358

@BlueRaja OP Clearly states only int for exponent. – David Heffernan Aug 02 '11 at 22:10
Unless you implement the integer exponentiation using integer arithmetic... which will probably be faster than running those exp and ln's. – Roman Starkov Feb 13 '14 at 18:28

score 0 · Answer 2 · 2011-08-02T22:14:27.887

0

For a compiler it is only worthwhile to optimize by converting to a series of multiplies, if the exponent is constant. In which case you can write x*x or x*x*x yourself.

Edit: So if you want to avoid your math is done by the Math.Pow implementation (which uses exponent functions), just don't call it. If Math.Pow would be added for integers, the compiler would have figure out from how it is called if it should emit code for multiplication (if n is constant and small) or the default using exponent functions. That is non-trivial work for a compiler, and there would be no gain in terms of performance.

edited Aug 02 '11 at 22:14

answered Aug 02 '11 at 21:52

So you think it would optimize if I do Math.Pow (3, 5)? The call is external so I can't see the code. – Joan Venge Aug 02 '11 at 21:55
1

This utterly misses the point. `Math.Pow` doesn't do a series of multiplications. And even if it did, the library code behind it would use intermediate values even if the exponent was not known at compile time. – David Heffernan Aug 02 '11 at 21:57

score 0 · Answer 3 · edited May 23 '17 at 11:53

0

I don't think that fast math functions was their first priority when they programmed them (see Why is Math.DivRem so inefficient). They could use a expotentiation by square that would be faster, at least for small exponents.

However because floating point is subject to rounding providing 2 different inplementations could mean different results, e.g. for pow(5.9,7) than for pow(5.9,7.0), which may be undesirable in some cases.

edited May 23 '17 at 11:53

Community

1
1

answered Aug 02 '11 at 23:05

ggf31416

3,582
1
25
26

What level of accuracy is guaranteed for the "pow" function? Guaranteeing precision within 0.5625ulp when raising to an integer power is a little tricky, but guaranteeing it when using exp(ln(base)\*pow) is even harder. Too C sufficiently botched extended-precision support that such types aren't generally available, since they'd make it much easier to yield a result accurate to `double` precision. – supercat Sep 16 '15 at 18:27

Chris Gregg · Answer 4 · 2011-08-02T22:23:07.337

-4

Well, you could write your own (in C):

int intPow(int a,int b){
  int answer = a;
  int i;
  for(i=0;i<b-1;i++)
    answer *= a;
  return answer;
}

edited Aug 02 '11 at 22:23

answered Aug 02 '11 at 21:50

Chris Gregg

2,376
16
30

1

Only there are much smarter (faster) ways to do it. – H H Aug 02 '11 at 21:54
1

Note that this runs in O(N). A good pow implementation could run in O(logN) – luiscubal Aug 02 '11 at 21:55
1

This is very inefficient. And it doesn't compile. I think that OP imagined that `a` was a floating point value. – David Heffernan Aug 02 '11 at 21:55
@luiscubal I think pow should be a lot better than `O(log N)`!! – David Heffernan Aug 02 '11 at 21:55
@all haters (joking) -- I edited it to compile in a non c99 environment. I hear you that it isn't efficient. :) – Chris Gregg Aug 02 '11 at 22:04
1

@David Heffernan - Just curious, could you provide an example(link if the explanation is too long) of pow algorithm better than O(logN)? A quick look at Wikipedia doesn't seem to suggest anything better than that... – luiscubal Aug 02 '11 at 22:04
1

@David: It *can* be O(1), but the tradeoff is that it consumes a *LOT* of space. – Ignacio Vazquez-Abrams Aug 02 '11 at 22:05
@luiscubal You can use the expression given by Ignacio Vazquez-Abrams – David Heffernan Aug 02 '11 at 22:06
@Chris Are you really still wanting to use default types for `a` and `b`? – David Heffernan Aug 02 '11 at 22:12
1

@David Heffernan - But now the problem is twofold: implementing efficient e^x AND efficient ln(x)... – luiscubal Aug 02 '11 at 22:16
@luiscubal Use the hardware for those, make it somebody else's problem – David Heffernan Aug 02 '11 at 22:18
1

@David Heffernan -- ah, good point! This is what I get for working in Python/C/Java/Obj C/Scheme...too many different ways to define parameters. I'll put in the ints... – Chris Gregg Aug 02 '11 at 22:22
4

Knuth volume 2, section 4.6.3 gives a tremendous exposition on the evaluation of powers – David Heffernan Aug 02 '11 at 22:27

Why isn't there Math.Pow that takes an int as the exponent?

4 Answers4

nm = em × ln n

n^m = e^{m × ln n}