 AVLZ -4 years ago 83
Python Question

# Understanding the number of iterations to find a solution using the Bisection method

I was asked to find the root of an equation using the Bisection method and only

`for`
loops with Python 3. This thread shows how to use the method, but not with the explanation for the number in
`range()`
.

As an example, I have the function

f(x) = x2 - 2*x - 3

and I want to find its negative root, starting with the interval [-4, 1].

I managed to write the function with a
`for`
loop, but I don't understand which range I should use, or how to come up with it.

Here is my code, that solves the problem:

``````...
a = -4
b = 1
c = (a + b)/2

for i in range(1000):
if f(c) == 0:
break
if f(a) * f(c) < 0:
b = c
elif f(a) * f(c) > 0:
a = c
c = (a + b) / 2

return c, f(c), i
``````

c = -1 (found the negative root), f(c) = 0 confirming that the program works, and i = 52 which indicates that after 52 "tries" of bisection, it found the right answer.

I put a very large number in
`range()`
to make sure I found the root, but why does it need only 52 iterations?

Plus, if my interval changed to [-2, 1], I would need 53 tries. Why is that so? Stefan Pochmann

If you `print([a, b])` in the loop, you can see the range evolve:

``````[-4, 1]
[-1.5, 1]
[-1.5, -0.25]
[-1.5, -0.875]
[-1.1875, -0.875]
[-1.03125, -0.875]
...
...
...
[-1.0000000000000284, -0.9999999999999929]
[-1.0000000000000107, -0.9999999999999929]
[-1.0000000000000018, -0.9999999999999929]
[-1.0000000000000018, -0.9999999999999973]
[-1.0000000000000018, -0.9999999999999996]
[-1.0000000000000007, -0.9999999999999996]
``````

The calculated mean of -1.0000000000000007 and -0.9999999999999996 is exactly -1. Why? Because you've reached the limit of the what floats can represent. Here are the exact values involved:

``````>>> '%.60f' % -1.0000000000000007
'-1.000000000000000666133814775093924254179000854492187500000000'

>>> '%.60f' % -0.9999999999999996
'-0.999999999999999555910790149937383830547332763671875000000000'

>>> '%.60f' % (-1.0000000000000007 + -0.9999999999999996)
'-2.000000000000000000000000000000000000000000000000000000000000'

>>> '%.60f' % ((-1.0000000000000007 + -0.9999999999999996) / 2)
'-1.000000000000000000000000000000000000000000000000000000000000'
``````

Floats store 52 bits of fraction, meaning 52 bits after the leading 1-bit. Meaning you lose what's smaller than about 1/252 of your value. After 52 steps, your initial range of size 5 has become about size 5/252. That's about 1/252 of your value -1. So around there, you reach a pretty good chance to stumble upon exactly -1 because of the imprecision.

It could take two or maybe three steps more, because 5/252 is still a bit larger than 1/252. You got lucky there. With your other initial range `[-2, 1]` you just got less lucky. There your range shrinks until `[-1.0000000000000002, -0.9999999999999999]` before you reach -1.

If you start with `[-4000000, 1]` instead, then you'll need 72 steps. It's 20 steps more because the initial range is a million times larger, which is about 220.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download