尝试通过二分搜索查找非完美立方体的立方根时出现无限循环

Question

此代码在 deltanum = 0.0000000000001 时给出相当准确的结果，但在 deltanum = 0.00000000000001 时进入无限循环（在 deltanum 中添加另一个零）。

它只发生在非完美的立方体上，它适用于像 1000 这样的完美立方体。为什么？

我是编程新手，跟随 OSSU。

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

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

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

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

Answer 2

大多数人会命名为 epsilon，并将 delta 用于 cuberoot**3 - num。

到最后，您希望这个表达式，

    cuberoot = (high + low)/2

会让你在每次迭代中的答案中大约多一点精度。（接近开始时每次大约将错误位数减少一半。）

您在抱怨 IEEE-754 double 在计算立方体时精度有限，还有差异。五十三位给你将近十六位十进制数字，你的 epsilon 是 1e-14。但是，如您所见，几位数长的输入 num 会蚕食您的利润。

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

你相信某个循环不变量成立，数量 cuberoot 和 cuberoot ** 3 将在每次迭代中改变。验证起来很简单。只需将它们分配给临时变量，并验证它们是否发生变化。如果他们不这样做，请尽早终止循环。更一般地说，要检测少数限制值之间的振荡，将先前的值放入 set 并在看到重复值时提前终止。

尝试通过二分搜索查找非完美立方体的立方根时出现无限循环

Infinite loop when trying to find cube root of a non-perfect cube through bisection search

python

python-3.x

bisection