小池有话说

开方运算

2016-02-04

如何计算开方呢?在我小的时候,我就知道如何计算了。 比如说计算2的开方,显然比1大,比2小,因为2的平方就是4了。我先从1.1开始试,因为我记的11,12,13,14,15的平方,因此我知道14的平方是196,15的平方是225,因此小数点后一位是4,我现在开到了1.4,然后我就一点点的试,保证它刚好比2小一点点。最后,如果我愿意,我会试出来无限位。

当然,我不愿意,因为这个活动太枯燥了。

不过,有了计算机,枯燥的事情都可以交给它来做。我们来看看,计算机如何计算开方吧。

我们可以像笔算一样计算,不过,这里有一个更加简单的过程:

如计算y的平方根,任意猜一个数字x, 如数字不对,则 y/x 也一定不对。但正确的答案一定在这两个数之间,因此我们取平均数(x+y/x)/2,一定比x更准确。

于是我们写出计算程序

double better_guess(double guess, double y) {
    return (guess + y/guess) / 2.0;
}

这个按照这个计算100次,总能计算得比较正确。(足够暴力)

double sqrt(double y)
{
    double guess = 1.0;
    for (int x=0; x < 100; x++) {
        guess = better_guess(guess, y);
    }
    return guess;
}

我们按照这个思路写程序,测试一下:

ours.sqrt(2.000000) = 1.414214
math.sqrt(2.000000) = 1.414214
ours.sqrt(0.000009) = 0.003000
math.sqrt(0.000009) = 0.003000
ours.sqrt(200000000000000000000.000000) = 14142135623.730951
math.sqrt(200000000000000000000.000000) = 14142135623.730951

我们惊喜的发现,正确性是足够的。