Why does this Python program loop indefinitely?

Question

x = 25
epsilon = 0.01
step = 0.1
guess = 0.0

while guess <= x:
    if abs(guess**2 -x) >= epsilon:
        guess += step

if abs(guess**2 - x) >= epsilon:
    print('failed')
else:
    print('succeeded: ' + str(guess))

I am given this Python program which attempts to calculate the square root of a number x. For some reason, this program loops indefinitely and I'm not sure why.

There are only finitely many values of guess, because, after guess>x (i.e. when guess>=25.1,, the while loop then stops). The while command in the middle of the program is the only thing that loops, so what is happening?

So what happens when guess = 5.0? Your if statement won't match but guess <= x still true. — Martijn Pieters
– Martijn Pieters, Commented Nov 6, 2016 at 21:51
Please have a look at Methods of computing square roots to implement a square root computation algorithm. A naive search is not performant at all. — Michael Hilbert
– Michael Hilbert, Commented Nov 6, 2016 at 22:02

Martijn Pieters · Accepted Answer · 2016-11-06 22:15:10Z

You only increment guess when the condition abs(guess**2 -x) >= epsilon is true. That condition is false when guess = 5.0. At that point guess never changes anymore but guess <= x is still true and you enter an infinite loop:

>>> x = 25
>>> epsilon = 0.01
>>> guess = 5.0
>>> abs(guess**2 - x)
0.0
>>> abs(guess**2 - x) >= epsilon
False

Starting at guess = 0.0 and incrementing by 0.1 means that your loop executes 50 times before reaching that point, after which guess never changes again.

In reality, guess is not 5.0 exactly because adding an approximation of 0.1 (which can't be represented exactly using binary fractions), gives you a value a small amount lower:

>>> guess = 0.0
>>> for _ in range(50):
...     guess += 0.1
...
>>> guess
4.999999999999998

but that difference is still smaller than epsilon.

You probably want to break the while loop when you have reached within epsilon distance of the target:

while guess <= x:
    if abs(guess**2 -x) < epsilon:
        break
    guess += step

trincot · Accepted Answer · 2016-11-06 21:59:30Z

0

Even if you change the while condition to < instead of <=, it will still loop indefinitely, because of floating point inaccuracy.

Although you add steps of 0.1, the guess value will not become exactly 5, but 4.999999999999998, at which point the loop will continue to run without entering in the if block.

This is at least what I see happening here

edited Nov 6, 2016 at 21:59

answered Nov 6, 2016 at 21:55

trincot

357k38 gold badges282 silver badges339 bronze badges

4 Comments

Martijn Pieters Over a year ago

The stepsize is 0.1, not 0.01. 50 * 0.1 is still 5.0 exactly ((50 * 0.1).is_integer() is true).

trincot Over a year ago

Maybe it depends on the processor, because I see it happening here.

Martijn Pieters Over a year ago

No, I can reproduce it when I step away from multiplication and use addition 50 times.

trincot Over a year ago

Indeed, I just came to the same conclusion :)

Collectives™ on Stack Overflow

Why does this Python program loop indefinitely?

2 Answers 2

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related