Geek Answers Handbook

Calculation of digits pi

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

He has the correct output, but the problem is that I don’t know at what point the output “gets bad”, since I have to indicate the accuracy in the code.

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

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

thanks

+4
source share
1 answer

The Gauss-Legendre algorithm (also the AGM algorithm) requires complete accuracy throughout.

Unlike Newton method iterations, AGM iterations are not self-correcting. Therefore, you need complete accuracy from the start. In addition, you need additional protective numbers.

My question is: if I want n digits pi, how many precision bits of b will it take?

First you need to convert the digits n (decimal) to binary bits b . So this will be:

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

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

How and how many iterations you need. This can be found from empirical evidence.

Here's the output of a small application, I wrote that Pi calculates up 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

Thus, 25 iterations are enough for 183 million digits. Similarly, it doubles with each iteration, so you can run some basic logarithm math to figure out how many iterations you need.

+10
source

More articles:


All Articles