用计算机计算1+1/2+1/3+...1/100000怎么减少误差？

如何减少截断误差，让计算结果可以更加精确。

热心回应 · 2019-8-15 01:21:27

既然是面试题，我觉得面试老师的意图应该不是考察那些高精度数学库。评论中有几位提到从小到大算，这个方向应该比较符合出题者的意图，不过可以更进一步，不是从小到大算，而是每次拿出最小的两项做加法再把他们的和放回去，迭代地做，其实就是哈弗曼编码的那种合并次序，我简单写了下，发现结果和 @陈硕老师给出的gsl是一样的，至少前15位一样，顺便把从小到大的求值结果也算了出来：
哈夫曼序: 12.090146129863429
从小到大: 12.090146129863408
从大到小: 12.090146129863335

热心回应 · 2019-8-15 01:21:28

除了从小到大加之外，我看已经有人提到Kahan summation algorithm了。给一个链接：
https://en.wikipedia.org/wiki/Kahan_summation_algorithm

热心回应 · 2019-8-15 01:21:29

要精确，用 gmp 库。
要快，用 gsl 库

#include #include #include // M_EULER#include #include int main(int argc, char* argv[]){ mpq_class qsum; double dsum = 0; const int N = argc > 1 ? atoi(argv[1]) : 100; for (int i = 1; i = 1; --i) { dsum += 1.0 / i; } printf("reverse %.15f\n", dsum); printf(" naive %.15f\n", log(N) + M_EULER);}

复制代码

结果：

$ g++ harmonic.cc -lgmpxx -lgmp -lgsl -lgslcblas && ./a.out 100000 mpq 12.090146129863427 double 12.090146129863335 mpf 12.09014612986342794736321936350421950079369894178 gsl 12.090146129863429reverse 12.090146129863408 naive 12.090141129871762

复制代码

热心回应 · 2019-8-15 01:21:30

挑战一下自己，我们找任意数量的位数（任意精确度）。。。

感觉就这么简单。。。

随便要求前面多少位，内存也完全足以计算前面几百万位

当然有办法再优化，但是基本道理大概是这样的吧。用python是因为更容易描述过程吧。

（为何最后六位不准呢，因为这六位会被更下面的几个digit影响到，毕竟有十万个更小数要加在一起，容易影响到前面了。。。）

－－－

另外补充这个　1　+　1/2　+　1/3　+　1/4　....　＋　1/n 接近 log(n) + k。
k 是0.577...左右。
如果把 k 算得准，然后 n 很大，这样应该更快算出来。

热心回应 · 2019-8-15 01:21:31

不使用浮点数，自行构建分数类，完全避免掉精度损失。

用计算机计算1+1/2+1/3+...1/100000怎么减少误差？

5 个回复