チュドノフスキーアルゴリズム

チュドノフスキー法は、ラマヌジャンのπ公式に基づいてπの桁を高速に計算する方法である。1988年にチュドノフスキー兄弟によって発表され^{[1] 、} πを小数点以下10億桁まで計算するために使用された。 ^[2]

これは、2009年12月のπの2.7兆桁^[3]、2011年10月の10兆桁^{[4] 、 [5]} 2016年11月の22.4兆桁^[6] 、 2018年9月～2019年1月の31.4兆桁^[7] 、 2020年1月29日の50兆桁^[8]、2021年8月14日の62.8兆桁^[9]、2022年3月21日の100兆桁^[10] 、 2024年3月14日の105兆桁^[11]、2024年6月28日の202兆桁^{[12]の世界記録計算に使用されました。}

このアルゴリズムは、否定されたヘーグナー数 、j関数、および次の急速に収束する一般化超幾何級数に基づいています。^[13]この公式の詳細な証明は、ここ^{[14]で見つけることができます。}${\displaystyle d=-163}$ ${\displaystyle j\left({\tfrac {1+i{\sqrt {163}}}{2}}\right)=-640320^{3}}$$${\displaystyle {\frac {1}{\pi }}=12\sum _{k=0}^{\infty }{\frac {(-1)^{k}(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}(640320)^{3k+3/2}}}}$$

この恒等式はπを含むラマヌジャンの いくつかの公式に似ており[ ^{13] 、}ラマヌジャン-佐藤級数の例である。

このアルゴリズムの時間計算量はである。^[15]${\displaystyle O\left(n(\log n)^{3}\right)}$

世界記録の計算に使用された最適化手法は、バイナリ分割と呼ばれます。^{[16] [信頼できない情報源? ]}

の係数を合計から取り除き、次のように簡略化することができる。${\textstyle 1/{640320^{3/2}}}$$${\displaystyle {\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}\sum _{k=0}^{\infty }{\frac {(-1)^{k}(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}(640320)^{3k}}}}$$

とし、それを合計に代入します。${\displaystyle f(n)={\frac {(-1)^{n}(6n)!}{(3n)!(n!)^{3}(640320)^{3n}}}}$$${\displaystyle {\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}\sum _{k=0}^{\infty }{f(k)\cdot (545140134k+13591409)}}$$

${\displaystyle {\frac {f(n)}{f(n-1)}}}$は と簡略化できるので、${\displaystyle {\frac {-(6n-1)(2n-1)(6n-5)}{10939058860032000n^{3}}}}$$${\displaystyle f(n)=f(n-1)\cdot {\frac {-(6n-1)(2n-1)(6n-5)}{10939058860032000n^{3}}}}$$

${\displaystyle f(0)=1}$の元の定義から、${\displaystyle f}$$${\displaystyle f(n)=\prod _{j=1}^{n}{\frac {-(6j-1)(2j-1)(6j-5)}{10939058860032000j^{3}}}}$$

この定義はに対して定義されていないので、和の最初の項を計算し、 の新しい定義を使用します。${\displaystyle f}$${\displaystyle n=0}$${\displaystyle f}$$${\displaystyle {\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}{\Bigg (}13591409+\sum _{k=1}^{\infty }{{\Bigg (}\prod _{j=1}^{k}{\frac {-(6j-1)(2j-1)(6j-5)}{10939058860032000j^{3}}}{\Bigg )}\cdot (545140134k+13591409)}{\Bigg )}}$$

とすると、${\displaystyle P(a,b)=\prod _{j=a}^{b-1}{-(6j-1)(2j-1)(6j-5)}}$${\displaystyle Q(a,b)=\prod _{j=a}^{b-1}{10939058860032000j^{3}}}$$${\displaystyle {\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}{\Bigg (}13591409+\sum _{k=1}^{\infty }{{\frac {P(1,k+1)}{Q(1,k+1)}}\cdot (545140134k+13591409)}{\Bigg )}}$$

させて、${\displaystyle S(a,b)=\sum _{k=a}^{b-1}{{\frac {P(a,k+1)}{Q(a,k+1)}}\cdot (545140134k+13591409)}}$${\displaystyle R(a,b)=Q(a,b)\cdot S(a,b)}$$${\displaystyle \pi ={\frac {426880{\sqrt {10005}}}{13591409+S(1,\infty )}}}$$

${\displaystyle S(1,\infty )}$は計算できないので、代わりにとを計算します。 が に近づくにつれて、近似値はより良くなります。${\displaystyle S(1,n)}$${\displaystyle n}$${\displaystyle \infty }$${\displaystyle \pi }$$${\displaystyle \pi =\lim _{n\to \infty }{\frac {426880{\sqrt {10005}}}{13591409+S(1,n)}}}$$

の元の定義から、${\displaystyle R}$${\displaystyle S(a,b)={\frac {R(a,b)}{Q(a,b)}}}$$${\displaystyle \pi =\lim _{n\to \infty }{\frac {426880{\sqrt {10005}}\cdot Q(1,n)}{13591409Q(1,n)+R(1,n)}}}$$

次のような値を考える${\displaystyle m}$${\displaystyle a<m<b}$

• ${\displaystyle P(a,b)=P(a,m)\cdot P(m,b)}$

• ${\displaystyle Q(a,b)=Q(a,m)\cdot Q(m,b)}$
• ${\displaystyle S(a,b)=S(a,m)+{\frac {P(a,m)}{Q(a,m)}}S(m,b)}$
• ${\displaystyle R(a,b)=Q(m,b)R(a,m)+P(a,m)R(m,b)}$

考慮する${\displaystyle b=a+1}$

• ${\displaystyle P(a,a+1)=-(6a-1)(2a-1)(6a-5)}$
• ${\displaystyle Q(a,a+1)=10939058860032000a^{3}}$
• ${\displaystyle S(a,a+1)={\frac {P(a,a+1)}{Q(a,a+1)}}\cdot (545140134a+13591409)}$
• ${\displaystyle R(a,a+1)=P(a,a+1)\cdot (545140134a+13591409)}$

#注: 極端な計算の場合は、他のコードを使用して GPU で実行することもできます。これは、これよりもはるかに高速です。
 10進数をインポート


 バイナリ分割の定義( a ,  b ):
     b  ==  a  +  1の場合:
        Pab  =  - ( 6 * a  -  5 ) * ( 2 * a  -  1 ) * ( 6 * a  -  1 )
        Qab  =  10939058860032000  *  a ** 3
        Rab  = パブ *  ( 545140134 * a  +  13591409 )
    それ以外：
        m  =  ( a  +  b )  //  2 です
        Pam 、 Qam 、 Ram  =  binary_split ( a 、 m )
        Pmb 、 Qmb 、 Rmb  =  binary_split ( m 、 b )
        
        パブ = パム * パム
        カブ = カアム * カム
        Rab  =  Qmb  *  Ram  +  Pam  *  Rmb
     Pab 、 Qab 、 Rabを返す


 チュドノフスキーの定義( n ):
    「「チュドノフスキーアルゴリズム」」」
    P1n 、 Q1n 、 R1n  = バイナリ分割( 1 、 n )
    戻り値 ( 426880  * 小数点.小数点( 10005 ) . sqrt ()  *  Q1n )  /  ( 13591409 * Q1n  +  R1n )


print ( f "1 = { chudnovsky ( 2 ) } " )   # 3.141592653589793238462643384

小数点.getcontext ( ) . prec = 100 # 小数点精度の桁数   
 n が範囲( 2,10 )の 場合:
    print ( f " { n } = { chudnovsky ( n ) } " )   # 3.14159265358979323846264338...

${\displaystyle e^{\pi {\sqrt {163}}}\approx 640320^{3}+743.99999999999925\dots }$

${\displaystyle 640320^{3}/24=10939058860032000}$

${\displaystyle 545140134=163\cdot 127\cdot 19\cdot 11\cdot 7\cdot 3^{2}\cdot 2}$

${\displaystyle 13591409=13\cdot 1045493}$

• ラマヌジャン・佐藤級数
• ベイリー・ボーウェイン・プルーフ式
• ボルウェインのアルゴリズム
• πの近似値