Calculating Pi - Brent-Salamin Algorithm

Date: 05/11/2000 at 11:47:24
From: Bill Smith
Subject: Pi

What are some methods for finding pi?

Date: 05/11/2000 at 13:40:44
From: Doctor Rob
Subject: Re: Pi

Thanks for writing to Ask Dr. Math, Bill.

Start at the following frequently asked questions (FAQ) page on pi 
from Ask Dr. Math:

   http://mathforum.org/dr.math/faq/faq.pi.html   

Then look at the links near the bottom of the page entitled, "Pi on 
the Web." Some of those should help. I particularly like "Pi through 
the ages."

As a follow-up, here is something you may find interesting. Probably 
the easiest way to get digits of Pi is this.

Start with a = 1, b = sqrt(2)/2, r = 1, and s = 1/2. Use as much 
precision in calculation as you want in the answer. Then do these 
steps:

     1.  A = (a+b)/2

     2.  B = sqrt(a*b)

     3.  C = (A-b)^2

     4.  R = 2*r

     5.  S = s - C*R

     6.  P = 2*A^2/S

     7.  If C = 0 to the precision used, stop, and the answer is
         Pi = P to that precision.

     8.  Replace a by A, b by B, r by R, and s by S

     9.  Go back to step 1.

This is called the Brent-Salamin Algorithm. Each calculation is pretty 
simple, and after just a few rounds it gives answers accurate to many 
decimal places. (Five rounds will give 42 decimal digits, if you use 
that much precision.) Explaining *why* this works is very hard. Please 
accept that it does.

If we make our precision eight decimal places, the first few steps go 
like this:

     a = 1
     b = 0.70710678
     r = 0
     s = 1/2
     A = 0.85355339
     B = 0.84089642
     C = 0.02144661
     S = 0.45710678
     R = 2
     P = 3.18767264
     C is not small enough,

     A = 0.84722490
     B = 0.84720127
     C = 0.00004005
     S = 0.45694658
     R = 3
     P = 3.14168029
     C is not small enough,

     A = 0.84721308
     B = 0.84721308
     C = 0.00000000
     S = 0.45694658
     R = 4
     P = 3.14159265
     C is small enough.

Then the answer is pi = 3.14159265, to eight decimal places.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/