From: HJSmith@ix.netcom.com (Harry Smith) Newsgroups: sci.math Subject: Re: Calculation of Pi Date: 2 Feb 1995 13:06:17 GMT In ciaro writes: > >Looking for algorithms to calc. PI. >Heard that Rumanajen's got it to 8 places with the 1st term. >Thanks! R > The following is from the file piw131.zip: ftp://oak.oakland.edu/SimTel/win3/math/piw131.zip SimTel/win3/math/ piw131.zip Computes Pi to a million or so decimal places These algorithms are documented in Scientific American, February 1988, Ramanujan and Pi, by Jonathan M. Borwein and Peter B. Borwein. Algorithm a: Let y[0] = SqRt(1/2), x[0] = 1/2 y[n] = (1 - SqRt(1 - y[n-1]^2)) / (1 + SqRt(1 - y[n-1]^2)) x[n] = ((1 + y[n])^2 * x[n-1]) - 2^n * y[n] Algorithm b: Let y[0] = SqRt(2) - 1, x[0] = 6 - 4 * SqRt(2) y[n] = (1 - SqRt(SqRt(1 - y[n-1]^4))) / (1 + SqRt(SqRt(1 - y[n-1]^4))) x[n] = ((1 + y[n])^4 * x[n-1]) - 2^(2n+1) * y[n] * (1 + y[n] + y[n]^2) For both algorithms, xn converges to 1/Pi. Algorithm a is quadratically convergent and algorithm b is quartically convergent. The following table shows how many iterations are needed to compute Pi to a given number of significant digits: Iterations Iterations Digits of algo. a of algo. b matching Pi ---------- ---------- ----------- 1 0 2 3 (1/x2 = 3.140, algo. a) 3 1 8 4 19 5 2 41 6 84 7 3 171 8 345 9 4 694 10 1392 11 5 2788 Algorithm b converges to a given number of digits about twice as fast as algorithm a, but takes about twice as much work per iteration. Using PiW, algorithm b is 10 to 20 percent faster than algorithm a. I used PiW to compute Pi to 500,000 decimal digits. This was done on an IBM AT compatible 33 MHz 486 DX computer using Windows 3.1 with 16 megabytes of RAM and 22 mega bytes of virtual memory. It took 37.3 hours for algorithm a and 31.0 hours for algorithm b. The results were the same. The divide and square root routines have been improved since these runs, so the program is a little faster now (10 to 20%). The distribution disk for PiW includes the executable file PiW.Exe, all the source code and this document. Read the READ-ME and the WHATFOR files for a complete description of what's on the disk. The first time I tried to compute Pi to more places than is normally needed I computed it to 50 decimal places using paper, pencil, and a hand calculator. The equation used was Pi = 16 * ArcTan(1/5) - 4 * ArcTan(1/239) ArcTan(1/x) = 1/x - 1/(3 * x^3) + 1/(5 * x^5) - ... This was done in the early 1970's. The equation was derived in 1706 by John Machin (1685-1751). After I got my Apple II+ computer in 1979, I computed Pi to 15,300 decimal places using Apple Pascal and the equation Pi = 48 * ArcTan(1/18) + 32 * ArcTan(1/57) - 20 * ArcTan(1/239) This is the same equation I used in 1989 to compute a 114,632 decimal place value using Borland Turbo Pascal on an IBM AT compatible computer. The equation is due to Carl Friedrich Gauss (1777-1855). In 1989, Pi was computed to 1,011,196,691 decimal digits. This was done by the Chudnovsky brothers (David and Gregory), Columbia University, using super computers. A year or so later the same two brothers computed Pi to a little over 2 billion (2 * 10^9) decimal digits. This time they used a parallel computer they built themselves in one of their apartments. They were written up in The New Yorker magazine. Its an interesting article, but I am not sure of the date (early 1991?). -- | Harry J. Smith | 19628 Via Monte Dr., Saratoga, CA 95070-4522, USA | Home Phone: 408 741-0406, Work Phone: 408 235-5088 (Voice Mail) | EMail: HJSmith@ix.netcom.com on the Internet via Netcom NetCruiser --