Алгоритм Чудновского

Алгоритм Чудновский является быстрым методом расчета цифр П , основанных на Рамануджан «ы л формул . Он был опубликован братьями Чудновскими в 1988 году ^[1] и использовался в расчетах мирового рекорда 2,7 триллиона цифр π в декабре 2009 года ^[2] 10 триллионов цифр в октябре 2011 года, ^{[3] [4]} 22,4 триллиона цифр в Ноябрь 2016 г. ^[5] 31,4 триллиона цифр в сентябре 2018 г. - январе 2019 г. ^[6] и 50 триллионов цифр 29 января 2020 г. ^[7]

Алгоритм основан на отрицательном числе Хегнера , j -функции и на следующем быстро сходящемся обобщенном гипергеометрическом ряде : ^[2]${\ displaystyle d = -163}$ ${\displaystyle \scriptstyle j\left({\frac {1+{\sqrt {-163}}}{2}}\right)=-640320^{3}}$

${\displaystyle {\frac {1}{\pi }}=12\sum _{q=0}^{\infty }{\frac {(-1)^{q}(6q)!(545140134q+13591409)}{(3q)!(q!)^{3}\left(640320\right)^{3q+3/2}}}}$

Подробное доказательство этой формулы можно найти здесь: ^[8]

Для высокопроизводительной итеративной реализации это можно упростить до

${\displaystyle {\frac {(640320)^{3/2}}{12\pi }}={\frac {426880{\sqrt {10005}}}{\pi }}=\sum _{q=0}^{\infty }{\frac {(6q)!(545140134q+13591409)}{(3q)!(q!)^{3}\left(-262537412640768000\right)^{q}}}}$

Есть 3 больших целых члена (полиномиальный член M _q , линейный член L _q и экспоненциальный член X _q ), которые составляют ряд, а π равно константе C, деленной на сумму ряда, как показано ниже:

${\displaystyle \pi =C\left(\sum _{q=0}^{\infty }{\frac {M_{q}\cdot L_{q}}{X_{q}}}\right)^{-1}}$, куда:

${\displaystyle C=426880{\sqrt {10005}}}$,

${\displaystyle M_{q}={\frac {(6q)!}{(3q)!(q!)^{3}}}}$,

${\displaystyle L_{q}=545140134q+13591409}$,

${\displaystyle X_{q}=(-262537412640768000)^{q}}$.

Члены M _q , L _q и X _q удовлетворяют следующим повторениям и могут быть вычислены как таковые:

${\displaystyle {\begin{alignedat}{4}L_{q+1}&=L_{q}+545140134\,\,&&{\textrm {where}}\,\,L_{0}&&=13591409\\[4pt]X_{q+1}&=X_{q}\cdot (-262537412640768000)&&{\textrm {where}}\,\,X_{0}&&=1\\[4pt]M_{q+1}&=M_{q}\cdot \left({\frac {(12q+2)(12q+6)(12q+10)}{(q+1)^{3}}}\right)\,\,&&{\textrm {where}}\,\,M_{0}&&=1\\[4pt]\end{alignedat}}}$

Вычисление M _q можно дополнительно оптимизировать, введя дополнительный член K _q следующим образом:

${\displaystyle {\begin{alignedat}{4}K_{q+1}&=K_{q}+12\,\,&&{\textrm {where}}\,\,K_{0}&&=6\\[4pt]M_{q+1}&=M_{q}\cdot \left({\frac {K_{q}^{3}-16K_{q}}{(q+1)^{3}}}\right)\,\,&&{\textrm {where}}\,\,M_{0}&&=1\\[12pt]\end{alignedat}}}$

Обратите внимание, что

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

${\displaystyle 640320^{3}=262537412640768000}$

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

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

Это тождество аналогично некоторым формулам Рамануджана , включающим π , ^[2], и является примером ряда Рамануджана – Сато .

Временная сложность алгоритма является . ^[9]${\displaystyle O(n\log(n)^{3})}$

См. Также [ править ]

• Алгоритм Борвейна
• Численные приближения π
• Рамануджан – Сато серия

Ссылки [ править ]