The Gauss–Legendre algorithm is an algorithm to compute the digits of \pi. It is notable for being rapidly convergent, with only 25 iterations producing 45 million correct digits of \pi.
It repeatedly replaces two numbers (a e b, say) by their arithmetic and geometric means,
\frac{{a + b}}{2}{\text{ e }}\sqrt {ab}
in order to find their arithmetic-geometric mean.
The algorithm is quite simple, and is described here. Below you can find a Python code for implementing the algorithm, making use of the decimal module:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #!/usr/bin/env pythonfrom __future__ import with_statementimport decimaldef pi_gauss_legendre(): D = decimal.Decimal with decimal.localcontext() as ctx: ctx.prec += 2 a, b, t, p = 1, 1/D(2).sqrt(), 1/D(4), 1 pi = None while 1: an = (a + b) / 2 b = (a * b).sqrt() t -= p * (a - an) * (a - an) a, p = an, 2*p piold = pi pi = (a + b) * (a + b) / (4 * t) if pi == piold: # equal within given precision break return +pidecimal.getcontext().prec = 4500print (pi_gauss_legendre()) |
This is a screen of output:
checksum: 38957cccdef0229b17dfce1dfb41c983f71f59d88a0e338d8718d21943258cae965609e9d16032c9fa87a0271e120d2c465784b7048fa0c9cd7dfecbe94e7680