logo标签列表

准确评估1/1 + 1/2 + ... 1/n这一级数

c++sumieee-754
7

我需要评估一行的总和：1/1+1/2+1/3+...+1/n。考虑到在C ++中，评估不是完全准确的，求和的顺序非常重要。表达式1/n+1/(n-1)+...+1/2+1/1可以提供更准确的结果。因此，我需要找出提供最大精度的求和顺序。我甚至不知道从哪里开始。实现的首选语言是C++。如果有任何错误，对不起。

1
你是在计算特定的n还是n趋近于无穷大。如果是后者，只需使用x = 2; :-) - paxdiablo
6
@Pax：这个级数的无穷和是无限大。 - Steve Jessop
还有一件事我忘了：如何计算总和的确切“准确”值？这也没有定义。 - Michael Pankov
3
@Pax: 不，这个总和是发散的，所以它必须是针对特定的n。你可能正在考虑的是1+1/2+1/4+...+1/n^2。 - erikkallen
啊，抱歉，我以为你想要的是1、2、4、8、...这个序列，而不是1、2、3、4、...。 - paxdiablo
哦，它被定义得非常好，可以通过调和数的定义或泰勒级数来表示。看看我的答案。 - liori
8个回答
14

对于较大的n值，最好使用渐进公式，例如 http://en.wikipedia.org/wiki/Harmonic_number 上的公式;

alt text

另一种方法是使用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)).

通过标准库，可以相当快速和准确地计算指数和对数。使用乘法可以获得更准确的结果。

如果这是你的作业并且需要使用简单的加法，你最好按其他人建议从小到大逐个相加。

这些解决方案比我的好得多，如果允许的话。 - Steve Jessop
啊伽马。一个我心中的常数！ - Mitch Wheat
这是一篇帖子里的两个答案。点赞是为了伽马含量公式。log(exp...) 的方法不会有所帮助，因为在累加多个值时也会出现丢失位数的问题。 - DarenW
5
缺乏准确性的原因是浮点数、双精度和长双精度类型的精度。它们只能存储有限的“小数”位数。所以将一个非常小的值加到一个大的值上没有效果，小项在大项中被“丢失”。
你正在求和的级数具有“长尾”，也就是说，小的项应该加起来对结果产生很大的贡献。但如果按降序求和，那么过一段时间后，每个新的小项都不会有影响（即使在此之前，它的大部分小数位数也会被舍弃）。一旦达到这个点，你可以再添加十亿个项，即使逐个相加，它仍然没有影响。
我认为按升序求和应该为这种类型的级数提供最佳的准确性，尽管可能存在某些奇怪的边角情况，在这些情况下，由于取整到(1/2)的幂而产生的误差可能刚好会给出比其他加法顺序更接近的答案。不过你可能无法真正预测这一点。
2
问题在于这个级数发散，因此即使按升序添加每个项，你也可能到达一个点，在那里逐个添加每个新项没有任何效果。 - Brooks Moses
5
2
直接链接到那篇文章中最相关的部分，特别是优化器和Kahan求和公式部分，会更有帮助：http://docs.sun.com/source/806-3568/ncg_goldberg.html#1070 - las3rjock
3
事实上，如果您正在为大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相比可以忽略不计。）
2
实际上我需要编写“我的程序”，因为这是某种教育任务。 - Michael Pankov
是的，但是你可以使用apfloats而不是低精度的double，从而获得所需的高精度。 - Ray
1

除非您使用一些准确的闭式表示，否则小到大的有序求和很可能是最准确的简单解决方案（我不清楚为什么对数指数会有帮助-那是一个巧妙的技巧，但据我所知，在这里你没有赢得任何东西）。

您可以通过意识到在一段时间后，总和将变得“量化”来进一步提高精度：实际上，当您具有2位数字精度时，将1.3加到41中的结果为42，而不是42.3-但通过保持“误差”项，您几乎可以将精度翻倍。这称为Kahan Summation。您将计算误差项（42-41-1.3 == -0.3），并通过在下一次添加之前将0.3添加到下一个术语中来进行更正。

在小到大排序中使用Kahan求和法，可能是你需要的最准确的方法。我真的怀疑你会需要更好的方法来处理谐波级数 - 毕竟，即使进行2^45次迭代（非常多），你仍然只需要处理至少为1/2^45的数字，并且总和大约为45（＜2^6），因此差异为51个二进制位 - 即使添加“错误”的顺序，仍然可以用双精度变量表示。

如果你按照从小到大的顺序，并使用Kahan求和法，今天的处理器在达到百分之一的误差之前，太阳可能已经熄灭了 - 而且由于该规模上的单个项误差，你将首先遇到其他棘手的精度问题（因为2^53或更大的数字根本无法准确地表示为双精度）。

请注意，如果您使用Kahan求和算法，可能需要小心优化设置，因为编译器可能会将其重写成无用的代码。 - Eamon Nerbonne
0

我不确定求和的顺序是否很重要，以前没有听说过。我猜你想在浮点运算中进行这个操作，所以首先要考虑更多类似于(1.0/1.0 + 1.0/2.0+1.0/3.0)的方式 - 否则编译器会执行整数除法。

要确定评估的顺序，也许可以使用for循环或括号？

例如：

float f = 0.0;
for (int i=n; i>0; --i) 
{
    f += 1.0/static_cast<float>(i);
}

哦，我忘了说，编译器通常有开关来确定浮点计算模式。这可能与您在求和顺序上所说的相关 - 在 Visual C + 中，它们可以在代码生成编译设置中找到，在 g++ 中则有处理此类情况的选项 -float。

实际上，其他人是正确的 - 您应该按最小分量的顺序进行求和;因此 1 / n + 1 / (n-1) .. 1/1

这是因为浮点数的精度与比例有关，如果从1开始，则相对于1.0，您将获得23位的精度。如果从较小的数字开始，精度会相对于较小的数字，因此您将获得相对于1xe-200或其他数字的23位精度。然后随着数字变大，将出现舍入误差，但总体误差将小于另一个方向。

使用浮点数运算，将1e-19加到1上并查看结果。 - Joey
是的，你想要将所有小数项相加，这样添加1的影响就不太可能把它们移出浮点数的尾数部分。 - paxdiablo
任务定义说明它扮演了一个角色。 在浮点数中，当然。我用数学方式写了这一行。 是的，我考虑过只使用简单的循环，但由于这样的排列组合数量庞大，看起来并不好。 - Michael Pankov
0
由于所有的数字都是有理数，最简单的方法（也可能是最快的方法，因为它需要进行较少的浮点运算）是使用有理数（由2个整数p、q组成的元组）进行计算，然后在最后进行一次浮点除法。
更新：为了有效地使用这种技术，您需要对p和q使用大整数，因为它们增长得非常快...
在Lisp中，内置有rationals的快速原型如下所示：
(defun sum_harmonic (n acc)
  (if (= n 0) acc (sum_harmonic (- n 1) (+ acc (/ 1 n)))))

(sum_harmonic 10 0)
7381/2520
[2.9289682]

(sum_harmonic 100 0)
14466636279520351160221518043104131447711/278881500918849908658135235741249214272
[5.1873775]

(sum_harmonic 1000 0)

53362913282294785045591045624042980409652472280384260097101349248456268889497101
75750609790198503569140908873155046809837844217211788500946430234432656602250210
02784256328520814055449412104425101426727702947747127089179639677796104532246924
26866468888281582071984897105110796873249319155529397017508931564519976085734473
01418328401172441228064907430770373668317005580029365923508858936023528585280816
0759574737836655413175508131522517/712886527466509305316638415571427292066835886
18858930404520019911543240875811114994764441519138715869117178170195752565129802
64067621009251465871004305131072686268143200196609974862745937188343705015434452
52373974529896314567498212823695623282379401106880926231770886197954079124775455
80493264757378299233527517967352480424636380511370343312147817468508784534856780
21888075373249921995672056932029099390891687487672697950931603520000
[7.485471]

因此，下一个更好的选择可能是维护浮点数列表，并在每个步骤中将两个最小的数字相加以减少它...

这可能有点棘手。我认为你需要将分母设为从1到n的所有数字的乘积，以便能够正确地进行加法运算。这意味着n！，它会很快超出32位int的范围。 - paxdiablo
1
你还没有尝试过吗？分母增长非常快，对于给定的n，它是n！。你需要使用一些BigInteger实现。 - liori
这是真的...我认为在过程中可能有共同的因子可以简化分数...我将尝试在内置分数的Lisp中实现它。 - fortran
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接