准确评估 1/1 + 1/2 + ... 1/n 行
我需要计算该行的总和：1/1+1/2+1/3+...+1/n。 考虑到 C++ 求值并不完全准确，求和的顺序起着重要作用。 1/n+1/(n-1)+...+1/2+1/1 表达式给出更准确的结果。 所以我需要找出求和的顺序，这可以提供最大的精度。 我什至不知道从哪里开始。 首选的实现语言是C++。 抱歉我的英语，如果有任何错误。
I need to evaluate the sum of the row: 1/1+1/2+1/3+...+1/n. Considering that in C++ evaluations are not complete accurate, the order of summation plays important role. 1/n+1/(n-1)+...+1/2+1/1 expression gives the more accurate result.
So I need to find out the order of summation, which provides the maximum accuracy.
I don't even know where to begin.
Preferred language of realization is C++.
Sorry for my English, if there are any mistakes.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
对于较大的 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))。
标准库可以快速准确地计算指数和对数。 使用乘法你应该得到更准确的结果。
如果这是你的作业，并且要求你使用简单的加法，你最好按照其他人的建议，从最小的一个到最大的一个进行加法。
For large n you'd better use asymptotic formulas, like the ones on http://en.wikipedia.org/wiki/Harmonic_number;
Another way is to use exp-log transformation. Basically:
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)).
Exponents and logarithms can be calculated pretty quickly and accuratelly by your standard library. Using multiplication you should get much more accurate results.
If this is your homework and you are required to use simple addition, you'll better add from the smallest one to the largest one, as others suggested.
我不确定求和的顺序是否起着重要作用，我以前没有听说过。 我猜你想在浮点算术中做到这一点，所以第一件事是考虑更多内联 (1.0/1.0 + 1.0/2.0+1.0/3.0) - 否则编译器将进行整数除法
来确定评估顺序，也许是for 循环还是括号？
例如
哦忘了说，编译器通常会有开关来确定浮点计算模式。 这可能与你所说的求和顺序有关 - 在 Visual C+ 中，这些可以在代码生成编译设置中找到，在 g++ 中，有选项 -float 可以
实际处理这个问题，另一个人是对的 - 你应该在最小分量在前的顺序； 所以
1/n + 1/(n-1) .. 1/1
这是因为浮点数的精度与小数位数相关，如果从 1 开始，相对于 1.0 将会有 23 位精度。 如果您从较小的数字开始，则精度是相对于较小的数字，因此您将获得相对于 1xe-200 或其他值的 23 位精度。 那么随着数字变大，会出现舍入误差，但总体误差会小于另一个方向
I'm not sure about the order of summation playing an important role, I havent heard that before. I guess you want to do this in floating point arithmetic so the first thing is to think more inline of (1.0/1.0 + 1.0/2.0+1.0/3.0) - otherwise the compiler will do integer division
to determine order of evaluation, maybe a for loop or brackets?
e.g.
oh forgot to say, compilers will normally have switches to determine floating point evaluation mode. this is maybe related to what you say on order of summation - in visual C+ these are found in code-generation compile settings, in g++ there're options -float that handle this
actually, the other guy is right - you should do summation in order of smallest component first; so
1/n + 1/(n-1) .. 1/1
this is because the precision of a floating point number is linked to the scale, if you start at 1 you'll have 23 bits of precision relative to 1.0. if you start at a smaller number the precision is relative to the smaller number, so you'll get 23 bits of precision relative to 1xe-200 or whatever. then as the number gets bigger rounding error will occur, but the overall error will be less than the other direction
缺乏准确性的原因是 float、double 和 long double 类型的精度。 他们只存储这么多的“小数”位。 因此，将一个非常小的值添加到一个大值中没有任何效果，小项在较大值中“丢失”。
您正在总结的系列有一个“长尾”，即小的术语加起来会产生很大的贡献。 但如果按降序求和，那么一段时间后，每个新的小项将不起作用（甚至在此之前，其大部分小数位将被丢弃）。 一旦达到这一点，您可以再添加十亿个术语，但如果一次只添加一个术语，仍然没有任何效果。
我认为按升序求和应该为此类系列提供最佳的准确性，尽管可能存在一些奇怪的极端情况，其中由于四舍五入到（1/2）次方而产生的错误可能恰好为某些问题提供了更接近的答案比其他人添加订单。 不过，您可能无法真正预测这一点。
The reason for the lack of accuracy is the precision of the float, double, and long double types. They only store so many "decimal" places. So adding a very small value to a large value has no effect, the small term is "lost" in the larger one.
The series you're summing has a "long tail", in the sense that the small terms should add up to a large contribution. But if you sum in descending order, then after a while each new small term will have no effect (even before that, most of its decimal places will be discarded). Once you get to that point you can add a billion more terms, and if you do them one at a time it still has no effect.
I think that summing in ascending order should give best accuracy for this kind of series, although it's possible there are some odd corner cases where errors due to rounding to powers of (1/2) might just so happen to give a closer answer for some addition orders than others. You probably can't really predict this, though.
此处：每个计算机科学家都应该了解浮点运算
Here: What Every Computer Scientist Should Know About Floating-Point Arithmetic
实际上，如果您要对大 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 相比，这几乎是微不足道的。）
Actually, if you're doing the summation for large N, adding in order from smallest to largest is not the best way -- you can still get into a situation where the numbers you're adding are too small relative to the sum to produce an accurate result.
Look at the problem this way: You have N summations, regardless of ordering, and you wish to have the least total error. Thus, you should be able to get the least total error by minimizing the error of each summation -- and you minimize the error in a summation by adding values as nearly close to each other as possible. I believe that following that chain of logic gives you a binary tree of partial sums:
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]and so on until you get to a single answer.
Of course, when N is not a power of two, you'll end up with leftovers at each stage, which you need to carry over into the summations at the next stage.
(The margins of StackOverflow are of course too small to include a proof that this is optimal. In part because I haven't taken the time to prove it. But it does work for any N, however large, as all of the additions are adding values of nearly identical magnitude. Well, all but log(N) of them in the worst not-power-of-2 case, and that's vanishingly small compared to N.)
http://en.wikipedia.org/wiki/Arbitrary- precision_arithmetic
您可以找到具有现成的 C/C++ 实现的库。
例如 http://www.apfloat.org/apfloat/
http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
You can find libraries with ready for use implementation for C/C++.
For example http://www.apfloat.org/apfloat/
除非您使用一些准确的封闭形式表示，否则从小到大的有序求和可能是最准确的简单解决方案（我不清楚为什么对数表达式会有所帮助 - 这是一个巧妙的技巧，但您不是据我所知，在这里可以赢得任何东西）。
您可以通过认识到一段时间后，总和将变得“量化”来进一步获得精度：实际上，当您有 2 位精度时，将 1.3 与 41 相加会得到 42，而不是 42.3 - 但是通过保持，您几乎可以实现精度加倍一个“错误”术语。 这称为 Kahan 求和。 您需要计算误差项 (42-41-1.3 == -0.3)，并在下一次加法中通过在下一项中添加 0.3 来更正该误差项，然后再再次添加它。
卡汉求和以及从小到大的排序可能会像您所需要的那样准确。 我严重怀疑你是否需要更好的调和级数 - 毕竟，即使经过 2^45 次迭代（疯狂的多次），你仍然只处理至少 1/2^45 大的数字，并且总和约为 45 (<2^6)，数量级差异为 51 的二的幂 - 即，如果您添加“错误”顺序，甚至仍然可以用双精度变量表示。
如果您从小到大并使用卡汉求和，那么在当今的处理器达到一定百分比的误差之前，太阳可能就会熄灭 - 并且您将首先由于该规模上的个别项误差而遇到其他棘手的精度问题无论如何（无论如何，2^53 或更大数量级的数字根本无法准确地表示为双精度数。）
Unless you use some accurate closed-form representation, a small-to-large ordered summation is likely to be most accurate simple solution (it's not clear to me why a log-exp would help - that's a neat trick, but you're not winning anything with it here, as far as I can tell).
You can further gain precision by realizing that after a while, the sum will become "quantized": Effectively, when you have 2 digits of precision, adding 1.3 to 41 results in 42, not 42.3 - but you achieve almost a precision doubling by maintaining an "error" term. This is called Kahan Summation. You'd compute the error term (42-41-1.3 == -0.3) and correct that in the next addition by adding 0.3 to the next term before you add it in again.
Kahan Summation in addition to a small-to-large ordering is liable to be as accurate as you'll ever need to get. I seriously doubt you'll ever need anything better for the harmonic series - after all, even after 2^45 iterations (crazy many) you'd still only be dealing with a numbers that are at least 1/2^45 large, and a sum that's on the order of 45 (<2^6), for an order of magnitude difference of 51 powers-of-two - i.e. even still representable in a double precision variable if you add in the "wrong" order.
If you go small-to-large, and use Kahan Summation, the sun's probably going to extinguish before today's processors reach a percent of error - and you'll run into other tricky accuracy issues just due to the individual term error on that scale first anyhow (being that a number of the order of 2^53 or larger cannot be represented accurately as a double at all anyhow.)
由于所有数字都是有理数，因此最简单的（也可能是最快的，因为它需要执行更少的浮点运算）是使用有理数（2 个整数 p,q 的元组）进行计算，然后只执行一个最后进行浮点除法。
更新 要有效地使用此技术，您将需要使用 bigint 来表示 p & q，因为它们增长得相当快...
Lisp 中的一个快速原型，内置有理数表明：
因此，下一个更好的选择可能是维护浮点列表并减少它，在每个步骤中将两个最小的数字相加...
As all your numbers are rationals, the easiest (and also maybe the fastest, as it will have to do less floating point operations) would be to do the computations with rationals (tuples of 2 integers p,q), and then do just one floating point division at the end.
update to use this technique effectively you will need to use bigints for p & q, as they grow quite fast...
A fast prototype in Lisp, that has built in rationals shows:
So, the next better option could be to mantain the list of floating points and to reduce it summing the two smallest numbers in each step...