CODEWITHSUNDEEP
python
19181918
19181918

Reputation: 37

Square root calculation using bisection

I have the following code which should find the square root using bisection, but for some reason it won't. When I want to find the square root of 9 I get 4.5. 

y = float(input('Enter the number that you want to find the square root of: '))
z = y
x = 0
ans = 0

while abs(ans**2 - abs(y)) > 0.0001 and ans <= x:
    ans = (x + y) / 2.0

    if ans**2 < z:
        x = ans
    else:
        y = ans


print 'The square root of', z, 'is', ans

Upvotes: 0

Views: 5866

Answers (3)

PM 2Ring
PM 2Ring

Reputation: 55499

Keiwan has explained what was wrong with your script, but here's a slightly different way to organize the logic. I've changed some of the variable names to make the code more readable, and I've put it into a function to make it easier to use. The code below works on Python 2 or Python 3, although there are minor differences in how the floating-point numbers are printed.

from __future__ import print_function, division

def sqrt_bisect(z, tol=1E-12):
    ''' Find the square root of `z` by bisection, with tolerance `tol` '''
    lo, hi = 0, z
    while True:
        mid = (lo + hi) / 2.0
        delta = mid * mid - z
        if abs(delta) < tol:
            break

        if delta > 0:
            #Too high
            hi = mid
        else:
            #Too low
            lo = mid

    return mid

for z in (1, 9, 16, 200):
    x = sqrt_bisect(z)
    print(z, x, x*x)

output

1 1.0 0.999999999999
9 3.0 9.0
16 4.0 16.0
200 14.1421356237 200.0

(That output was created using Python 2).

Just for fun, here's a more compact variation of that function.

Instead of using separate lo and hi variables to store the bounds of the interval we're bisecting, this version uses a list named bounds. The statement bounds[delta > 0] = mid works because False is numerically equal to zero, and True is equal to one. So when delta is positive bounds[delta > 0] is equivalent to bounds[1]. It's a clever trick, but it does make the code a little trickier to read if you're not used to that construction.

def sqrt_bisect(z, tol=1E-12):
    ''' Find the square root of `z` by bisection, with tolerance `tol` '''
    bounds = [0, z]
    while True:
        mid = sum(bounds) / 2.0
        delta = mid * mid - z
        if abs(delta) < tol:
            break
        bounds[delta > 0] = mid

    return mid

Upvotes: 0

Ani Menon
Ani Menon

Reputation: 28257

Square root of a number x: sqrt=x**(1.0/2)

Alternative :

import math
math.sqrt(x)

Using bisection algorithm:

y = float(input('Enter the number that you want to find the square root of: '))
num = y
x = 0
ans = 0

while abs(ans**2 - abs(num)) > 0.0001 and ans <= y:
    ans = (x + y) / 2.0
    if ans**2 < num:
        x = ans
    else:
        y = ans

print 'The square root of', num, 'is', ans

Upvotes: 0

Keiwan
Keiwan

Reputation: 8301

You need to check if ans <= y, because y is your right border in this case. Also you need to compare ans**2 to the absolute value of z, not y, because you are changing y inside the loop:

while abs(ans**2 - abs(z)) > 0.00001 and ans <= y:   
    ans = (x + y) / 2.0

    if ans**2 < z:
        x = ans
    else:
        y = ans

Upvotes: 2

Related Questions