如何改进这个平方根方法？

Question

我知道这听起来像是家庭作业,但事实并非如此.最近我一直对用于执行某些数学运算的算法感兴趣,例如正弦,平方根等.目前,我正在尝试编写用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个滴答).我知道这个特殊方法永远不会比本机方法更快,但我只是想知道我是否可以进行任何优化.

我立即看到的唯一优化是计算将运行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;

作为您提及的维基百科文章 - 您不能使用牛顿方法有效地计算平方根 - 而是使用对数.

Answer 2

float InvSqrt (float x){
  float xhalf = 0.5f*x;
  int i = *(int*)&x;
  i = 0x5f3759df - (i>>1);
  x = *(float*)&i;
  x = x*(1.5f - xhalf*x*x);
  return x;}

这是我最喜欢的快速平方根.实际上它是平方根的倒数,但你可以在你想要之后将其反转......我不能说如果你想要平方根而不是平方根,那么它是否更快,但它的变形很酷.
http://www.beyond3d.com/content/articles/8/