应该添加浮点数以获得最精确的结果？

Question

这是我在最近的采访中被问到的一个问题,我想知道(我实际上并不记得数值分析的理论,所以请帮助我:)

如果我们有一些累积浮点数的函数:

std::accumulate(v.begin(), v.end(), 0.0);

vstd::vector<float>例如,是一个.

• 在累积它们之前对这些数字进行排序会更好吗？

• 哪个订单会给出最准确的答案？

我怀疑按升序排序数字实际上会减少数值误差,但不幸的是我无法证明这一点.

PS我确实意识到这可能与现实世界的编程无关,只是好奇.

Answer 1

你的直觉基本上是正确的,按升序(大小)排序通常会有所改善.考虑我们添加单精度(32位)浮点数的情况,并且有10亿个值等于1 /(10亿),并且一个值等于1.如果1首先出现,那么总和将会到来由于精度损失,1 +(1/1十亿)为1.每次添加对总数都没有影响.

如果小值首先出现,它们至少会总结为某些东西,尽管即便如此,我有2 ^ 30个,而在2 ^ 25左右之后,我又回到了每个人不会影响总数的情况下更多.所以我仍然需要更多技巧.

这是一个极端情况,但一般情况下,添加两个相似幅度的值比添加两个非常不同的值的值更准确,因为您以较小的值"丢弃"较少的精度位.通过对数字进行排序,您可以将相似幅度的值组合在一起,并通过按升序添加它们,您可以为小值提供累积达到较大数字幅度的"机会".

尽管如此,如果涉及负数,很容易"智胜"这种方法.考虑三个要求的值,{1, -1, 1 billionth}.算术正确的总和是1 billionth,但如果我的第一个加法涉及微小的值,那么我的最终总和将是0.在6个可能的订单中,只有2个是"正确的" - {1, -1, 1 billionth}和{-1, 1, 1 billionth}.所有6个订单给出的结果在输入中最大幅度值的范围内是准确的(0.0000001%输出),但是对于其中4个,结果在真实解决方案的范围内是不准确的(100%输出).您正在解决的特殊问题将告诉您前者是否足够好.

事实上,除了按排序顺序添加它们之外,您还可以玩更多技巧.如果你有很多非常小的值,中等数量的中等值,以及少量的大值,那么首先将所有小值相加可能是最准确的,然后分别总计中等值,加上这两个总数然后加上大的.找到最准确的浮点加法组合并不是一件容易的事情,但是为了应对非常糟糕的情况,你可以保持不同大小的整个运行总数,将每个新值添加到与其幅度最匹配的总数中,当一个运行总计开始变得太大而不是它的大小时,将它添加到下一个总计并开始一个新的.从它的逻辑极端来看,这个过程相当于以任意精度类型执行求和(所以你要这样做).但是考虑到以递增或递减的顺序添加的简单选择,升序是更好的选择.

它确实与现实世界的编程有一定关系,因为在某些情况下,如果你不小心砍掉由大量值组成的"重"尾巴,你的计算可能会出现严重错误,每个值都太小而不能单独影响总和,或者如果你从许多小的值中抛弃太多的精度,这些小的值只会影响总和的最后几位.如果尾巴可以忽略不计,你可能不在乎.例如,如果您只是首先将少量值加在一起,而您只使用总和中的一些有效数字.

Answer 2

还有一种算法设计用于这种累积操作,称为Kahan Summation,你可能应该知道.

根据维基百科,

的Kahan的求和算法(也称为补偿求和)显著降低通过添加有限精度浮点数的一个序列获得的总的数值误差,相对于明显的方法.这是通过保持单独的运行补偿(一个变量来累积小错误)来完成的.

在伪代码中,算法是:

function kahanSum(input)
 var sum = input[1]
 var c = 0.0          //A running compensation for lost low-order bits.
 for i = 2 to input.length
  y = input[i] - c    //So far, so good: c is zero.
  t = sum + y         //Alas, sum is big, y small, so low-order digits of y are lost.
  c = (t - sum) - y   //(t - sum) recovers the high-order part of y; subtracting y recovers -(low part of y)
  sum = t             //Algebraically, c should always be zero. Beware eagerly optimising compilers!
 next i               //Next time around, the lost low part will be added to y in a fresh attempt.
return sum

Answer 3

我在Steve Jessop提供的答案中尝试了极端的例子.

#include <iostream>
#include <iomanip>
#include <cmath>

int main()
{
    long billion = 1000000000;
    double big = 1.0;
    double small = 1e-9;
    double expected = 2.0;

    double sum = big;
    for (long i = 0; i < billion; ++i)
        sum += small;
    std::cout << std::scientific << std::setprecision(1) << big << " + " << billion << " * " << small << " = " <<
        std::fixed << std::setprecision(15) << sum <<
        "    (difference = " << std::fabs(expected - sum) << ")" << std::endl;

    sum = 0;
    for (long i = 0; i < billion; ++i)
        sum += small;
    sum += big;
    std::cout  << std::scientific << std::setprecision(1) << billion << " * " << small << " + " << big << " = " <<
        std::fixed << std::setprecision(15) << sum <<
        "    (difference = " << std::fabs(expected - sum) << ")" << std::endl;

    return 0;
}

我得到了以下结果:

1.0e+00 + 1000000000 * 1.0e-09 = 2.000000082740371    (difference = 0.000000082740371)
1000000000 * 1.0e-09 + 1.0e+00 = 1.999999992539933    (difference = 0.000000007460067)

第一行中的错误在第二行中大于十倍.

如果我在上面的代码中将doubles 更改为s float,我得到:

1.0e+00 + 1000000000 * 1.0e-09 = 1.000000000000000    (difference = 1.000000000000000)
1000000000 * 1.0e-09 + 1.0e+00 = 1.031250000000000    (difference = 0.968750000000000)

答案都不接近2.0(但第二个稍微接近).

使用doubleDaniel Pryden描述的Kahan求和(用s):

#include <iostream>
#include <iomanip>
#include <cmath>

int main()
{
    long billion = 1000000000;
    double big = 1.0;
    double small = 1e-9;
    double expected = 2.0;

    double sum = big;
    double c = 0.0;
    for (long i = 0; i < billion; ++i) {
        double y = small - c;
        double t = sum + y;
        c = (t - sum) - y;
        sum = t;
    }

    std::cout << "Kahan sum  = " << std::fixed << std::setprecision(15) << sum <<
        "    (difference = " << std::fabs(expected - sum) << ")" << std::endl;

    return 0;
}

我得到2.0:

Kahan sum  = 2.000000000000000    (difference = 0.000000000000000)

即使我在上面的代码中将doubles 更改为s float,我得到:

Kahan sum  = 2.000000000000000    (difference = 0.000000000000000)

似乎Kahan是要走的路!

Answer 4

有一类算法可以解决这个确切的问题,而无需对数据进行排序或重新排序.

换句话说,求和可以在数据上一次完成.这也使得这样的算法适用于预先不知道数据集的情况,例如,如果数据实时到达并且需要维持运行总和.

这是最近一篇论文的摘要:

我们提出了一种新颖的在线算法,用于精确求和浮点数流."在线"是指算法一次只能看到一个输入,并且可以采用这种输入的任意长度输入流,同时只需要恒定的存储器."精确"是指我们算法的内部数组的总和恰好等于所有输入的总和,返回的结果是正确舍入的总和.正确性证明对所有输入(包括非标准化数字但模数中间溢出)有效,并且与加数的数量或和的条件数无关.该算法渐近地每个求和只需要5个FLOP,并且当指令级数大于10,000时,由于指令级并行性运行速度仅比明显的,快速但愚蠢的"普通递归求和"循环慢约2-3倍. .因此,据我们所知,它是已知算法中最快,最准确,最大的内存效率.实际上,如果没有硬件改进,很难看出更快的算法或需要明显更少FLOP的算法.提供了大量加数的应用程序.

来源:算法908:浮点流的在线精确求和.