Why does this While loop terminate?

Question

x=1.0
i=1
while(1.0+x>1.0):
 x=x/2
 i=i+1
print i

Follow up question, why is the value of i=54?

My thinking was that the loop would not end as the value of (1.0+x) will always stay greater than 1.0. But when running the code, that's not the case.

• JBernardo: because float precision

Answer 1

Due to the inaccuracy of floating point, there will always come a time when the value of x is so small that Python can't store its value, and it essentially becomes 0. It takes 54 iterations (53, actually) to get to that stage, which is why i is 54.

For example,

>>> 1e-1000
0.0

• JBernardo: Actually a to a float number (double precision) undergo to zero, it takes more steps than 53 2.**-1074 vs 2.**-1075. The key here is to add 1

Answer 2

Why 54? -- Actually it is 53, because it was before you increment it

>>> 2.**-54
5.551115123125783e-17
>>> 2.**-53
1.1102230246251565e-16
>>> 2.**-52
2.220446049250313e-16
>>> sys.float_info.epsilon
2.220446049250313e-16

if you add something so small to 1, it will be still 1.

Answer 3

When dealing with floats or floating point numbers, you will encounter the notorious Floating Point Epsilon:

In your case, this takes 54 iterations to get below that threshold (since the default floating point type in Python is single precision, and the floating point epsilon for single precision is:

def machineEpsilon(func=float):
 machine_epsilon = func(1)
 while func(1)+func(machine_epsilon) != func(1):
 machine_epsilon_last = machine_epsilon
 machine_epsilon = func(machine_epsilon) / func(2)
 return machine_epsilon_last

Hence:

In [2]: machineEpsilon(float)
Out[2]: 2.2204460492503131e-16

Where does the 53 iterations come from?

From this line in your code:

x=x/2

Which assigns the current value of x to x/2 meaning that on the 53th iteration, it became:

1.11022302463e-16

Which is less than the floating point epsilon.

Answer 4

As has been pointed out - it's because of the accuracy of floats. If you wanted to overcome this "limitation" you can use Python's fractions module, eg:

from fractions import Fraction as F
x = F(1, 1)
i=1
while(F(1, 1)+x>1.0):
 print i, x
 x = F(1, x.denominator * 2)
 i=i+1
print i

(NB: This will continue until interrupted)