"pow" (power) function

[Ben Cartwright]

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