如何改善这种平方根方法? [英] How can I improve this square root method?

问题描述

我知道这听起来像是一项家庭作业，但事实并非如此.最近，我对用于执行某些数学运算(例如正弦，平方根等)的算法感兴趣.目前，我正在尝试编写

I know this sounds like a homework assignment, but it isn't. Lately I've been interested in algorithms used to perform certain mathematical operations, such as sine, square root, etc. At the moment, I'm trying to write the Babylonian method of computing square roots in C#.

到目前为止，我有这个:

So far, I have this:

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个刻度).我知道这个特定的方法永远不会比原生方法快，但是我只是想知道我是否可以进行任何优化.

It works just fine and produces the exact same answer as the .NET Framework's Math.Sqrt() method every time. As you can probably guess, though, it's slower than the native method (by around 800 ticks). I know this particular method will never be faster than the native method, but I'm just wondering if there are any optimizations I can make.

我立即看到的唯一优化是，即使确定了答案后，计算也将运行100次(此时，r始终是相同的值).因此，我添加了一个快速检查功能，以查看新计算出的值是否与先前计算出的值相同，并退出循环.不幸的是，它并没有对速度产生太大影响，但似乎是正确的选择.

The only optimization I saw immediately was the fact that the calculation would run 100 times, even after the answer had already been determined (at which point, r would always be the same value). So, I added a quick check to see if the newly calculated value is the same as the previously calculated value and break out of the loop. Unfortunately, it didn't make much of a difference in speed, but just seemed like the right thing to do.

在您说为什么不使用Math.Sqrt()代替?"之前，我只是作为学习练习，并不打算在任何生产代码中实际使用此方法.

And before you say "Why not just use Math.Sqrt() instead?"... I'm doing this as a learning exercise and do not intend to actually use this method in any production code.

推荐答案

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

First, instead of checking for equality (r == last), you should be checking for convergence, wherein r is close to last, where close is defined by an arbitrary epsilon:

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

正如您链接的维基百科文章所提到的那样-您无法使用牛顿方法有效地计算平方根-而是使用对数.

As the wikipedia article you linked to mentions - you don't efficiently calculate square roots with Newton's method - instead, you use logarithms.

这篇关于如何改善这种平方根方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！