Essays/Chudnovsky Algorithm

From J Wiki
Jump to: navigation, search

The Chudnovsky algorithm is a fast method for computing the digits of \pi. Each term of the series produces an additional 14 decimal digits.

 \frac{1}{\pi} = 12 \sum^\infty_{k=0} \frac{(-1)^k (6k)! (13591409 + 545140134k)}{(3k)!(k!)^3 640320^{3k + 3/2}}

To facilitate its implementation in J, we rewrite the formula so that the terms are rational.

 \frac{1}{\pi} = \frac{12}{640320^{1.5}} \sum^\infty_{k=0} \frac{(-1)^k (6k)! (13591409 + 545140134k)}{(3k)!(k!)^3 640320^{3k}}

pica=: 3 : 0
 k  =. x: i. y
 top=. (!6*k) * 13591409+545140134*k
 bot=. (!3*k) * ((!k)^3) * 640320^3*k
 rt =. -:@(+640320&%)^:(>.2^.1+y) x:%:640320   NB. sqrt 640320 to 14*y digits
 % (12 % 640320*rt) * -/ top % bot
)

For example:

   0j100 ": pica 7
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170658
   0j100 ": t %~ <.@o. t=. 10^100x
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679



See also


Contributed by Roger Hui.