二分搜索平方根实现

Question

当试图找到一个数字二分法的平方根的近似值时，算法似乎表现得非常好。

事实上，二分法搜索仅需一秒钟即可得出 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)

但是当要找到 10**46 时，它计算了这么长时间，我最终终止了它...

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)

有什么解释吗？任何人都可以运行吗？

Answer 1

@Lecagy 是正确的。问题是浮点数的数量是有限的。因此，当您对相邻的两个进行平均时，平均数是两者之一。

你只需要添加一个条件来检查这个。

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)

现在它可以立即运行，但不能保证在 epsilon 内。

二分搜索平方根实现

bisection search square root implementation

algorithm

search

iteration

bisection