等分搜索平方根实现

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

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