通过对分搜索寻找非完美立方体的立方根时出现无限循环

Question

这段代码在deltanum = 0.0000000000001时给出相当准确的结果，但在deltanum = 0.00000000000001时进入无限循环（在deltanum中再加一个零）。你知道吗

它只适用于非完美立方体，对1000个完美立方体也适用。为什么？你知道吗

我是编程新手，跟随奥苏。你知道吗

num = 100
high = num
low = 0
icount = 0
cuberoot = (high + low)/2      #cuberoot of num
deltanum = 0.00000000000001
while abs(cuberoot**3 - num)>=deltanum:
    icount+=1
    print(icount)
    if cuberoot**3 > num:
        high = cuberoot
    elif cuberoot**3 < num:
        low = cuberoot
    else:
        break
    cuberoot = (high + low)/2
print("Cube root: " + str(cuberoot))
print("Number of iterations: " + str(icount))

Answer 1

大多数人会把它命名为epsilon，并用delta表示cuberoot**3 - num。你知道吗

最后，你希望这个表达

    cuberoot = (high + low)/2

将为您在每次迭代中获得大约多一点的精确性。 （接近开始时，每次大约将错误位数减半。）

您在抱怨IEEE-754 double在计算多维数据集时精度有限，而且存在差异。 53位给出了16位小数，而ε是1e-14。 但是一个输入num只有几个数字长，就会消耗掉你的边距，正如你发现的那样。你知道吗

对于更高精度的计算，您可能更喜欢使用Decimal。 或者，查看gmp库。你知道吗

你相信某种循环不变量成立， 数量cuberoot和cuberoot ** 3在每次迭代中都会改变。 验证起来很简单。 只需将它们赋给临时变量，并验证它们是否更改。 如果他们没有提前终止循环。 更一般而言，要检测少数限制值之间的振荡，请将以前的值放入set中，并在看到重复值时提前终止。你知道吗

Answer 2

您使用的是floats。float数学在精度方面有缺陷-您的增量可能太小，无法正常工作，并且您的解决方案在值之间翻转，而从未达到while条件限制。请参阅Is floating point math broken?了解有关为什么float有时会“中断”的更多推理。你知道吗

您也可以将其限制为一定的重复次数：

num = 100
high = num
low = 0
icount = 0
maxcount = 100000
cuberoot = (high + low)/2      #cuberoot of num
deltanum = 0.00000000000001
while abs(cuberoot**3 - num)>=deltanum:
    icount+=1
    print(icount)
    if cuberoot**3 > num:
        high = cuberoot
    elif cuberoot**3 < num:
        low = cuberoot
    else:
        break
    cuberoot = (high + low)/2

    if icount > maxcount:
        print("Unstable solution reached after ",maxcount, "tries")
        break
print("Cube root: " + str(cuberoot) + " yields " + str(cuberoot**3))
print("Number of iterations: " + str(icount))

输出：

Unstable solution reached after  100000 tries
Cube root: 4.641588833612779 yields 100.00000000000003
Number of iterations: 100001