Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: Notesfiles $Revision: 1.7.0.7 $; site uiucuxc
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxn!ihnp4!inuxc!pur-ee!uiucdcs!uiucuxc!grayson
From: grayson@uiucuxc.Uiuc.ARPA
Newsgroups: net.sources
Subject: Re: Solving Pi
Message-ID: <12500018@uiucuxc>
Date: Thu, 1-Aug-85 21:21:00 EDT
Article-I.D.: uiucuxc.12500018
Posted: Thu Aug  1 21:21:00 1985
Date-Received: Sun, 4-Aug-85 08:04:44 EDT
References: <187@ski.UUCP>
Lines: 33
Nf-ID: #R:ski.UUCP:-18700:uiucuxc:12500018:000:1015
Nf-From: uiucuxc.Uiuc.ARPA!grayson    Aug  1 20:21:00 1985


	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