方根与巴比伦或苍鹭的方法？

Question

我在java中实现了Babylonian/Heron的方法,以获得基于维基百科信息的数字的平方根

目前我有:

public static void main(String[] args) {
    System.out.println(Sqrt.sqrt1(8));
    //System.out.println(Sqrt.sqrt2(8));   //Infinite loop
    System.out.println(Sqrt.sqrt3(8));
    System.out.println(Sqrt.sqrt4(8));
}

static float sqrt1(float x) {
    float b = 0, h = x;

    while (b != h) {
        b = (h + b) / 2;
        h = x / b;
    }
    return b;
}

static double sqrt2(double x) {
    double b = x, h = 0;

    while (b != h) {
        b = (h + b) / 2;
        h = x / b;
    }
    return b;
}

static double sqrt3(double x) {
    double b = x, h = 0;

    while (Math.abs(b - h) > 0.000000000001) {
        b = (h + b) / 2;
        h = x / b;
    }
    return b;
}

static double sqrt4(double x) {
    double r = x, t = 0;

    while (t != r) {
        t = r;
        r = (x / r + r) / 2;
    }
    return r;
}

输出将是:

2.828427

2.82842712474619

2.82842712474619

sqrt2方法将永远循环,但这只发生在双精度,因为sqrt1方法适用于浮点数.我不知道为什么会这样.因此,如果我想使用双打,sqrt3方法看起来像是要走的路.

我对实施哪些方法感到困惑,¿巴比伦方法与苍鹭方法相同吗？

据我所知,巴比伦方法是基于这样一个事实:正方形的一边是正方形(x)面积的平方根.因此,您可以从具有bh尺寸的矩形开始,获得两边的平均值(b = b + h/2),然后将此结果视为较小矩形的一侧,当然得到另一边(h = x/b).矩形将开始进入所需的正方形.这是我在sqrt1,sqrt2和sqrt3方法中所做的:

while (b != h) {
    b = (h + b) / 2;
    h = x / b;
}

在另一方面,维基百科链接说巴比伦/苍鹭方法是相同的,并将其描述为:

"基本思想是,如果x高估了非负实数S的平方根,则S/x将被低估,因此可以合理地预期这两个数的平均值可以提供更好的近似值"

您可以在sqrt4方法中看到此实现:

    while (t != r) {  
        t = r;  
        r = (x/r + r) / 2;  
    }  

从我所看到的,这两种方法不尽相同,但相似.如果我错了请纠正我.

有趣的是我无法做到:while (b != h) {当b和h是sqrt2方法中显示的双倍时,因为它将永远循环.相反,我用过while (Math.abs(b - h) > 0.000000000001) {

但是,我可以这样做:while (t != r) {使用sq和4中的b和h双打.

我很感激有人解释这种行为.

- - - - - -编辑: - - - - - - - - - - - - - - - - - - - -----------------------

如所建议的,两种算法都是相同的,但实现的不同.但是,以下建议的代码循环,就像sqrt2 x = 8:

static double sqrt5(double x) {
    double b = x;

    while (b != x/b) {
        b = (x / b + b) / 2;
    }
    return b;
}

那么.. sqrt4与其他实现的区别是什么？为什么它不会像其他人一样永远循环？

Answer 1

更新: sqrt4最终退出循环的机会要大于sqrt5因为它的停止条件将一次迭代的近似值与之前的迭代次数进行比较.

计算倾向于减少误差,因此最终计算的值b非常接近于仅在最后一位x/b不同的精确平方根b.此时,(x / b + b) / 2使用可用有限精度计算的值将相等b,并且迭代停止.

例如,如果我们计算sqrt(2)并且已达到近似值b = 1.414213562373095,我们有:

>>> b
1.414213562373095
>>> 2/b                     # Close but not quite equal to b, 
1.4142135623730951          # iteration in sqrt5 continues
>>> (2/b + b)/2        
1.414213562373095           # Exactly equal to b, sqrt4 stops

如您所见,一旦b达到1.414213562373095,其值将不会被循环中的计算更改.因为b和2/b仍然不同,所以最后一位数字sqrt5永远不会退出.

巴比伦和苍鹭的方法是相同的算法,它与用于求解x²= a的Newton-Rhapson方法一致.您拥有的各种实现之间的区别在于停止条件.例如:

while (b != h) {
    b = (h + b) / 2;
    h = x / b;
}

是相同的:

while (b != x/b) {
    b = (x / b + b) / 2;
}

当然,b != x/b不是一个非常好的停止条件,因为b可能永远不会成为x的数学上精确的平方根:如果b不是精确的平方根,则x/b不等于b.例如在Python中:

>>> sqrt(2)
1.4142135623730951
>>> 2/sqrt(2)
1.4142135623730950

例如,您应该几乎总是使用相对差异的界限作为停止条件

eps = 1e-6;
while (abs(b-h)/b > eps) { ...