www.pi314.net


History
Mathematicians
All formulas
Num. approx.
Softwares
Misc. math.
Digits
Poetry
Papers/videos
Delirium !
 Pi-Day
Images
Music
Links
Bibliography



Boris Gourévitch
The world of Pi - V2.57
modif. 13/04/2013



Pi-Day in
Pi Day Countdown
Google
Home Version history Guestbook Who I am Some pictures (fr) Acknowledgements Last modifications Contact

Cette page en français This page in English


pict

Simon Plouffe

Finding the N  th digit of a number a without needing to know the previous one thanks to the BBP formula



1 The BBP formula

Little reminder: On the 19 septembre 1995 at 0h29 (!), after month on research in the dark, Simon Plouffe, David Bailey and Peter Borwein de Vancouver discover the apperently simple and innocent formula
     sum  oo  1 (   4       2       1       1  )
p =    16k   8k-+-1-  8k+-4-- 8k+-5-- 8k+-6-
    k=0
(1)

now called the BBP formula (see Plouffe's page). Our three canadians noticed that this expression is very close to a decomposition in base 16 of p  . In the 1996 article [1] that is now famous, they show that you can use 1 to find the n  th digit of p  in base  p
2  (all the more in base 16) without having worked out the previous digist, all of this in roughly a linear time        3
O(n.log n  ) and in space O(logn)  !! The space required being so small, they apply straight away this result by calculating the 40  billionth digit of p  in base 2.

Let's stop now working on the calculation of the n  th digit of p  by considering the general case of a number a  and an associated BBP formula:

2 Finding the N  -th digit of a number a  without knowing the previous one

We will follow here, with a few adaption, the very clear explenation of Xavier Gourdon and Pascal Sebah on the subject [2] which already simplified the original article [1]. X. Gourdon knows a lot on claculation algorithm since he is the current holder (for quite a few years) of the speed record in calculating the decimals of p  with the program PiFast (even faster than the program made by Kanada's team).

To simplify the reasoning, we will restrain ourself to base 2  , and the N  th bit of a  defines the N  th bit of the fraction part of a  , that is the part after the dot. The fraction part of a number shall be written as {x}=  x- [x]  .

2.1 Shift

The first idea relies on the following theorem

Theorem 2.1 The N + n  th bit of a  is obtained by calculating the n  th bit of 2Na  i.e. the n  th bit of {    }
 2N a .

Proof. Decomposing a  in base 2   

a = [a]+ {a}=  sum   ak+  sum   ak,        (a   (-  {0,1})
                  2k      2k           k
              k<0     k>0
(2)

where { 2Na} =  sum     -ak-=  sum     aN+k
           k>N 2k- N    k>0  2k  . The n  th bit of {2N a} is therefore a
  N+n  which as wanted is the N + n  th bit of a  .  __

Example 2.2 Let's find the 13th bit of p  . Since we have 212p = 12867.9635...  , in particular, {    }
 212p  = 0.9635...  . All that is left now is to work out the 1er  bit of 0.9635  . Changing into binary, we get

         -1   1-  -1   1-   0-  -1   1-
0.9635...= 21 + 22 + 23 + 24 + 25 + 26 + 27 + ...= [0.1111011...]base 2
(3)

hence the 13`eme  bit of p  is 1  , and the 17`eme  bit is 0  .

Finding the N + 1  th bit of p  is therefore the same as finding the first bit of {    }
 2N p . Using the BBP formula 1, this correspond to the first bit of the serie

       oo  ({   N-4n}   {   N- 4n }  {  N- 4n }  {  N- 4n } )
pN =  sum     4.2----  -   2.2-----  -  2-----  -  2-----   = AN + BN
     n=0    8n+ 1       8n + 4      8n + 5     8n + 6
(4)

where AN  and BN  are the sums

         sum                   sum 
AN  =       ,        BN =      .
      0<n<N/4              n>N/4
(5)

Taking into account the fast decrease of 2N -4n  for n > N-
    4  , we just need to evaluate the first few terms of BN  (in floating point form!), plus exacly enough for the rest of the sum is less than the presicion needed (here 1  bit after the dot).

Concerning AN  , we can put its general term in the form

{    }
 p.2n
  m
(6)

with p, n  and m  in N  . By writting p.2n = qm + r  the euclidien division of p.2n  by m  , we can see that r < m  , { p.2n}   r-
   m   = m  . This can also be written as

{ p.2n }   p.2n (mod m)
  -m--  = -----m-----.
(7)

2.2 Exponentiation

Imagine that we want to calculate the 1000`eme  bit of 231549  . Thanks to the previous principles, this comes down to calculate the 965`eme  bit of 419  and so the 1er  bit of 249694  . Using 7, we need to find r  such that 2964 = 49q + r  hence evaluate 2964 (mod 49)  .

Calculating 2964 (mod 49)  is done by a method called binary exponentiation (or binary powering), whose idea seems to have been already used before 200 BC [3], and even considered by the Egyptians to carry out multiplication! This simply comes down to using modulo 49  arithmetic, in other words working in Z/49Z  , in three steps :

  1. We decompose 964  in powers of 2  : 989 = 512 +256 + 128+ 64+ 4
  2. We calculate each steps the power of untill we reach 512  : 22 = 4; 24 = (22)2 = 4*4 = 16;  28 = 162 = 256 = 49 *5+ 11 = 11; 216 = 112 = 121 = 23;                                                  232 = 232 = 529 = 39;  264 = 392 = 1521 = 2;  2128 = 22 = 4;  2256 = 16;   2512 = 162 = 11
  3. We use step 1 et 2 : 2964 = 2512+256+128+64+4 = 11 ×16 × 4× 2× 4 = 5632 = 46  .

More generally to obtain       n
r = p.2 (mod m)  , we set r  to 1 and we take the biggest power of 2  less than n  . Then we apply the following algorithm that is equivalent to our example :

  1. If n > t  , Then r = 2.r (mod m)  ;  n = n- t  ; EndIf
  2. t = t/2;
  3. If t > 1  Then r = r2 (mod m)  ; Go to step 1. ; EnfIf.

Finnaly we end up with r = p.r (mod m);  to take into account p  . Due to the decomposition of n  in powers of 2  , we use O(logn)  (mod m)  operations for this calculation, which is very weak !

2.3 Final Steps

All that is left is to obtain r-= p.2n-(modm)
m       m  and then to sum evrything on 0 < n < N-
        4  to obtain AN  in 5. We need to note that if the calculation of every term of AN  is done in floating point form and that, say, the last bit is wrong, then in the worst case scenario the of the remainders on the whole sum will produce an error on 1+ log2 N
       4  bits. For the values of N  non-excessive, we can in all calmness carry out the calculations of -r
m  with an arithmetic precision of only 64  bits.

For this reason and by noting that for AN  , we sum O(N )  termes each needing O(logN )  operations due to the exponentiation, the algorithm requires O(N.logN.M (logN ))  operations and O(logN )  in space, where j < M (j) < j2  is the complexity of the multiplication of two integers of size j  bits.

References

[1]   D.H. Bailey, P.B. Borwein, S. Plouffe, “On the Rapid Computation of Various Polylogarithmic Constants”, Mathematics of Computation, 1997, vol. 66, pp. 903-913.

[2]   X. Gourdon, P. Sebah, “N-th digit computation”, preprint, 2003, http://numbers.computation.free.fr/Constants/Algorithms/nthdigit.pdf.

[3]   D. E. Knuth, “The Art of Computer Programming. Vol. 2: Seminumerical Algorithms”, Addison-Wesley, Reading, MA, 1981.


back to home page