Re: "pow" (power) function

Mike Ressler wrote:
> >>> timeit.Timer("pow(111,111)").timeit()
> 10.968398094177246
> >>> timeit.Timer("111**111").timeit()
> 10.04007887840271
> >>> timeit.Timer("111.**111.").timeit()
> 0.36576294898986816
>
> 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
  107362012888474225801214565046695501959850723994224804804775911
  175625076195783347022491226170093634621466103743092986967777786
  330067310159463303558666910091026017785587295539622142057315437
  069730229375357546494103400699864397711L
>>> int(111.0**111.0)
  107362012888474224720018046104893130890742038145054486592605938
  348914231670972887594279283213585412743799339280552157756096410
  839752020853099983680499334815422669184408961411319810030383904
  886446681757296875373689157536249282560L

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.24572032043829495
>>> Timer('2**29').timeit()
  0.25511642791934719
>>> Timer('2**30').timeit()
  0.27746782979170348
>>> Timer('2**31').timeit() # overflow: 2**31 > 2147483647
  2.8205724462504804
>>> Timer('2**32').timeit()
  2.2251812151589547
>>> Timer('2**33').timeit()
  2.4067177773399635

Floating point is a whole 'nother ball game:

>>> Timer('2.0**30.0').timeit()
  0.33266301963840306
>>> Timer('2.0**31.0').timeit() # no threshold here!
  0.33437446769630697

--Ben
Received on Sun Apr 30 12:02:54 2006