c++ - 计算 pi 的位数

Question

我已经使用 GMP 库和 C++ 编写了 Gauss-Legendre 算法的实现代码来计算 pi 的位数。

它有正确的输出，但问题是我不知道输出在哪一点“变坏”，因为我必须在代码中指定精度。

这是使用 64 位精度的输出:3.141592653589793238*35*，最后两位数字不正确。

我的问题是，如果我想要 pi 的 n 位，b 的精度是多少，算法的迭代次数是多少 i 需要吗？

谢谢

Answer 1

Gauss-Legendre 算法(又名 AGM 算法)要求全程精确。

与牛顿法迭代不同，AGM 迭代不能 self 纠正。因此，您从一开始就需要完全精确。此外，您还需要额外的保护数字。

My question is, if I want n digits of pi, how many bits of precision b will be needed?

首先，您需要将 n(十进制)位转换为 b 二进制位。那将是:

        log(10)
b = n ---------- + epsilon
        log(2)

其中 epsilon 是保护数字的数量。您需要多少取决于实现和舍入行为，但通常 100 位对于任何 # 次迭代都绰绰有余。

至于你需要多少次迭代。这可以通过经验证据找到。

这是我编写的一个小应用程序的输出，该应用程序使用 Gauss-Legendre 算法将 Pi 计算到 1 亿位数字:

================================================================
Computing pi to 100000000 digits:
Threads: 8

Starting AGM...         1.394965 seconds
Starting Iteration 0...    -3 (error in decimal digits)
Starting Iteration 1...    -9
Starting Iteration 2...    -20
Starting Iteration 3...    -42
Starting Iteration 4...    -85
Starting Iteration 5...    -173
Starting Iteration 6...    -347
Starting Iteration 7...    -696
Starting Iteration 8...    -1395
Starting Iteration 9...    -2792
Starting Iteration 10...    -5586
Starting Iteration 11...    -11175
Starting Iteration 12...    -22352
Starting Iteration 13...    -44706
Starting Iteration 14...    -89414
Starting Iteration 15...    -178829
Starting Iteration 16...    -357661
Starting Iteration 17...    -715324
Starting Iteration 18...    -1430650
Starting Iteration 19...    -2861302
Starting Iteration 20...    -5722607
Starting Iteration 21...    -11445216
Starting Iteration 22...    -22890435
Starting Iteration 23...    -45780871
Starting Iteration 24...    -91561745
Starting Iteration 25...    -183123492
AGM:                    118.796792 seconds
Finishing...            3.033239   seconds
Radix Conversion...     2.924844   seconds

Total Wall Time:        126.151086 seconds

CPU Utilization:        495.871%
CPU Efficiency:         61.984%

Writing to "pi.txt"...  Done

因此，对于 1.83 亿个数字，25 次迭代就足够了。同样，每次迭代它都会加倍，因此您可以运行一些基本的对数数学运算来计算您需要多少次迭代。