HOME

TheInfoList



OR:

The Bailey–Borwein–Plouffe formula (BBP formula) is a formula for . It was discovered in 1995 by Simon Plouffe and is named after the authors of the article in which it was published, David H. Bailey, Peter Borwein, and Plouffe. Before that, it had been published by Plouffe on his own site. The formula is : \pi = \sum_^\left frac \left(\frac-\frac-\frac-\frac\right)\right/math> The BBP formula gives rise to a spigot algorithm for computing the ''n''th base-16 (hexadecimal) digit of (and therefore also the ''4n''th
binary digit Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two digits (0 and 1) * Binary function, a function that takes two arguments * Binary operation, a mathematical operation that ta ...
of ) without computing the preceding digits. This does ''not'' compute the ''n''th decimal of (i.e., in base 10). But another formula discovered by Plouffe in 2022 allows extracting the ''n''th digit of in decimal. BBP and BBP-inspired algorithms have been used in projects such as PiHex for calculating many digits of using distributed computing. The existence of this formula came as a surprise. It had been widely believed that computing the ''n''th digit of is just as hard as computing the first ''n'' digits. Since its discovery, formulas of the general form : \alpha = \sum_^\infty \left \frac \frac \right/math> have been discovered for many other irrational numbers \alpha, where p(k) and q(k) are
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An ex ...
s with integer coefficients and b \geq 2 is an integer base. Formulas of this form are known as BBP-type formulas. Given a number \alpha, there is no known systematic algorithm for finding appropriate p(k), q(k), and b; such formulas are discovered
experimentally An experiment is a procedure carried out to support or refute a hypothesis, or determine the efficacy or likelihood of something previously untried. Experiments provide insight into cause-and-effect by demonstrating what outcome occurs when ...
.


Specializations

A specialization of the general formula that has produced many results is : P(s, b, m, A) = \sum_^\left frac \sum_^m \frac \right where ''s'', ''b'', and ''m'' are integers, and A = (a_1, a_2, \dots, a_m) is a
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
of integers. The ''P'' function leads to a compact notation for some solutions. For example, the original BBP formula : \pi = \sum_^\left frac \left(\frac-\frac-\frac-\frac\right)\right/math> can be written as : \pi = P\bigl(1, 16, 8, (4, 0, 0, -2, -1, -1, 0, 0) \bigr).


Previously known BBP-type formulae

Some of the simplest formulae of this type that were well known before BBP and for which the ''P'' function leads to a compact notation, are: : \begin \ln\frac &= \frac + \frac + \frac + \frac + \frac + \cdots \\ &= \sum_^\infty \frac = \frac \sum_^\infty \left \frac \left( \frac \right) \right\\ &= \frac P\bigl(1, 10, 1, (1) \bigr), \end : \begin \ln 2 &= \frac + \frac + \frac + \frac + \frac + \cdots \\ &= \sum_^\infty \frac = \frac \sum_^\infty \left \frac \left( \frac \right) \right\\ &= \frac P\bigl( 1, 2, 1, (1) \bigr). \end (In fact, this identity holds true for ''a'' > 1: :\ln\frac = \sum_^\infty \frac.) Plouffe was also inspired by the arctan power series of the form (the ''P'' notation can be also generalized to the case where ''b'' is not an integer): : \begin \arctan\frac &= \frac - \frac + \frac - \frac + \frac + \cdots \\ &= \sum_^\infty \left \frac \frac \right = \frac \sum_^\infty \left \frac \left( \frac + \frac \right) \right\\ &= \frac P\left( 1, b^4, 4, \left(1, 0, -b^, 0\right) \right). \end


The search for new equalities

Using the ''P'' function mentioned above, the simplest known formula for is for ''s'' = 1, but ''m'' > 1. Many now-discovered formulae are known for ''b'' as an exponent of 2 or 3 and ''m'' as an exponent of 2 or it some other factor-rich value, but where several of the terms of sequence ''A'' are zero. The discovery of these formulae involves a computer search for such linear combinations after computing the individual sums. The search procedure consists of choosing a range of parameter values for ''s'', ''b'', and ''m'', evaluating the sums out to many digits, and then using an integer relation-finding algorithm (typically Helaman Ferguson's
PSLQ algorithm An integer relation between a set of real numbers ''x''1, ''x''2, ..., ''x'n'' is a set of integers ''a''1, ''a''2, ..., ''a'n'', not all 0, such that :a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0.\, An integer relation algorithm is an algorithm fo ...
) to find a sequence ''A'' that adds up those intermediate sums to a well-known constant or perhaps to zero.


The BBP formula for

The original BBP summation formula was found in 1995 by Plouffe using PSLQ. It is also representable using the ''P'' function above: : \begin \pi &= \sum_^\infty \left \frac \left( \frac - \frac - \frac - \frac \right) \right\\ &= P\bigl( 1, 16, 8, (4, 0, 0, -2, -1, -1, 0, 0) \bigr), \end which also reduces to this equivalent ratio of two polynomials: : \pi = \sum_^\infty \left \frac \left( \frac \right) \right This formula has been shown through a fairly simple proof to equal .


BBP digit-extraction algorithm for

We would like to define a formula that returns the ''n''th
hexadecimal In mathematics and computing, the hexadecimal (also base-16 or simply hex) numeral system is a positional numeral system that represents numbers using a radix (base) of 16. Unlike the decimal system representing numbers using 10 symbols, h ...
digit of . A few manipulations are required to implement a spigot algorithm using this formula. We must first rewrite the formula as : \pi = 4 \sum_^\infty \frac - 2 \sum_^\infty \frac - \sum_^\infty \frac - \sum_^\infty \frac. Now, for a particular value of ''n'' and taking the first sum, we split the
sum Sum most commonly means the total of two or more numbers added together; see addition. Sum can also refer to: Mathematics * Sum (category theory), the generic concept of summation in mathematics * Sum, the result of summation, the additio ...
to
infinity Infinity is that which is boundless, endless, or larger than any natural number. It is often denoted by the infinity symbol . Since the time of the ancient Greeks, the philosophical nature of infinity was the subject of many discussions am ...
across the ''n''th term: : \sum_^\infty \frac = \sum_^n \frac + \sum_^\infty \frac. We now multiply by 16''n'', so that the hexadecimal point (the divide between fractional and integer parts of the number) is in the ''n''th place: : \sum_^\infty \frac = \sum_^n \frac + \sum_^\infty \frac. 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; conversely, 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 to reduce modulo  8''k'' + 1. Our sum for the first fractional part then becomes : \sum_^n \frac + \sum_^\infty \frac. Notice how the modulus operator always guarantees that only the fractional sum will be kept. To calculate 16''n''−''k'' mod (8''k'' + 1) quickly and efficiently, the modular exponentiation algorithm is used. When the running product becomes greater than one, the modulus is taken, just as for the running total in each sum. Now to complete the calculation, this must be applied to each of the four sums in turn. Once this is done, the four summations are put 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). This process is similar to performing
long multiplication A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Efficient multiplication algorithms have existed since the advent of the d ...
, but only having to perform the summation of some middle columns. While there are some carries that are not counted, computers usually perform arithmetic for many bits (32 or 64) and round, and we are only interested in the most significant digit(s). There is a possibility that a particular computation will be akin to failing to add a small number (e.g. 1) to the number 999999999999999, and that the error will propagate to the most significant digit.


BBP compared to other methods of computing

This algorithm computes without requiring custom data types having thousands or even millions of digits. The method calculates the ''n''th digit ''without'' calculating the first ''n'' − 1 digits and can use small, efficient data types. Though the BBP formula can directly calculate the value of any given digit of with less computational effort than formulas that must calculate all intervening digits, BBP remains
linearithmic In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
(O(n \log n)), whereby successively larger values of ''n'' require increasingly more time to calculate; that is, the "further out" a digit is, the longer it takes BBP to calculate it, just like the standard -computing algorithms.


Generalizations

D. J. Broadhurst provides a generalization of the BBP algorithm that may be used to compute a number of other constants in nearly linear time and logarithmic space.D. J. Broadhurst
"Polylogarithmic ladders, hypergeometric series and the ten millionth digits of ζ(3) and ζ(5)"
(1998) ''arXiv'' math.CA/9803067
Explicit results are given for
Catalan's constant In mathematics, Catalan's constant , is defined by : G = \beta(2) = \sum_^ \frac = \frac - \frac + \frac - \frac + \frac - \cdots, where is the Dirichlet beta function. Its numerical value is approximately : It is not known whether is irra ...
, \pi^3, \pi^4,
Apéry's constant In mathematics, Apéry's constant is the sum of the reciprocals of the positive cubes. That is, it is defined as the number : \begin \zeta(3) &= \sum_^\infty \frac \\ &= \lim_ \left(\frac + \frac + \cdots + \frac\right), \end ...
\zeta(3), \zeta(5), (where \zeta(x) is the Riemann zeta function), \log^32, \log^42, \log^52, and various products of powers of \pi and \log2. These results are obtained primarily by the use of polylogarithm ladders.


See also

* Approximations of * Experimental mathematics *
Bellard's formula Bellard's formula is used to calculate the ''n''th digit of π in base 16. Bellard's formula was discovered by Fabrice Bellard in 1997. It is about 43% faster than the Bailey–Borwein–Plouffe formula (discovered in 1995). It has been used in P ...


References


Further reading

* D. J. Broadhurst
"Polylogarithmic ladders, hypergeometric series and the ten millionth digits of ζ(3) and ζ(5)"
(1998) ''
arXiv arXiv (pronounced " archive"—the X represents the Greek letter chi ⟨χ⟩) is an open-access repository of electronic preprints and postprints (known as e-prints) approved for posting after moderation, but not peer review. It consists o ...
'' math.CA/9803067


External links

* Richard J. Lipton,
Making An Algorithm An Algorithm — BBP
, weblog post, July 14, 2010. * Richard J. Lipton,
Cook’s Class Contains Pi
, weblog post, March 15, 2009. * * David H. Bailey,
BBP Code Directory
, web page with links to Bailey's code implementing the BBP algorithm, September 8, 2006. {{DEFAULTSORT:Bailey-Borwein-Plouffe formula Pi algorithms Experimental mathematics