Solving Pi

[grayson at uiucuxc.Uiuc.ARPA]

	Here is the fastest way ever, and it is not a series.  It is called
the Gauss-Legendre method, and was discovered independently by Salamin and
Brent.  It is based on the arithmetic-geometric mean, which is:

agm(a,b):
	loop until a - b is very small
		amean = (a+b)/2; gmean = sqrt(a*b);
		a = amean; b = gmean;
	return a;


pi
	a = 1; b = 1/sqrt(2); t = 1/4; x = 1;
	loop until a - b is very small
		y = a; a = (a+b)/2; b = sqrt(b*y); t = t - x*(a-y)^2; x = 2*x;
	return pi = (a+b)^2 / (4*t);

With this method they've gotten 10000000 digits in 4 hours.


Sources:
	R. P. Brent, Multiple-precision zero-finding methods and the complexity
	  of elementary funciton evaluation, in "Analytic Computation
	  Complexity", ed. J. F. Traub, Academic Press 1976
	R. P. Brent, ACM Transactions on mathematical Software, Algorithm 524,
	  4 (1978) 57-70, 71-81.
	R. P. Brent, MP source code, in fortran on the CYBER.

from:

	uucp:	{ihnp4,pur-ee}!uiucdcs!uiucuxc!grayson
		Dan Grayson, Math Dept, Univ of Ill, Urbana 61801