Bailey-Borwein-Plouffe formula

In mathematics, the Bailey-Borwein-Plouffe formula (BBP formula) originally referred to the π summation formula discovered in 1995 by Simon Plouffe. A great many other formula of the form

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

have since been discovered that sum to other fundamental irrational constants. These are collectively known as BBP-type formulae [1] (http://mathworld.wolfram.com/BBP-TypeFormula.html).

The original π summation is this:

<math>\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).<math>

The amazing thing about this particular formula is that rearranging it a little gives an algorithm for extracting hexadecimal digits of π.

BBP algorithm

In order to perform digit extraction first we must rewrite the formula as

<math>\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)}. <math>

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

<math>\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)}.<math>

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

<math>\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}.<math>

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 <math>\mod 8k+1<math>. Our sum for the first fractional part then becomes:

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

Notice how the modulo operator always guarantees that only the fractional sum will be kept.

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

<math>4 \Sigma_1 - 2 \Sigma_2 - \Sigma_3 - \Sigma_4. <math>

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

Advantages of the BBP algorithm

This means that 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, only computers with small, but efficient data types need 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.de:Bailey-Borwein-Plouffe-Formel