Three ‘guess and check’ methods to search square root and cube root.

  1. Exhaustive Enumeration
  2. Bisection Search
  3. Newton-Raphson (for root finding)

Sample Code

Exhaustive Enumeration

Cube Root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
cube = -64
epsilon = 0.01
guess = 0.0
increment = 0.0001
num_guesses = 0
while abs(guess**3 - cube) >= epsilon and abs(guess) <= abs(cube):
    if cube < 0:
        guess -= increment
    else:
        guess += increment
    num_guesses += 1
print('num_guesses = ', num_guesses)
if abs(guess**3 - cube) >= epsilon:
    print('Failed on cube root of', cube)
else:
    print('Cube root of ' + str(cube) + ' is ' + str(guess))

Square Root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
x = 25
epsilon = 0.01
numGuesses = 0
low = 1.0
high = x
ans = (low + high) / 2.0
while abs(ans**2 - x) >= epsilon:
    print('low = ' + str(low) + ' high = ' + str(high) + ' ans = ' + str(ans))
    numGuesses += 1
    if ans**2 < x:
        low = ans
    else:
        high = ans
    ans = (low + high) / 2.0
print('numGuesses: ' + str(numGuesses))
print(str(ans) + ' is close to square root of ' + str(x))

Cube Root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
cube = -27
epsilon = 0.01
numGuesses = 0
if cube >= 0:
    low = 0
    high = cube
else:
    low = cube
    high = 0
guess = (low + high) / 2.0
while abs(guess**3 - cube) >= epsilon:
    print('low = ' + str(low) + ' high = ' + str(high) + ' guess = ' + str(guess))
    if guess**3 < cube:
        low = guess
    else:
        high = guess
    guess = (low + high) / 2.0
    numGuesses += 1
print('numGuesses: ' + str(numGuesses))
print(str(guess) + ' is close to square root of ' + str(cube))

Newton-Raphson

Square Root

1
2
3
4
5
6
7
8
9
10
#Find the square root of 24
epsilon = 0.01
y = 24.0
guess = y/2.0
numGuesses = 0
while abs(guess**2 - y) >= epsilon:
	numGuesses += 1
	guess = guess - ( (guess**2 - y) / (2 * guess) )
print('numGuesses = ' + str(numGuesses))
print('Square root of ' + str(y) + ' is about ' + str(guess))