Calculating the digits of pi

Question

I've used the GMP library and C++ to code an implementation of the Gauss-Legendre algorithm to calculate the digits of pi.

It has correct output, but the problem is I don't know at which point the output "turns bad", since I have to specify the precision in the code.

Here is the output using 64-bit precision: 3.141592653589793238*35*, the last two digits being incorrect.

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

Thank You

Answer 1

The Gauss-Legendre algorithm (aka the AGM algorithm) requires full precision all the way through.

Unlike Newton's Method iterations, AGM iterations aren't self-correcting. So you need full precision from the start. Furthermore, you need extra guard digits.

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

First you need to convert the n (decimal) digits into b binary bits. So that would be:

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

Where epsilon is the number of guard digits. How much you need depends on the implementation and rounding behavior, but typically 100 bits is more than enough for any # of iterations.

As for how many iterations you need. This can be found by empirical evidence.

Here's the output of a small app I wrote that compute Pi to 100 million digits using the Gauss-Legendre algorithm:

================================================================
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.