LeetCode Sqrt(x)：Babylonian法比Bakshali法更快的原因探究

我在LeetCode的Sqrt(x)问题中实现了两种求平方根的方法：巴比伦法（Babylonian Method）和巴克沙利法（Bakshali Method）。理论上巴克沙利法是二次收敛的，相当于两次巴比伦迭代的效果，我原本以为它的效率会更高，但提交后发现巴比伦法的运行速度反而更快。这是为什么？

巴比伦法代码 #

if x <= 1:
    return x
else:
    x_0 = len(str(x)) * (10**2)
    change = 1
    while change > 0.01:
        x_n = 0.5 * (x_0 + x/x_0)
        change = abs(x_0-x_n)
        x_0 = x_n
            
return int(x_0)

巴克沙利法代码 #

if x <= 1:
    return x
else:
    x_0 = 0.5 * x
    change = 1
    while change > 0.01:
        a_n = (x - x_0**2)/(2*x_0)
        b_n = x_0 + a_n
        change = abs((x_0**2)-x)
        x_0 = b_n - (a_n**2)/(2*b_n)
                
return int(x_0)

关键原因分析 #

• 初始值选择差距过大
  巴比伦法的初始值是len(str(x)) * 100，是基于x的位数做的估算，离真实平方根的距离近很多。比如x=10000（平方根100），初始值是4*100=400；而巴克沙利法用的是0.5*x，也就是5000，和真实值差了50倍。初始值偏差大直接导致巴克沙利法需要更多次迭代才能收敛到0.01的精度要求，抵消了它收敛阶高的优势。

• 单次迭代计算量差异明显
  巴克沙利法单次迭代要完成的运算比巴比伦法复杂得多：需要计算平方、两次除法、多次加减；而巴比伦法只需要一次加法、一次除法、一次乘法（乘0.5）。每一次迭代的额外运算开销累积起来，即使收敛阶更高，也架不住迭代次数没减少甚至更多，整体耗时自然更高。

• 停止条件严格程度不同
  巴比伦法的停止条件是两次迭代值的差小于0.01，而巴克沙利法是判断x0²和x的差小于0.01。这两个条件的严格程度不一样：比如当x很大时，x0² -x的0.01阈值对应的x0误差其实更小，会导致巴克沙利法多做几次迭代。比如x=1000000（平方根1000），如果x0=999.99，x0²=999980.0001，和x的差是19.9999，远大于0.01，还得继续迭代；但巴比伦法中如果x0到xn的差小于0.01就会停止，更早退出循环。

• 浮点数运算的额外开销
  浮点数的平方、除法操作本身比加法、乘法的计算开销更大，巴克沙利法里多次用到平方和除法，每一步的耗时都比巴比伦法的简单运算要久，累积下来整体速度就慢了。

内容的提问来源于stack exchange，提问作者abdulqgg