Formulate BBP
The formula BBP (or Bailey-Borwein-Plouffe) makes it possible to calculate the énième decimal of π in Base 2 (or 16) without having to calculate the precedents of them, and by using very little memory and time. It was obtained the September 19th 1995 by Simon Plouffe in collaboration with David Bailey and Peter Borwein
The formula
Exploitation of the formula to calculate the decimals of π
The goal is to calculate to it digit of π in Base 16.Already, it is noticed that it (N+1) E decimal of π bases 16 of them is the same one as the 1st decimal of 16Nπ. Indeed, as in ten bases, to multiply a figure 16 by 16 base some makes it possible to shift the comma of a row towards the line. Thus by multiplying a number by 16N, the comma is shifted of NR row towards the line. It “is thus enough” to calculate the first digit of 16Nπ, equal by formula BBP to:
But to calculate the first figures behind the comma of this number is not so simple, for two reasons:
- # Initially, this number being very large, that requires to carry out calculations on very large numbers;
- #Ensuite, because this sum is infinite.
Let us pose . The calculation of the first digits of SN(a) will make it possible to obtain those of 16Nπ, by the relation:
Let us cut out the sum SN(a) of them two:
and let us calculate AN(a) and BN(a) independently.
Calculation of BN(a)
Although it is an infinite sum, this term is very simple to calculate, because it is noticed that its terms quickly become very small and only the first digits are sought.
-
Indeed, the first term of the sum is: . As one seeks to it decimal π (NR = 1.000.000 000 for example), the first bN term is much lower than 1.
- Moreover, each following term has one zero of more behind the comma that the precedent, because for K ≥ NR, bk > 16 bk+1:
Finally, the sum BN(a) is form (in the worst case):
Thus to obtain BN(a) with a precision of P figures behind the comma, it is enough to calculate P first terms of the sum, plus some following to avoid the problems of reserves which can possibly appear.
It is thus enough to calculate:
This sum being made up only of one small number of terms (of constant number), its computing time is negligible for a Ordinateur.
Calculation of AN(a)
The problem to calculate AN(a) is that the first terms are extremely large (NR figures bases of it 16 front the comma!). Nevertheless, as one seeks only the first figures behind the comma, it does not matter the whole part, as large as it is. One can thus of of “get rid” by using arithmetic Modulo.
All the difficulty is thus reduced of finding the part fractional of .
For that, one carries out the Euclidean Division of 16N-k by 8k+a:
Thus
is lower than 1, therefore it is the fractional part of .
And
It is thus enough to calculate: .
By using the fast method of Exponentiation, 16N-k is calculated quickly (execution time in O (log2 (N-k)).
Conclusion
With final, to obtain the first digits of π 16 (or 2 base some), it is necessary to calculate the first digits of:
with .
Complexity of this method
To calculate to it digit of π 16 base some (and thus the 4ne digit bases 2 of them):
Temporal complexity
- Bn' (A) is calculated in linear complexity (O (1))
- An' (A): by using the method of exponentiation fast, its terms are calculated in O (log2 (N)). Thus the sum of N terms, An' (A), is calculated in O (n*log2 (N)).
Thus Sn' (A) is calculated in O (1) + O (n*log2 (N))= O (n*log2 (N)). Thus finally, πn is calculated in 4* O (n*log2 (N))= O (n*log2 (N)).
From where a time of calculation proportional to n*log2 (N), is quasilinear.
Space complexity
Complexity memory use is constant: only successive sums on small numbers are carried out (a precision of ten decimals is necessary).
Derived formulas
Simon Plouffe
Original formula:
Viktor Adamchick and Stan Coach (1997)
Fabrice Bellard
Records
For comparison, the current record of calculation of all the decimals of π is of 1.241 billion decimals (either approximately 4.123 billion binary digits).- October 7th 1996 (Fabrice Bellard): 400 billionth digit bases 2 of them
- September 1997 (Fabrice Bellard): 1.000 billionth digit bases 2 of them
- February 1999 (Percival Hake): 40.000 billionth digit bases 2 of them
- 2001: 4.000.000 billionth digit bases 2 of them
And for the calculation of the decimals?
Currently, no really effective formula was discovered to calculate to it digit of π bases 10 of them. Simon Plouffe developed in December 1996, starting from a very old series of calculation of π based on the coefficients of the Binomial theorem, a method to calculate the figures bases 10 of them, but its complexity in O (n3*log2 (N)) made in practice unusable. Fabrice Bellard improved the algorithm well to reach a complexity in O (n2), but that is not sufficient to compete with the traditional methods of calculation of all the decimals.
Appendix: demonstration of formula BBP
Let us show already a general result:
- from where:
Let us apply this result to formula BBP:
One poses :
One breaks up into simple elements:
| Random links: | Jacques Desautels | Chandler gene | Rio Gravataí | Pilot (Misadventure, the last Master of the air) | Daniel Crevier | Manchester_du_nord,_Indiana |