4

I've got the following Python script:

x = 300000000.0
while (x < x + x):
    x = x + x
    print "exec: " + str(x)
print "terminated" + str(x)

This seemingly infinite loop, terminates pretty quickly if x is a floating point number. But if i change x to 300000000 instead, it gets into an infinite loop (runs longer than a minute in my test).

I think this is to do with the fact that it's exhausting the precision of a floating point number that can be represented in memory. Can someone provide a more detailed explanation why this is?

Joe Tam
  • 564
  • 5
  • 16

3 Answers3

11
  • When you initialize x to 300000000, integer math is used throughout the program.
  • When you initialize x to 300000000.0, floating-point math is used instead.

In Python, integers can grow arbitrarily large. (More accurately, they're limited by the available memory.) This means that the integer version of your program takes a very long time to terminate.

The largest float is about 1.8e308. It takes about 1000 iterations of the floating-point version of the loop to exceed that value, at which point x gets set to positive infinity, and the program terminates.

NPE
  • 486,780
  • 108
  • 951
  • 1,012
  • voted as correct answer since this actually why it explains it doesn't terminate for the integer case, where other answers just explained the obvious that it terminates when x = inf if x is a float – Joe Tam Feb 09 '17 at 18:56
6

This is because a floating-point overflow occurs. In that case, as per IEEE754, x will adopt the value positive infinity, which is by definition not less than anything else:

>>> x = float("inf")
>>> x
inf
>>> x + x
inf
>>> x < x + x
False
Niklas B.
  • 92,950
  • 18
  • 194
  • 224
4

x doubles after each step. A finite number x is never equal to 2 * x. But once you exceed the maximum exponent of your floating point type, the doubling turns x to +infinity. And +infinity = 2*+infinity. So the loop terminates at that point.

CodesInChaos
  • 106,488
  • 23
  • 218
  • 262