473,699 Members | 2,226 Online

# "pow" (power) function

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

Mar 15 '06 #1
11 4433
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

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

Sam

Mar 16 '06 #3
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.
Mar 16 '06 #4
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.

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

Mar 16 '06 #5
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.

Mar 16 '06 #6
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)
6 BINARY_POWER
7 RETURN_VALUE dis.dis(lambda x, y: pow(x,y)) 1 0 LOAD_GLOBAL 0 (pow)
9 CALL_FUNCTION 2
12 RETURN_VALUE

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

Mar 16 '06 #7
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
Mar 16 '06 #8
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

Mar 17 '06 #9

"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

Mar 17 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 9 2206 by: Aaron Gallimore | last post by: Hi, Pretty simple one I think...Is there a "power of" or squared function in C++. This is what i'm trying to achieve. (array-array)*2 this doesnt work with minus numbers so i need a square or power function. also.. Is there a "sum of" function. Ultimately i'm trying to do a euclidean 6 2718 by: M Welinder | last post by: The title more or less says it all: in C99, is the value of INT_MIN % -1 well defined (when performed as signed integers) under the assumption of two-complement representation. Note, that this is not the usual negative-values-and-% question -- the problem here is that the corresponding signed division, INT_MIN / -1, overflows. Thus I don't see what use a%b = a-(a/b)*b can be here. 13 2085 by: Dave win | last post by: howdy.... plz take a look at the following codes, and tell me the reason. 1 #define swap(a,b) a=a^b;b=b^a;a=a^b 2 3 int main(void){ 4 register int a=4; 5 register int b=5; 6 swap(a,b); 7 15 28816 by: Bjorn Jensen | last post by: Hi! An beginner question: Pleas help me with this (-: Error (the arrow points on the s in sqrt) ===== tal.java:6: cannot find symbol symbol : method sqrt(int) location: class tal System.out.println(i + ": " + sqrt(4)); 1 2886 by: Curten | last post by: Hi, When I run a program I have made, i get this error message sometimes: "Application error:The instruction at '...' referenced memory at '...'. Memory could not be "read"..." Are there any common mistakes that cause this problem? Before i get the message above i get this in the command window: "pow: OVERFLOW error". I suppose these error messages are connected, but how? What causes pow: OVERFLOW error? 7 5213 by: Camellia | last post by: hi all, I wrote a "table of powers" program and made the 5th power the highest, but when I tried to run the program I found a problem. Here's the output: Integer Square power 3rd power 4th power 5th ------- ------ --------- --------- --------- 1 1 1 1 1 22 6236 by: Alexandre Proulx | last post by: I am trying to find 2 at the power of 601, but my calculator doesn't have a large enough screen, so I decided to make a program for my computer to do this, but when I get to a high number the computer only prints : 1.#INF00. Is there any way to do it? My code is the fallowing: #include #include #include using namespace std; float a; float x; float y; 0 1592 by: tarlino | last post by: Hi! I'm play with the sound generation (c++ and directX). Now I would like to manage same filter on my sample. But now I must to convert my audio buffer "BYTE" (from DirectX) to an arry of "short" and viceversa. I found this source: ************************************************************** double dPowI = ceil( log10( (double)iLen / ( ((double)wBitsPerSample / 8 ) + wChannels - 1 ) ) / log10( 2.0 ) ); int iNearTwoPower = (int)pow(... 2 1628 by: Netwatcher | last post by: can somebody explain me where to put "{ }" and ";" symbols on a script? i did search the web but didn't find any explanation written in a way i can understand. example of a code that i tried and doesn't work