c# - 我怎样才能改进这个平方根方法？

Question

我知道这听起来像是家庭作业，但事实并非如此。最近我对用于执行某些数学运算的算法很感兴趣，例如正弦、平方根等。目前，我正在尝试编写 Babylonian method在 C# 中计算平方根。

到目前为止，我有这个:

public static double SquareRoot(double x) {
    if (x == 0) return 0;

    double r = x / 2; // this is inefficient, but I can't find a better way
                      // to get a close estimate for the starting value of r
    double last = 0;
    int maxIters = 100;

    for (int i = 0; i < maxIters; i++) {
        r = (r + x / r) / 2;
        if (r == last)
            break;
        last = r;
    }

    return r;
}

它工作得很好，每次都会产生与 .NET Framework 的 Math.Sqrt() 方法完全相同的答案。不过，正如您可能猜到的那样，它比本地方法慢(大约 800 ticks)。我知道这种特殊方法永远不会比 native 方法快，但我只是想知道是否可以进行任何优化。

我立即看到的唯一优化是计算将运行 100 次，即使在答案已经确定之后(此时，r 始终是相同的值)。因此，我添加了一个快速检查以查看新计算的值是否与先前计算的值相同并跳出循环。不幸的是，这对速度没有太大影响，但似乎是正确的做法。

在你说“为什么不直接使用 Math.Sqrt() 而不是？”之前...我这样做是为了学习练习，并不打算在任何生产代码中实际使用这种方法。

Answer 1

首先，您应该检查收敛性，而不是检查是否相等(r == last)，其中 r 接近 last，其中 close 由任意 epsilon 定义:

eps = 1e-10  // pick any small number
if (Math.Abs(r-last) < eps) break;

正如您链接到的维基百科文章提到的那样 - 您无法使用牛顿法有效地计算平方根 - 相反，您可以使用对数。