比较C或C++中两个浮点值的总和

假设您有两组根据IEEE754实现的浮点变量,意味着将其视为根据标准中的公式计算的精确值.所有合法价值都是可能的.集合中的变量数量可以是任何自然数.

在数学意义上,比较精确的,由所述变量表示的值的总和是什么是好的方法.由于域的性质,问题可以很容易地表示为将单个总和与零进行比较.您可以忽略存在NaN或Infinities的可能性,因为它与核心问题无关.(可以轻松独立地检查这些值,并以适合此问题的特定应用的方式采取行动.)

一种天真的方法是简单地求和和比较,或者将一组的值和另一组的值相加.

    bool compare(const std::vector& lhs, const std::vector& rhs)
    {
        float lSum = 0.0f;
        for (auto value : lhs)
        {
            lSum += value;
        }
        float rSum = 0.0f;
        for (auto value : rhs)
        {
            rSum += value;
        }

        return lSum < rSum;
    }

很明显,在关于浮点运算的各种其他问题中提到的天真方法存在问题.大多数问题都与两个困难有关:

浮点值的相加结果根据顺序而不同

添加某些值集的某些顺序可能导致中间溢出(计算的中间结果超出可用数据类型支持的范围)

float small = strtof("0x1.0p-126", NULL);
float big = strtof("0x1.8p126", NULL);

std::cout << std::hexfloat << small + big - big << std::endl;
std::cout << std::hexfloat << (big-2*small) + (big-small) + big - (big+small) - (big+2*small) << std::endl;

此代码将导致0和inf; 这说明了排序如何影响结果.希望,订购问题也是非常重要的.

float prev;
float curr = 0.0f;

do
{
    prev = curr;
    curr += strtof("0x1.0p-126", NULL);
} while (prev != curr);

std::cout << std::hexfloat << curr << std::endl;

如果有足够的时间来实际完成计算,这段代码将导致0x1.000000p-102,而不是天真的预期,0x1.fffffep127(建议将curr初始化更改为`strtof("0x1.fff000p-103")实际观察到这一点.); 这说明了添加的中间结果与特定加数之间的比例如何影响结果.

关于获得最佳精度的说法很多,例如.这个问题.

手头的问题不同之处在于我们不希望最大限度地提高精度,但我们有一个明确定义的功能需要精确实现.

虽然对某些人来说这可能是有用的想法运动似乎充其量存在争议,但请考虑以下情况:这些值集之间的比较可能是在各种环境中独立对整个数据集执行的其他操作的基石.一些系统的同步,完美操作可能依赖于这种比较被很好地定义和确定性地实现,而不管加数顺序和实现IEEE754的特定体系结构.

这个,或者只是好奇心.

在讨论中,Kahan求和算法已被提及为相关的.然而,该算法是最小化误差的合理尝试.它既不保证结果的正确符号,也不依赖于操作的顺序(至少保证一致的,如果错误的话,结果,对于集合的排列).

最明显的解决方案之一是采用/实现定点运算,使用足够的位来精确地表示每个可能的操作数值并保持精确的中间结果.

但是,这可以通过仅使用浮点运算来保证正确的结果符号.如果是这样,溢出问题(如上面的一个例子所示)需要在解决方案中解决,因为这个问题具有特定的技术方面.

(以下是原始问题.)

我有两组多个浮点(浮点或双精度)值.我想为这个问题提供一个完美的答案.由于浮点运算中的伪像,在某些极端情况下,根据操作的顺序,天真方法的结果可能是错误的.更不用说简单的总和会导致溢出.我不能为我提供任何努力,因为我所拥有的只是模糊的想法,所有这些都很复杂而且不具说服力.

一种可能的方法是使用超累积器计算总和:这是用于计算浮点数的精确和的算法.虽然这些想法已经存在了一段时间,但这个术语是一个相对较新的术语.

在某种意义上,您可以将其视为Kahan求和的扩展,其中序列和存储为值数组,而不仅仅是一对.然后,主要的挑战就是弄清楚如何在各种值之间分配精度.

一些相关的论文和代码:

YK Zhu和WB Hayes."算法908:浮点流的在线精确求和".ACM数学软件交易(ACM TOMS),37(3):37:1-37:13,2010年9月.doi:10.1145/1824801.1824815

不幸的是,论文和代码背后是付费专区,但这似乎是C++代码.

RM Neal,"使用小型和大型超级累积器的快速精确求和".2015. arXiv:1505.05571

C代码可用

MT Goodrich,A.Eldawy"用于求和浮点数的并行算法".2016. arXiv:1605.05436

这个和上面的Java代码