对非常小的指数求和:下溢

计算科学 C 统计数据 浮点
2021-12-03 11:25:43

我正在尝试(在 C 中)计算一个总和,例如

S=iexp(ai),

在哪里104<ai<105近似正态分布。因此,即使我使用 Log-Sum-Exp 技巧

S=exp(log[iexp(ai+K)]K),

K=mini(ai)阶的指数这意味着在求和过程中几乎每一项都消失了,因为只有正态分布的最右侧有贡献(只有大约个点!)。有什么聪明的方法来处理这样的金额吗?在此先感谢您的任何建议。1053106

2个回答

您可以使用 Kahan 求和算法 [1] 的想法是重新安排求和运算,从而限制精度损失。代码非常简单(转载自下面的[1])。如果这还不够,您可以使用多精度表示,例如四倍双精度 [2]。它们受到多种语言/编译器(包括 GNU c)的支持。最后,如果这还不够,您可以使用基于扩展的多精度算术 [3]。我用 C++ 类编写了一个实现,它可以像数字 [4] 一样使用。现在,如果下溢发生在单个术语中(即,如果 exp() 下溢),那么您可能需要使用具有更多位数的浮点表示。例如,您可以使用 MPFR [5]。它具有任意精度的所有经典运算符和函数的实现(非常好的库,

function KahanSum(input)
    var sum = 0.0
    var y,t                      // Temporary values.
    var c = 0.0                  // A running compensation for lost low-order bits.
    for i = 1 to input.length do
        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 overly-aggressive optimizing compilers!
    next i                       // Next time around, the lost low part will be added to y in a fresh attempt.
    return sum

[1] https://en.wikipedia.org/wiki/Kahan_summation_algorithm

[2] https://en.wikipedia.org/wiki/Quadruple-precision_floating-point_format

[3] J. Shewchuk,自适应精度浮点算术和快速鲁棒几何谓词、离散和计算几何(影响因子:0.69)。07/1996;18(3)。DOI: 10.1007/PL00009321

[4] https://gforge.inria.fr/frs/?group_id=5833 , MultiPrecision_psm

[5] MPFR:http ://www.mpfr.org/

您正在添加正项,因此您不必担心最终结果的不精确性,就像您有负项一样: (10^100+5)-(10^100+3)=2 but (10^100 +5)+(10^100+3)=2*10^100 (只要您不需要 100 位精度)。

在你的情况下,我会按降序(在数量上)对指数进行排序。然后我会继续添加,以防万一有最小条款的进位。