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

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

have since been discovered that sum to other fundamental irrational constants. These are collectively known as BBP-type formulae. The original π summation is this:

\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). The amazing thing about this particular formula, is that if you rearrange this a little you can find an algorithm for extracting hexadecimal digits of π.

BBP algorithm

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

16^n

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

Do not forget that only the fractional part is accurate, so in order to extract the digit you wanted you must remove the integer part of the final sum and multiply by 16 to "skim off" the hexadecimal digit at this position (in theory the next few digits up to the accuracy of the calculations you 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.

<< Previous

Word Browser

Next >>

nidoran
fake (band)
tehillim
italo turkish war
sargeras
draenor
de casteljau's algorithm
hummel (artillery)
sumo (album)
warbucket
eight step rail

pixy stix
tom johnston (us musician)
jet age
francisco balagtas
julio machado
pont mousson
mara nsu ange
brum beat
nera
hombres g
john harington gubbins

counts and dukes of bar
henry, count of portugal
uss dale (dd 4)
carling academy birmingham
forgiven, not forgotten
richard dale
cursus
seth lover
talk on corners
toby spence
antoine, duke of brabant

rotation curve
charlie o'brien
buffalo gap
in blue
souterrain
augusta national golf club
large burgh
buhler
counterintuitive behavior of social systems
boxer mrav
borrowed heaven