Chudnovsky algorithm

APL-related discussions - a stream of APL consciousness.
Not sure where to start a discussion ? Here's the place to be
Forum rules
This forum is for discussing APL-related issues. If you think that the subject is off-topic, then the Chat forum is probably a better place for your thoughts !

Chudnovsky algorithm

Postby Roger|Dyalog on Wed Dec 23, 2020 10:07 pm

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

Image

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

Image

      
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.
Roger|Dyalog
 
Posts: 231
Joined: Thu Jul 28, 2011 10:53 am

Return to APL Chat

Who is online

Users browsing this forum: No registered users and 1 guest