AVLZ -4 years ago 83

Python Question

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

`for`

`range()`

As an example, I have the function

f(x) = x^{2}- 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`

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()`

Plus, if my interval changed to [-2, 1], I would need 53 tries.

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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/2^{52} of your value. After 52 steps, your initial range of size 5 has become about size 5/2^{52}. That's about 1/2^{52} 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/2^{52} is still a bit larger than 1/2^{52}. 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 2^{20}.

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

Latest added