Question

a) you can see a program for using bisection search to find the square root of x:

x = 25

epsilon = 0.01

low = 0.0

high = max(1.0, x)

guess = (low + high) / 2

numberofguesses = 1

while abs(guess ** 2 - x) > epsilon :

print('low =', low, 'high = ', high, 'guess = ', guess)

if guess** 2 > x : # the guess is too high, so move high down to guess

high = guess

else : # the guess is too low, so move low up to guess

low = guess

print('number of guesses:', numberofguesses)

print(guess, 'is close enough to the square root of ', x)

Try out the program, and fix any typos (mine or yours) so that it works. Think about why it starts high with max(1, x) in place of simply high = x. Change the program so that the value of x is read from the user. Ask the user for a positive number. If the user gives a negative number, then ask again, repeatedly until a positive number is given.

b) Modify the bisection search program shown above, so that it finds the cube root of a number. The number can be negative or positive.

Answer 1

The corrected program is as follows:

while True:
    inp = float(input("Calculate square root of? "))
    if inp<=0:
        print('Please enter a positive number')
        continue
    else:
        break
x = inp
epsilon = 0.01
low = 0.0
high = max(1.0, x)
guess = (low + high) / 2
numberofguesses = 1
while abs(guess ** 2 - x) > epsilon :
    print('low =', low, 'high = ', high, 'guess = ', guess)
    numberofguesses+= 1
    if guess** 2 > x : # the guess is too high, so move high down to guess
        high = guess
    else : # the guess is too low, so move low up to guess
        low = guess
    guess = (low + high) / 2
print('number of guesses:', numberofguesses)
print(guess, 'is close enough to the square root of ', x)

Reason we use high=max(1.0,x)

When x is between 0 and 1, the square root of x is greater than x itself. Therefore we can't just set high to x, because it needs to start out higher than the desired answer.

Bisection method to find cube root:

n = float(input())
if (n>0 and n<1) or (n>-1 and n<0):
    low=abs(n)
    high=1
else:
    if n>=1 or n<=-1:
        low=0
        high=abs(n)
eps = 0.0000001
numberOfGuesses = 0
mid = (low + high) / 2.0
while abs((mid**3)-abs(n)) > eps :
        if mid**3 < abs(n):
                low = mid
        else:
                high = mid
        mid = (low + high)/2.0
        numberOfGuesses = numberOfGuesses + 1
guess = mid
if n>0:
    print ("Cube Root of ",n ," : ", guess, " in ",numberOfGuesses," guesses.")
else:
    print ("Cube Root of ",n ," : ", -1*guess, " in ",numberOfGuesses," guesses.")