Chudnovsky algorithm

[Roger|Dyalog]

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



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

      ⍝
pica←{
  k   ← qi ⍳⍵
  top ← (!Q k×qi 6) ×Q (qi 13591409) +Q k ×Q qi 545140134
  bot ← (!Q k×qi 3) ×Q ((!Q k)*Q qi 3) ×Q (qi 640320) *Q k ×Q qi 3
  rt  ← {(qi 2) ÷Q⍨ ⍵ +Q (qi 640320) ÷Q ⍵}⍣(⌈2⍟1+⍵) qi 640320*0.5
                                          ⍝ sqrt 640320 to 14×⍵ digits
  ÷Q ((qi 12) ÷Q (qi 640320) ×Q rt) ×Q -Q/ top ÷Q bot
}

For example:

      100 ⍕Q pica 8
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170680

      ⍝ OEIS A000796
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982

pica uses operator Q and function qi of the Rational Arithmetic facility. The code is available from here.

Substantially the same text previously appeared as the J wiki essay Chudnovsky Algorithm, 2011-05-08.