通过逐次逼近实现平方根法

Question

逐次逼近求平方根是使用以下算法实现的：

首先猜测平方根是 x / 2。将这个猜测称为 g。
实际平方根必须在 g 和 x/g 之间。在逐次逼近的每一步，通过平均 g 和 x/g.
重复步骤 2，直到 g 和 x/g 的值在硬件精度允许的范围内尽可能接近。在 Java 中，检查此条件的最佳方法是测试平均值是否等于用于生成它的任一值。

真正让我困惑的是第3步的最后一句，我解释如下：

private double sqrt(double x) {
    double g = x / 2;
    while(true) {
        double average = (g + x/g) / 2;
        if(average == g || average == x/g) break;
        g = average;
    }

    return g;
}

这似乎只会导致无限循环。我完全遵循算法，如果平均值等于 g 或 x/g（用于生成它的两个值），那么我们就有了答案？

Answer 1

永远不要比较浮点值是否相等。结果不靠谱。

像这样使用 epsilon：

if(Math.abs(average-g) < 1e-7 || Math.abs(average-x/g) < 1e-7)

您可以将 epsilon 值更改为您需要的任何值。可能最好的是与原始 x 有关的内容。

Answer 2

要检查 g 和 x/g 是否与硬件允许的一样接近，请查看相对差异并进行比较它与浮点格式的 epsilon 一起使用。如果它在 epsilon 的小整数倍以内，则可以。

x和y的相对差异，见https://en.wikipedia.org/wiki/Relative_change_and_difference

32 位 IEEE 浮点数的 epsilon 约为 1.0e-7，如此处的其他答案之一，但该答案使用的是绝对差异而不是相对差异。

实际上，这意味着：

 Math.abs(g-x/g)/Math.max(Math.abs(g),Math.abs(x/g)) < 3.0e-7

Answer 3

为什么有人会使用这种方法，他们可以简单地使用 (2n^2) = 4n^2 和 (n + 1)^2 = n^2 + 2n + 1 的公式来填充每个尾数中的位，并将指数除以二，将尾数乘以二当且仅当指数的 mod 与两个等于 1?

通过逐次逼近实现平方根法

Implementing the square root method through successive approximation

algorithm

square-root