java - 获得近似平方根

Question

我正在使用以下公式实现巴比伦方法来近似数字的平方根：n

nextGuess = (lastGuess + n / lastGuess) / 2;

所以当nextGuess和lasGuess几乎相同时，nextGuess是近似的平方根。

我正在做的是检查是否nextGuess并且lastGuess小于非常小的数字，例如0.0001我可以声称这nextGuess是的近似平方根n。如果不nextGuess成为lastGuess。

那么我怎样才能以正确的方式实现呢？

我当前的代码：

public static void getApproximatedSquare(long n){
    DecimalFormat decimalFormat = new DecimalFormat("#.####");
    decimalFormat.setRoundingMode(RoundingMode.CEILING);

    double lastGuess = 1, nextGuess;

    nextGuess = (lastGuess + n / lastGuess) / 2;
    Double init =  0.0001;
    System.out.println(decimalFormat.format(init));
    if (Double.valueOf(decimalFormat.format(nextGuess)) <= init)
        //todo

}

score 4 · Accepted Answer

目前的实施草案有一些缺陷：

我怀疑你真的需要Double.valueOf(decimalFormat.format(...))，它只是从结果中删除了一些精度
你的收敛条件不是nextGuess < init但是difference_between_nextGuess_and_lastGuess < init
你必须重复近似直到收敛，所以你不能只使用 a if。您需要一个for或while或（如我的解决方案中所示）do... while

这应该可以工作（在每一步，它都会打印最后一个和下一个猜测）

public static double getApproximatedSquare(long n) {
    DecimalFormat decimalFormat = new DecimalFormat("#.####");
    decimalFormat.setRoundingMode(RoundingMode.CEILING);

    double lastGuess, nextGuess = 1;
    double init = 0.0001;
    do {
        lastGuess = nextGuess;
        nextGuess = (lastGuess + (double) n / lastGuess) / 2;
        System.out.println(decimalFormat.format(lastGuess)+" ---> "+decimalFormat.format(nextGuess));
    } while (Math.abs(lastGuess - nextGuess) >= init);
    return nextGuess;
}

score 1 · Accepted Answer

使用绝对容差总是一个坏主意，因为它没有考虑参数的数量级。相对误差更好。

但在平方根的情况下，我推荐一种更好的方法：确保您的初始近似值在精确根的 √2 倍范围内。这是通过将参数的浮点表示中的 2 的指数减半来获得的。（如果你不能访问这个指数，你可以通过连续的除法或乘法得到它，直到达到区间 [1, 2)。）

示例：对于 27，您有 16 ≤ 27 < 32。那么 1 ≤ √27 / 4 < √2，您可以从 4 开始迭代。

然后执行巴比伦公式的四次迭代。不多，不多。

在该示例中，经过四次迭代，您将获得 5.19615242271，这是准确的。

如果你觉得连续的减半或加倍过程很慢，并且认为牛顿更快，请考虑 (x + n / x) / 2 > x / 2，这样牛顿实际上比减半收敛得慢，涉及更多的算术！

score 0 · Accepted Answer

如果nextGuess' 的值是 100% 肯定会下降并达到足够好的值，你不能这样做吗？

public static void getApproximatedSquare(long n){
    DecimalFormat decimalFormat = new DecimalFormat("#.####");
    decimalFormat.setRoundingMode(RoundingMode.CEILING);

    double lastGuess = n + 1;
    double nextGuess = n;
    double init      = 0.0001;

    while (lastGuess - nextGuess > init)
    {
        lastGuess = nextGuess;
        nextGuess = (lastGuess + n / lastGuess) / 2;
    }

    System.out.println(decimalFormat.format(init));
}

score -1 · Accepted Answer

作为上述nextGuess方法sqrt(n)，您可以使用以下方法：

double lastGuess = n;
double nextGuess = n;
double epsilon = 1e-4;
while (lastGuess - nextGuess > epsilon) {
    lastGuess = nextGuess;
    nextGuess = (lastGuess + n / lastGuess) / 2;
}

java - 获得近似平方根

4 回答 4

Related

Reference