平方根2的二进制搜索

Question

我有一个问题，我的二进制搜索算法寻找2的平方根似乎是在一个无限循环中，并永远运行：

num = 2
low = 1
high = num
i = 0
while((i**2) != 2): #was while(low<high): but wasnt working with it either
 i = low + (high - low) / 2;

 sqrt = i * i

 if (sqrt == num):
     print(i)
 elif(sqrt < num):
     low = i
 else:
     high = i
print(sqrt)    

testRoot = 2 ** (.5)
print(testRoot)

我不确定我的while循环是否存在问题。我认为这将是一个非常直接的二进制搜索算法，只需稍加修改即可适应平方根方面。

当运行我的代码时，我似乎无法让它产生任何输出。我不确定代码或编译器是否存在真正的问题，因为我认为我遵循的算法与过去非常接近。

Answer 1

两个浮点数之间的相等是一个非常严格的条件，因为2的平方根在小数点后有无限位数。在以下情况下尝试此：

while (abs((i ** 2) - 2) > 1e-8)

Answer 2

正如我在最初的评论和所有答案中提到的，2的平方根是非理性的。每一个不是完美平方的整数的平方根都是无理的，所以2在这方面并不特别。重要的是，x**2==2对于任何具有有限精度的x（因为有限精度是表示数字是有理数的另一种方式）来说永远不会是真的。

其他答案建议搜索，直到达到某个固定的、预先确定的精度。这很有效，特别是如果你提前知道答案的二进制数量级，那么你可以将结果的精度设置为最后一位。

我想建议一种更自然的方法。您可以检查中心值是否正好等于其中一个边界。这意味着，在当前的猜测中，两个边界之间的差异有一半表示精度不到一位数。您对中心的措辞已经正确：i=low（high-low）/2可以使用=与low和high进行比较，而i=（low-high）/2可能不能。这是因为high-low的精度大于或等于任一边界的精度，而low-high可能会丢失一些数字。

因此，以下是我的建议：

num = 2
low = 1
high = num
guess = low + (high - low) / 2
count = 0
while guess != low and guess != high:
    sqr = guess * guess

    if sqr == num:
        break
    elif(sqr < num):
        low = guess
    else:
        high = guess

    guess = low + (high - low) / 2
    count += 1
else:
    if abs(low * low - num) < abs(high * high - num):
        guess = low
    else:
        guess = high

print(count, ':', sqr)
print(num ** (.5), '~=', guess)

我添加了count以进行验证。在52次迭代中获得结果，精度在1位数以内：

52 : 2.0000000000000004
1.4142135623730951 ~= 1.4142135623730951 

对边界的最后检查（while中的else子句）可确保您获得最接近所需结果的边界，而不管您先点击哪个边界。

收敛是合理的：IEEE-754格式的64位浮点数尾数中有53位，因此有必要将搜索空间精确地减半很多次才能得到结果（第一次是在循环之外）。

这是我用来测试的片段：https://ideone.com/FU9r82

Answer 3

问题是，在浮点数上使用=几乎总是一个糟糕的做法，对此有各种各样的问题。您应该用abs（a-b）替换比较

我修改后的代码看起来像这样（Python 3），如果你想要更精确，用更小的数字替换1e-6。但是请注意，“太精确”是不明智的，如果您希望循环停止，建议精度为1.0e-15或更大，因为浮点数本身有精度限制。

num = 2
low = 1
high = num
i = 0
while abs((i**2) - num) > 1e-6:  # Note
    i = low + (high - low) / 2
    sqrt = i * i

    if abs(sqrt - num) < 1e-6:  # Note
        print(i)
    elif(sqrt < num):
        low = i
    else:
        high = i
print(sqrt)

testRoot = 2 ** (.5)
print(testRoot)