我正在尝试(在 C 中)计算一个总和,例如
,
在哪里近似正态分布。因此,即使我使用 Log-Sum-Exp 技巧
,
和阶的指数。这意味着在求和过程中几乎每一项都消失了,因为只有正态分布的最右侧有贡献(只有大约个点!)。有什么聪明的方法来处理这样的金额吗?在此先感谢您的任何建议。
我正在尝试(在 C 中)计算一个总和,例如
,
在哪里近似正态分布。因此,即使我使用 Log-Sum-Exp 技巧
,
和阶的指数。这意味着在求和过程中几乎每一项都消失了,因为只有正态分布的最右侧有贡献(只有大约个点!)。有什么聪明的方法来处理这样的金额吗?在此先感谢您的任何建议。
您可以使用 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 位精度)。
在你的情况下,我会按降序(在数量上)对指数进行排序。然后我会继续添加,以防万一有最小条款的进位。