准确评估1/1 + 1/2 + ... 1/n行

Question

我需要评估行的总和:1/1 + 1/2 + 1/3 + ... + 1/n.考虑到在C++评估中并不完全准确,求和的顺序起着重要作用.1/n + 1 /(n-1)+ ... + 1/2 + 1/1表达式给出更准确的结果.所以我需要找出求和的顺序,它提供了最大的准确性.我甚至不知道从哪里开始.首选的实现语言是C++.对不起我的英文,如果有任何错误.

Answer 1

对于大n,你最好使用渐近公式,比如http://en.wikipedia.org/wiki/Harmonic_number上的公式;

另一种方法是使用exp-log转换.基本上:

H_n = 1 + 1/2 + 1/3 + ... + 1/n = log(exp(1 + 1/2 + 1/3 + ... + 1/n))= log(exp(1)*exp(1/2)*exp(1/3)*...*exp(1/n)).

标准库可以非常快速准确地计算指数和对数.使用乘法,您应该得到更准确的结果.

如果这是你的功课,你需要使用简单的添加,你最好从最小的一个添加到最大的一个,正如其他人建议的那样.

Answer 2

缺乏准确性的原因是float,double和long double类型的精度.他们只存储这么多"十进制"的地方.因此,将较小的值添加到较大的值不会产生任何影响,较小的术语会在较大的值中"丢失".

你总结的系列有一个"长尾",从某种意义上说,小的术语应该是一个很大的贡献.但是如果按降序求和,那么一段时间后每个新的小项都没有效果(甚至在此之前,它的大部分小数位将被丢弃).一旦你达到这一点,你可以增加十亿个术语,如果你一次一个,它仍然没有效果.

对于这类序列,我认为按升序求和应该给出最佳精度,尽管有可能存在一些奇怪的极端情况,其中由于舍入到(1/2)的幂而导致的错误可能恰好给出了一些更接近的答案.额外订单比其他人.不过,你可能无法真正预测到这一点.

Answer 3

我甚至不知道从哪里开始.

这里:每个计算机科学家应该知道的浮点运算

Answer 4

实际上，如果您要对大 N 进行求和，按从小到大的顺序相加并不是最好的方法 - 您仍然可能遇到这样的情况：相加的数字相对于总和来说太小而无法产生准确的结果。

这样看问题：无论顺序如何，您都有 N 次求和，并且您希望总误差最小。因此，您应该能够通过最小化每个求和的误差来获得最小的总误差，并且通过添加彼此尽可能接近的值来最小化求和中的误差。我相信遵循该逻辑链会给您一个部分和的二叉树：

Sum[0,i] = value[i]

Sum[1,i/2] = Sum[0,i] + Sum[0,i+1]

Sum[j+1,i/2] = Sum[j,i] + Sum[j,i+1]

依此类推，直到得到一个答案。

当然，当 N 不是 2 的幂时，您最终会在每个阶段得到剩余的内容，需要将其带入下一阶段的求和。

（StackOverflow 的边距当然太小，无法证明这是最优的。部分原因是我没有花时间来证明这一点。但它确实适用于任何 N，无论多大，因为所有添加都是添加几乎相同数量级的值。好吧，在最坏的非 2 的幂情况下，除了 log(N) 之外，所有这些都与 N 相比微乎其微。）