浮点计算误差集累

2012-06-05

同一个函数,即使用递归和非递归两种形式实现,其计算结果都可能不相同。

比如计算 1+e2+e3+…+en

double f(int n)
{
        if(n == 0)
                return exp(0);
        else
                return exp(n) + f(n-1);
}

对比下面

sum = 0;
for(int i=0; i<n; i++)
{
        sum += exp(i);
}

有什么区别呢?计算顺序不同。

上面的是递归到函数栈的底部,回去的时候计算的。也就是说它的计算顺序是:

f(n) = exp(n) + f(n-1)
=exp(n) + exp(n-1) + f(n-2)
=exp(n) + exp(n-1) + exp(n-2) + f(n-3)

=exp(n) + exp(n-1) + exp(n-2) + … + f(2)
=exp(n) + exp(n-1) + exp(n-2) + … + exp(2) + f(1)
=exp(n) + exp(n-1) + exp(n-2) + … + exp(2) + exp(0)

  是从exp(n)加到exp(0)的,与for那个的计算顺序相反。

两者加的数都是一样的。但计算顺序不一样。由于浮点运算的误差集累,最终得到的结果不一样。

这样带来的误差看似微小,但在某些场合积累下来之后误差却是惊人的。