CODEWITHSUNDEEP
algorithmsearchiterationbisection
Alex S
Alex S

Reputation: 91

bisection search square root implementation

When trying to find a close approximate of the square root of a number bisection algorithms seems to perform extremely well.

In fact bisection search gives a result in just a second for the square root of 10^45 

start_time = time.time()
x = 10**45
epsilon = 0.01
numGuesses = 0
low = 0.0
high = max(1.0, x)
ans = (high + low)/2.0

while abs(ans**2 - x) >= epsilon:
    print('low =', low, 'high =', high, 'ans =', ans)
    numGuesses += 1
    if ans**2 < x:
        low = ans
    else:
        high = ans    
    ans = (high + low)/2.0
print('numGuesses =', numGuesses)
print(ans, 'is close to square root of', x)

elapsed_time = time.time() - start_time
print(elapsed_time)

But when it comes to finding 10**46 it calculates for so long I eventually terminate it...

start_time = time.time()
x = 10**46
epsilon = 0.01
numGuesses = 0
low = 0.0
high = max(1.0, x)
ans = (high + low)/2.0

while abs(ans**2 - x) >= epsilon:
    print('low =', low, 'high =', high, 'ans =', ans)
    numGuesses += 1
    if ans**2 < x:
        low = ans
    else:
        high = ans    
    ans = (high + low)/2.0
print('numGuesses =', numGuesses)
print(ans, 'is close to square root of', x)

elapsed_time = time.time() - start_time
print(elapsed_time)

Is there any explanation? Can anyone run it?

Upvotes: 1

Views: 228

Answers (1)

btilly
btilly

Reputation: 46497

@Lecagy is correct. The problem is that there are a finite number of floating point numbers. Therefore when you average two that are next to each other, the average is one of the two.

You just need to add a condition to check for this.

import time
start_time = time.time()
x = 10**46
epsilon = 0.01
numGuesses = 0
low = 0.0
high = max(1.0, x)
ans = (high + low)/2.0

while abs(ans**2 - x) >= epsilon and ans != low and ans != high:
    print('low =', low, 'high =', high, 'ans =', ans)
    numGuesses += 1
    if ans**2 < x:
        low = ans
    else:
        high = ans
    ans = (high + low)/2.0
print('numGuesses =', numGuesses)
print(ans, 'is close to square root of', x)

elapsed_time = time.time() - start_time
print(elapsed_time)

And now it runs instantly but is not guaranteed to be within epsilon.

Upvotes: 1

Related Questions