"pow" (power) function

[Russ]

I have a couple of questions for the number crunchers out there:

Does "pow(x,2)" simply square x, or does it first compute logarithms
(as would be necessary if the exponent were not an integer)?

Does "x**0.5" use the same algorithm as "sqrt(x)", or does it use some
other (perhaps less efficient) algorithm based on logarithms?

Thanks,
Russ

[Schüle Daniel]

Russ wrote:

I have a couple of questions for the number crunchers out there:

Does "pow(x,2)" simply square x, or does it first compute logarithms
(as would be necessary if the exponent were not an integer)?

Does "x**0.5" use the same algorithm as "sqrt(x)", or does it use some
other (perhaps less efficient) algorithm based on logarithms?

you can try and timeit

111**111 107362012888474 225801214565046 695501959850723 994224804804775 911175625076195 783347022491226 170093634621466 103743092986967 777786330067310 159463303558666 910091026017785 587295539622142 057315437069730 229375357546494 103400699864397 711L timeit.Timer("p ow(111,111)").t imeit() 40.888447046279 907 timeit.Timer("1 11**111").timei t() 39.732122898101 807 timeit.Timer("1 11**0.5").timei t() 2.0990891456604 004 timeit.Timer("p ow(111,0.5)").t imeit() 4.1776390075683 594 timeit.Timer("1 11**0.3").timei t() 2.3824679851531 982 timeit.Timer("p ow(111,0.3)").t imeit()

4.2945041656494 141

interesting result
seems that ** computates faster

[sam]

I not shure which algorithm,but I am assumeing that all Python does,is
to call the underlying C pow() function.

Sam

[Paul Rubin]

Schüle Daniel <uv**@rz.uni-karlsruhe.de> writes:

>>> timeit.Timer("1 11**0.3").timei t() 2.3824679851531 982 >>> timeit.Timer("p ow(111,0.3)").t imeit()

4.2945041656494 141

interesting result
seems that ** computates faster

Maybe "111**0.3" parses faster than pow(111,0.3), if timeit uses eval.
Also, pow() may incur more subroutine call overhead--better check
the bytecode for both versions.

[Ben Cartwright]

Russ wrote:

I have a couple of questions for the number crunchers out there:

Sure, but the answers depend on the underlying Python implementation.
And if we're talking CPython, they also depend on the underlying C
implementation of libm (i.e., math.h).

Does "pow(x,2)" simply square x, or does it first compute logarithms
(as would be necessary if the exponent were not an integer)?

The former, using binary exponentiation (quite fast), assuming x is an
int or long.

If x is a float, Python coerces the 2 to 2.0, and CPython's float_pow()
function is called. This function calls libm's pow(), which in turn
uses logarithms.

Does "x**0.5" use the same algorithm as "sqrt(x)", or does it use some
other (perhaps less efficient) algorithm based on logarithms?

The latter, and that algorithm is libm's pow(). Except for a few
special cases that Python handles, all floating point exponentation is
left to libm. Checking to see if the exponent is 0.5 is not one of
those special cases.

If you're curious, download the Python source, open up
Objects/floatobject.c, and check out float_pow(). The binary
exponentation algorithms are in Objects/intobject:int_p ow() and
Objects/longobject:long _pow().

The 0.5 special check (and any other special case optimizations) could,
in theory, be performed in the platform's libm. I'm not familiar
enough with any libm implementations to comment on whether this is ever
done, or if it's even worth doing... though I suspect that the 0.5 case
is not.

Hope that helps,
--Ben

[Russ]

Ben Cartwright wrote:

Russ wrote:

Does "pow(x,2)" simply square x, or does it first compute logarithms
(as would be necessary if the exponent were not an integer)?

The former, using binary exponentiation (quite fast), assuming x is an
int or long.

If x is a float, Python coerces the 2 to 2.0, and CPython's float_pow()
function is called. This function calls libm's pow(), which in turn
uses logarithms.

I just did a little time test (which I should have done *before* my
original post!), and 2.0**2 seems to be about twice as fast as
pow(2.0,2). That seems consistent with your claim above.

I'm a bit surprised that pow() would use logarithms even if the
exponent is an integer. I suppose that just checking for an integer
exponent could blow away the gain that would be achieved by avoiding
logarithms. On the other hand, I would think that using logarithms
could introduce a tiny error (e.g., pow(2.0,2) = 3.9999999996 <- made
up result) that wouldn't occur with multiplication.

Does "x**0.5" use the same algorithm as "sqrt(x)", or does it use some
other (perhaps less efficient) algorithm based on logarithms?

The latter, and that algorithm is libm's pow(). Except for a few
special cases that Python handles, all floating point exponentation is
left to libm. Checking to see if the exponent is 0.5 is not one of
those special cases.

I just did another little time test comparing 2.0**0.5 with sqrt(2.0).
Surprisingly, 2.0**0.5 seems to take around a third less time.

None of these differences are really significant unless one is doing
super-heavy-duty number crunching, of course, but I was just curious.
Thanks for the information.

[Ben Cartwright]

Russ wrote:

Ben Cartwright wrote:

Russ wrote:

Does "pow(x,2)" simply square x, or does it first compute logarithms
(as would be necessary if the exponent were not an integer)?

The former, using binary exponentiation (quite fast), assuming x is an
int or long.

If x is a float, Python coerces the 2 to 2.0, and CPython's float_pow()
function is called. This function calls libm's pow(), which in turn
uses logarithms.

I just did a little time test (which I should have done *before* my
original post!), and 2.0**2 seems to be about twice as fast as
pow(2.0,2). That seems consistent with your claim above.

Actually, the fact that x**y is faster than pow(x, y) has nothing do to
with the int vs. float issue. It's actually due to do the way Python
parses operators versus builtin functions. Paul Rubin hit the nail on
the head when he suggested you check the bytecode:

import dis
dis.dis(lambda x, y: x**y) 1 0 LOAD_FAST 0 (x)
3 LOAD_FAST 1 (y)
6 BINARY_POWER
7 RETURN_VALUE dis.dis(lambda x, y: pow(x,y)) 1 0 LOAD_GLOBAL 0 (pow)
3 LOAD_FAST 0 (x)
6 LOAD_FAST 1 (y)
9 CALL_FUNCTION 2
12 RETURN_VALUE

LOAD_GLOBAL + CALL_FUNCTION is more expensive than LOAD_FAST,
especially when you're doing it a million times (which, coincidentally,
timeit does).

Anyway, if you want to see the int vs. float issue in action, try this:
from timeit import Timer
Timer('2**2').t imeit() 0.1268101158232 1844 Timer('2.0**2.0 ').timeit() 0.3333601174343 8121 Timer('2.0**2') .timeit() 0.3668183555611 2219 Timer('2**2.0') .timeit() 0.3794981837060 0497

As you can see, the int version is much faster than the float version.
The last two cases, which also use the float version, have an
additional performance hit due to type coercion. The relative speed
differences are similar when using pow():
Timer('pow(2, 2)').timeit() 0.3300096886915 7532 Timer('pow(2.0, 2.0)').timeit() 0.5035636218470 9269 Timer('pow(2.0, 2)').timeit() 0.5511293818585 7274 Timer('pow(2, 2.0)').timeit() 0.5519881960581 1877

I'm a bit surprised that pow() would use logarithms even if the
exponent is an integer. I suppose that just checking for an integer
exponent could blow away the gain that would be achieved by avoiding
logarithms. On the other hand, I would think that using logarithms
could introduce a tiny error (e.g., pow(2.0,2) = 3.9999999996 <- made
up result) that wouldn't occur with multiplication.

These are good questions to ask an expert in floating point arithmetic.
Which I'm not. :-)

Does "x**0.5" use the same algorithm as "sqrt(x)", or does it use some
other (perhaps less efficient) algorithm based on logarithms?

The latter, and that algorithm is libm's pow(). Except for a few
special cases that Python handles, all floating point exponentation is
left to libm. Checking to see if the exponent is 0.5 is not one of
those special cases.

I just did another little time test comparing 2.0**0.5 with sqrt(2.0).
Surprisingly, 2.0**0.5 seems to take around a third less time.

Again, this is because of the operator vs. function lookup issue.
pow(2.0, 0.5) vs. sqrt(2.0) is a better comparison:

from timeit import Timer
Timer('pow(2.0, 0.5)').timeit() 0.5170143710281 5362 Timer('sqrt(2.0 )', 'from math import sqrt').timeit()

0.4664909672223 9847

None of these differences are really significant unless one is doing
super-heavy-duty number crunching, of course, but I was just curious.
Thanks for the information.

Welcome. :-)

--Ben

[Mike Ressler]

On Wed, 2006-03-15 at 18:46 -0800, Ben Cartwright wrote:

Anyway, if you want to see the int vs. float issue in action, try this:

>>> from timeit import Timer
>>> Timer('2**2').t imeit() 0.1268101158232 1844 >>> Timer('2.0**2.0 ').timeit() 0.3333601174343 8121 >>> Timer('2.0**2') .timeit() 0.3668183555611 2219 >>> Timer('2**2.0') .timeit() 0.3794981837060 0497

As you can see, the int version is much faster than the float version.

I have a counterexample. In the original timeit example, 111**111 was
used. When I run that

timeit.Timer("p ow(111,111)").t imeit() 10.968398094177 246 timeit.Timer("1 11**111").timei t() 10.040078878402 71 timeit.Timer("1 11.**111.").tim eit()

0.3657629489898 6816

The pow and ** on integers take 10 seconds, but the float ** takes only
0.36 seconds. (The pow with floats takes ~ 0.7 seconds). Clearly
typecasting to floats is coming in here somewhere. (Python 2.4.1 on
Linux FC4.)

Mike

[Ben Cartwright]

Mike Ressler wrote:

timeit.Timer("p ow(111,111)").t imeit() 10.968398094177 246 timeit.Timer("1 11**111").timei t() 10.040078878402 71 timeit.Timer("1 11.**111.").tim eit() 0.3657629489898 6816

The pow and ** on integers take 10 seconds, but the float ** takes only
0.36 seconds. (The pow with floats takes ~ 0.7 seconds). Clearly
typecasting to floats is coming in here somewhere. (Python 2.4.1 on
Linux FC4.)

No, there is not floating point math going on when the operands to **
are both int or long. If there were, the following two commands would
have identical output:

111**111 107362012888474 225801214565046 695501959850723 994224804804775 911
175625076195783 347022491226170 093634621466103 743092986967777 786
330067310159463 303558666910091 026017785587295 539622142057315 437
069730229375357 546494103400699 864397711L int(111.0**111. 0) 107362012888474 224720018046104 893130890742038 145054486592605 938
348914231670972 887594279283213 585412743799339 280552157756096 410
839752020853099 983680499334815 422669184408961 411319810030383 904
886446681757296 875373689157536 249282560L

The first result is accurate. Work it out by hand if you don't believe
me. ;-) The second suffers from inaccuracies due to floating point's
limited precision.

Of course, getting exact results with huge numbers isn't cheap,
computationally . Because there's no type in C to represent arbitrarily
huge numbers, Python implements its own, called "long". There's a fair
amount of memory allocation, bit shifting, and other monkey business
going on behind the scenes in longobject.c.

Whenever possible, Python uses C's built-in signed long int type (known
simply as "int" on the Python side, and implemented in intobject.c).
On my platform, C's signed long int is 32 bits, so values range from
-2147483648 to 2147483647. I.e., -(2**31) to (2**31)-1.

As long as your exponentiation result is in this range, Python uses
int_pow(). When it overflows, long_pow() takes over. Both functions
use the binary exponentiation algorithm, but long_pow() is naturally
slower:
from timeit import Timer
Timer('2**28'). timeit() 0.2457203204382 9495 Timer('2**29'). timeit() 0.2551164279193 4719 Timer('2**30'). timeit() 0.2774678297917 0348 Timer('2**31'). timeit() # overflow: 2**31 > 2147483647 2.8205724462504 804 Timer('2**32'). timeit() 2.2251812151589 547 Timer('2**33'). timeit() 2.4067177773399 635

Floating point is a whole 'nother ball game:
Timer('2.0**30. 0').timeit() 0.3326630196384 0306 Timer('2.0**31. 0').timeit() # no threshold here!

0.3343744676963 0697

--Ben

[Terry Reedy]

"Mike Ressler" <mi**********@a lum.mit.edu> wrote in message
news:11******** **************@ dhcp-78-140-229.jpl.nasa.go v...

I have a counterexample. In the original timeit example, 111**111 was
used. When I run that

timeit.Timer("p ow(111,111)").t imeit() 10.968398094177 246 timeit.Timer("1 11**111").timei t() 10.040078878402 71 timeit.Timer("1 11.**111.").tim eit()

0.3657629489898 6816

The pow and ** on integers take 10 seconds, but the float ** takes only
0.36 seconds. (The pow with floats takes ~ 0.7 seconds). Clearly
typecasting to floats is coming in here somewhere. (Python 2.4.1 on
Linux FC4.)

For floats, f**g == exp(log(f**g)) == exp(g*log(f)) (with maybe further
algebraic manipulation, depending on the implementation) . The time for
this should only be mildly dependent on the magnitudes of f and g.

The time for i**j, on the other hand, grows at least as fast as log(j). So
I should expect comparisons to depend on magnitudes, as you discovered.

Terry Jan Reedy