我使用 GMP 库和 C++ 编写了 Gauss-Legendre 算法的实现来计算 pi 的位数。
它有正确的输出，但问题是我不知道输出在什么时候“变坏”，因为我必须在代码中指定精度。
这是使用 64 位精度的输出：3.141592653589793238* 35 *，最后两位数不正确。
我的问题是，如果我想要n位的 pi，需要多少位精度b以及算法i需要多少次迭代？
谢谢你
问问题
2449 次
1 回答
10
Gauss-Legendre 算法（又名 AGM 算法）需要全程精确。
与牛顿法迭代不同，AGM 迭代不是自校正的。因此，您从一开始就需要完全精确。此外，您需要额外的保护数字。
我的问题是，如果我想要
npi 的数字，需要多少位精度b？
首先，您需要将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
So 25 iterations is sufficient for 183 million digits. Likewise, it doubles with each iteration, so you can run some basic logarithm math to figure out how many iterations you need.
于 2013-01-04T18:29:41.973 回答