0

when I calculate multiple powers

 123 ** 123 ** 123

The computation takes indefinite time to execute, but when I run

In [5]: 0.123 ** 123 ** 123                                                                                       
Out[5]: 0.0

it returns immediately.

How does the floating-point version run so much faster?

Charles Duffy
  • 280,126
  • 43
  • 390
  • 441
AbstProcDo
  • 19,953
  • 19
  • 81
  • 138
  • 9
    Floating point precision is not infinite, and anything times zero is zero. So as soon as the number gets too low for the computer to store and rounds to zero, the rest of the computation is unnecessary and can be short-circuited. – Charles Duffy Nov 03 '18 at 23:06
  • Also note that the result of that integer computation would be unimaginably vast: there's only 10 ** 80 ish atoms in the universe. – Jared Smith Nov 03 '18 at 23:23
  • You might be interested in looking at the source for the implementation of the `pow()` function for [long](https://hg.python.org/cpython/file/c7163a7f7cd2/Objects/longobject.c#l3599) and [float](https://hg.python.org/cpython/file/6a60359556f9/Objects/floatobject.c#l807) values. There are many cases to short circuit out in the float implementation then use the system `pow()` function. Longs will loop to perform the calculation. – Jeff Mercado Nov 03 '18 at 23:24
  • My (initial) hypothesis is that `0.123**a` with `a` a large integer is evaluated quickly as `exp(log(0.123)*a)` using floating point arithmetic. However `123**a` is evaluated exactly with slow bigint calculations. Note that `123.0**123**123` gives a quick overflow (which may support my hypothesis). – Erwin Kalvelagen Nov 03 '18 at 23:57

1 Answers1

2

As Charles Duffy mentioned in the comments, floating point math does not have infinite precision (see also the question Is floating point math broken?).

In 0.123 ** 123 ** 123 the intermediary result becomes equal to zero after just a few steps and subsequent multiplications don't need to be performed.

Naive demonstration of a temporary value becoming equal to zero:

>>> v = 0.123
>>> i = 0
>>> while True:
...:    v = v*v
...:    i += 1
...:    if v == 0:
...:        break
...:    
>>> i
>>> 9

In the real world, nothing close to this happens. CPython calls the patform pow here in line 912. The platform math functions tend to be optimized to the extreme and take any shortcut they can, with trickery and deception aquired over generations of numerical mathematics.

timgeb
  • 76,762
  • 20
  • 123
  • 145
  • I would be very disappointed if the Python runtime would do anything like this. I doubt there is any looping like this involved. – Erwin Kalvelagen Nov 04 '18 at 00:45
  • @ErwinKalvelagen of course Python does not parse exponentiation into a (Python) loop. It's a demonstration of what happens in principle - the number gets too small to be different from zero. You can see that the system `pow` is called here in line [912](https://hg.python.org/cpython/file/6a60359556f9/Objects/floatobject.c#l912). – timgeb Nov 04 '18 at 08:44