Just a note to self, so I don't lose some of these sites I've found.
I've been looking at algorithms to calculate π (pi) recently. I've not actually installed and learned anything like GMP, MAPM, MPFR, or other so-called "bignum" libraries, so I'm pretty much limited to the digits that can be stored in a double. *sniff* Well, I'll get around to it eventually, eh?
So, the major algorithms I've found are as follows:
- Archimedes' iterative algorithm for approximating Pi This algorithm starts off with a circle inscribed in a square, and a square inscribed in that circle. The perimeters of the squares quite obviously set upper and lower bounds for the diameter of the circle, and the diagonal of the inner square equals the diameter of the circle; so upper and lower bounds for π (pi) can be calculated. Given relationships between regular polygons, each n-gon (starting with the square, or 4-gon) can yield a 2n-gon, ad infinitum. The only limitation is the precision with which you can store numbers, in particular the square root of two (as your initial calculation of the diameter, given a 1×1 inscribed square).
- The Bailey, Borwein, and Plouffe (BPP) formula
- Series expansions and Fibonacci numbers
- Pi and the Fibonacci Numbers (Talks about several series-expansion algorithms such as arctangent, Gregory's series, and Machin's formula.)
I've implemented Aristotle's algorithm and Gregory's series, and filled a double with accurate values for π (pi) fairly quickly. Actually, the expansion of Gregory's series rand several orders of magnitude faster. I suppose now I should install GMP and play with actual numbers instead of these piddly little doubles.
See also: History of numerical approximations of pi on Wikipedia

