Bailey-Borwein-Plouffe formula

From Wikipedia, the free encyclopedia

In mathematics, the Bailey-Borwein-Plouffe formula (BBP formula) is a π summation formula discovered in 1995 by Simon Plouffe. The formula is named after David H. Bailey, Peter Borwein, and Plouffe. A great many formulae that sum to other fundamental irrational constants have since been discovered. They are of the form

\alpha = \sum_{k = 0}^{\infty} \frac{p(k)}{b^kq(k)}

where p and q are polynomials in integer coefficients. Formulae in this form are known as BBP-type formulae [1].

The original π summation is

\pi = \sum_{k = 0}^{\infty} \frac{1}{16^k} \left( \frac{4}{8k + 1} - \frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6}\right).

[edit] BBP algorithm

The formula yields an algorithm for extracting hexadecimal digits of π. In order to perform digit extraction first we must rewrite the formula as

\pi = 4 \sum_{k = 0}^{\infty} \frac{1}{(16^k)(8k+1)} - 2 \sum_{k = 0}^{\infty} \frac{1}{(16^k)(8k+4)} - \sum_{k = 0}^{\infty} \frac{1}{(16^k)(8k+5)} - \sum_{k = 0}^{\infty} \frac{1}{(16^k)(8k+6)}.

Now we would like to find hexadecimal digit n of π, so, taking the first sum we split the sum to infinity across the nth term

\sum_{k = 0}^{\infty} \frac{1}{(16^k)(8k+1)} = \sum_{k = 0}^{n} \frac{1}{(16^k)(8k+1)} + \sum_{k = n + 1}^{\infty} \frac{1}{(16^k)(8k+1)}.

We now multiply by 16n so that the hexadecimal point (the divide between fractional and integer parts of the number) is in the right place.

\sum_{k = 0}^{\infty} \frac{16^{n-k}}{8k+1} = \sum_{k = 0}^{n} \frac{16^{n-k}}{8k+1} + \sum_{k = n + 1}^{\infty} \frac{16^{n-k}}{8k+1}.

Since we only care about the fractional part of the sum, we look at our two terms and realise that only the first sum is able to produce whole numbers whereas the second sum cannot produce whole numbers since the numerator can never be larger than the denominator for k > n. Therefore we need a trick to remove the whole numbers for the first sum. That trick is \mod 8k+1. Our sum for the first fractional part then becomes:

\sum_{k = 0}^{n} \frac{16^{n-k} \mod 8k+1}{8k+1} + \sum_{k = n + 1}^{\infty} \frac{16^{n-k}}{8k+1}.

Notice how the modulo operator always guarantees that only the fractional sum will be kept. To calculate 16^{n-k}\mod 8k+1 quickly and efficiently, use the binary exponentiation algorithm. When the running product becomes greater than one, take the modulo just as you do for the running total in each sum.

Now to complete the calculation you must apply this to each of the four sums in turn. Once this is done, taking the four summations and put them back into the sum to π.

4 \Sigma_1 - 2 \Sigma_2 - \Sigma_3 - \Sigma_4. \,\!

Since only the fractional part is accurate, extracting the wanted digit requires that one removes the integer part of the final sum and multiplies by 16 to "skim off" the hexadecimal digit at this position (in theory the next few digits up to the accuracy of the calculations used would also be accurate).

[edit] Advantages of the BBP algorithm

This algorithm can be used on computers without creating custom data types with thousands or even millions of digits in order to try to compute π. Because of the method to remove the first n − 1 digits to get at the nth digit, computers with only small, but efficient, data types can be used. This increase in speed caused by using smaller data types makes the algorithm the fastest way to compute the nth digit (or a few digits in a neighborhood of the nth). Previous π-computing algorithms using the large data types remain faster when the goal is to compute all the digits from 1 to n.

[edit] External links

Retrieved from "http://en.wikipedia.org../../../b/a/i/Bailey-Borwein-Plouffe_formula_b0ef.html"
In other languages