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
--