二等分搜索平方根实现

Alex S 发表于 Dev

亚历克斯·S

试图找到数字平方根的近似值时，二等分算法似乎表现出色。

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

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

btilly

@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之内。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。