如何汇总大量浮点数？

Question

我建立了一个并行和代码来汇总大量的浮点数然后我发现当数字的数量大于100000000时,结果会出错.然后我构建一个串行代码进行比较.序列号也输错了号码.谁知道为什么？谢谢!

我的简单代码如下.

结果是"1.67772e + 007".它应该是1e + 008

int main()
{
    size_t N=100000000;
    cout<<"n is : "<<N<<endl;
    clock_t start = clock();
    task_scheduler_init init;
    vector<float> myvec;
    vector<float>* pvec;
    for(int i=0;i<N;i++)
        myvec.push_back(1.0f);
    pvec=&myvec;
    float mysum;
    mysum=parallelSum(pvec);
    cout<<" the p sum is: "<<mysum<<endl;
    clock_t finish = clock();
        cout<<"Time Used  = "<<(finish - start)/CLOCKS_PER_SEC<<endl;
        mysum=0;
       for(int i=0;i<N;i++)
    mysum+=myvec[i];
        cout<<" the s sum is: "<<mysum<<endl;
    return 0;
}

Answer 1

您的问题是由于浮点数的可用精度有限.

而

1.0f + 1.0f == 2.0f, 

你会发现的

16777216.0f + 1.0f == 16777216.0f

额外的1.0f被丢弃,因为16777217无法以float格式表示.

看看你的结果--1.67772e + 007 - 很明显,这正是发生的事情.

您的预期结果100000000.0比16777216.0f大很多(6x),但是一旦总和达到16777216.0f,它将保留在那里,剩下的8327884增加了1.0f.

解决方案:尝试使用double代替float,其中最多去9007199254740992.0触及这个问题之前.

为什么？

在单精度浮点中,只有24位精度可用,2 ^ 24是16777216.没有办法以24位编码16777217,因此它只是保持在16777216,因为它足够接近真实答案.当你向一个大数字添加许多非常小的数字时会产生真正的问题,其中小数字的总和相对于大数字是显着的,但是它们不是.

请注意,16777216.0f不是可以表示的最大数字float,但只表示精度限制.例如,16777216.0fx 2 ^ 4 + 2 ^ 4 => 16777216.0fx 2 ^ 4

double具有53位精度,因此可以编码最多2 ^ 53,或者9007199254740992.0在达到添加1.0d失败的点之前.

这个问题也代表了浮点运算并行化的另一个危险 - 浮点加法不是关联的,换句话说,你的顺序算法:

Sum(A) = (...((((A1 + A2) + A3) + A4) ... A10000)

可能会产生与并行版本不同的结果:

Sum(A) = (...((((A1 + A2) + A3) + A4) ... A1000)
       + (...((((A1001 + A1002) + A1003) + A1004) ... A2000)
       + (...((((A2001 + A2002) + A2003) + A2004) ... A3000)
       ...
       + (...((((A9001 + A9002) + A9003) + A9004) ... A10000)

因为任何给定的步骤可能会失去不同程度的精度.

这并不意味着两者都更正确,但你可能会得到意想不到的结果.

如果您真的必须使用float,请尝试以下方法:

• 将您的数字从最负数到最正数排序(顺序(N log N))
• 依次添加每一对:B1:= A1 + A2,B2:= A3 + A4,B3:= A5 + A6这会产生一个新的列表B,是初始列表的一半长度
• 在B上重复此过程以获得C,C获得D等
• 当只剩下一个号码时停止.

请注意,这会将您的算法复杂度从O(N)操作更改为O(N log N)操作,但更有可能产生正确的数字.它非常平行.如果你聪明的话,你可以合并排序和求和操作.

Answer 2

使用Kahan求和算法

• 它具有与天真求和相同的算法复杂度
• 它将大大提高求和的准确性,而无需将数据类型切换为double.

我使用std :: accumulate测试了总计1000000的1.0f浮点数 - 结果是1.67772e + 007.但是,使用此Kahan求和实现,结果是1e + 008

template <class Iter>
float kahan_summation(Iter begin, Iter end) {
  float result = 0.f;

  float c = 0.f;
  for(;begin != end; ++begin) {
    float y = *begin - c;
    float t = result + y;
    c = (t - result) - y;
    result = t;
  }
  return result;
}

您当然可以切换到all floats,doubles并且kahan求和算法将提供比使用双精度的朴素求和更高的精度.

Answer 3

IEEE754 不准确。尝试一下GMP。