Daily Archives: 3/3/2007

Pi, 10m digits, 3m11s, 20 minutes to program…

PiWhile playing around with the GNU Bignum library and Mersenne primes, I decided to code up a simple program to compute pi to an obscene number of decimal places (I chose 10 million, a much larger number than any of my previous efforts). The GNU Bignum Library supports arbitrary precision floating point arithmetic as well, which made the Brent-Salamin (also called the Gauss-Legendre algorithm or the AGM algorithm) to compute pi. It’s very simple, and has quadratic convergence, which means that only 22 iterations are sufficient to generate 10m digits of accuracy. The resulting program worked the very first time I ran it. It takes 3m 11s or so on my AMD64 box, which makes it much, much faster than any other program I’ve written to date. (It still pales to the gmp-chudnovsky program (which I used to check my generated digits) but it’s not bad for 20 minutes of work and a lazy 73 lines of code. The GMPLIB is quite a nice piece of work.

Gauss-Legendre algorithm – Wikipedia, the free encyclopedia

And here’s my source code:

Barely commented, but consider the above link the comments.

Technorati Tags: , ,