From: tony@mantis.co.uk (Tony Lezard)
Newsgroups: sci.math
Subject: Re: pi algorithm on a PC
Date: 22 Feb 91 18:42:19 GMT

hemphill@betwixt.cs.caltech.edu (Scott Hemphill) writes:

> I have a million digits of pi on-line in printable form (and then compressed)
> You never know when you might need it.  :-)

I know >100 digits of pi and I can vouch that it has been useful occasionally
for such things as testing the output of pi computing programs. (I remember
it also being useful for one or two other things, but I forget what they
were.)

To stop the debate about what the digits are around the 20th place, I certify
the following 100 d.p. as CORRECT:

        3.1415926535 8979323846 2643383279 5028841971 6939937510
          5820974944 5923078164 0628620899 8628034825 3421170679

If using this as an approximation for pi, change the trailing 79 to 80 since
the next digit is an 8. :-)/2

In all this discussion, the original problem of getting a PC to generate an
arbitary number of digits has fallen by the wayside a bit. To rectify this,
I present a speedy algorithm that doesn't involve arctans:

Set a = x = 1, b = 1/sqrt(2), c = 1/4.

Then iterate this lot as many times as you like:

    .--> y := a
    |    a := (a + b) / 2
    |    b := sqrt(b*y)
    |    c := c - x * (a - y)^2
    |    x := 2 * x
    |    Loop back to here
    |      |
    `------/

When you get to the bit that invites you to loop back, the expression
(a + b)^2/(4*c) will contain the curernt approximation to pi.

This converges quadratically - ie, every time you go round the loop, the
number of decimal places doubles. The algorithm was used in Yoshiaki
Tamura and Tasumasa Kanada's computation of 16,777,216 digits. There are
probably even slicker algorithms by now.

--
Tony Lezard.  E-mail: tony@mantis.co.uk, Snail: Mantis Consultants,
Unit 56, St. John's Innovation Centre, Cambridge, CB4 4WS, United Kingdom.
Voice: +44 223 421094.  Most appropriate anagram of name: Lazy Rodent.