平方根的巴比伦算法。

1 巴比伦算法介绍一

巴比伦算法可能算是最早的用于计算$sqrt{S}$的算法之一，因为其可以用牛顿法导出，因此在很多地方也被成为牛顿法。其核心思想在于为了计算x的平方根，可以从某个任意的猜测值g开始计算。在真实的运算中，我们往往将g直接设置为x，不过也可以选择其他任何的正数值。那么其计算的迭代过程为:

1.如果猜测值g已经足够接近于正确的平方根，算法结束，函数将g作为结果返回。

2.如果猜测值g不够精确，那么使用g和x/g的平均值作为新的猜测值。因为这两个值中的一个小于确切的平方根，另一个则大于确切的平方根，选择平均值有助于你得到一个更接近于正确答案的值。

3.把新的猜测值赋予给变量g，重复第一步的判断。

2 巴比伦算法介绍二

1.    假设要求a的平方根，先找到一个近似值x0，如a/2；

2.    被开方数a除以近似值x0;

3.    求第一步和第二步得到的值的平均数；

4.    令平均数为新的近似值，返回第二步，循环计算（根据精度要求，进行循环控制）

经过前面四个步骤，可以得到如上公式；

对公式的理解：可以把xn理解为x0，xn+1理解为x1，然后套用公式即可。

3 核心代码

/// <summary>
/// 计算 v 的平方根
/// 据说来自于远古巴比伦时代的算法
/// </summary>
/// <param name="v"></param>
/// <returns></returns>
public static double Sqrt(double v)
{
    const double e = 0.000001;
    double x = v;
    double y = 1.0;
    while ((x - y) > e)
    {
        x = (x + y) / 2;
        y = v / x;
    }
    return x;
}
 

---------------------------------------------
POWER BY TRUFFER.CN