추드노브스키 알고리즘 은 라마누잔 의 π 공식 을 바탕으로 π 의 숫자를 계산하는 빠른 방법이다.그것은 Chudnovsky 형제에 의해 1988[1]에 π의 2.7조의 세계 기록 산출에 12월 2009,[2]에 10월 2011,[3][4]22.4조 자리 10조 자리 숫자에 11월 2016,[5]에 9월 31.4조 자리 1월 29일 2018–January 2019,[6]50조원 숫자, 2020,[7]628조에서 사용되었다고 출판되었다.8월 14일 숫자 , 2021.[8]
The algorithm is based on the negated Heegner number d = − 163 {\displaystyle d=-163} , the j -function j ( 1 + i 163 2 ) = − 640320 3 {\displaystyle j\left({\tfrac {1+i{\sqrt {163}}}{2}}\right)=-640320^{3}} , and on the following rapidly convergent generalized hypergeometric series :[2]
1 π = 12 ∑ q = 0 ∞ ( − 1 ) q ( 6 q ) ! ( 545140134 q + 13591409 ) ( 3 q ) ! ( q ! ) 3 ( 640320 ) 3 q + 3 2 {\displaystyle {\frac {1}{\pi }}=12\sum _{q=0}^{\infty }{\frac {(-1)^{q}(6q)!(545140134q+13591409)}{(3q)!(q!)^{3}\left(640320\right)^{3q+{\frac {3}{2}}}}}} 이 공식에 대한 자세한 증거는 여기에서 확인할 수 있다.[9]
고성능 반복 구현의 경우 다음과 같이 단순화할 수 있음
( 640320 ) 3 2 12 π = 426880 10005 π = ∑ q = 0 ∞ ( 6 q ) ! ( 545140134 q + 13591409 ) ( 3 q ) ! ( q ! ) 3 ( − 262537412640768000 ) q {\displaystyle {\frac {(640320)^{\frac {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개의 큰 정수 항(다항 용어 Mq , 선형 용어 Lq , 지수 용어q X)이 있으며, π 은 다음과 같이 연속물의 합으로 나눈 상수 C 와 같다.
π = C ( ∑ q = 0 m M q l L q X q ) - 1 {\displaystyle \pi = C\left(\sum _ {q=0}^{\inflt }{\frac {M_{q}\cdot L_{q}}}}}}}}}}}}{ q}}}}}}}}}}}}}}{{{ x_{ q}\rig)^{{{{{{{{{x_ {{{{{{{{{{{{ C = 426880 10005 {\ displaystyle C=426880{\sqrt{10005 }}, M q = ( 6 q ) ! ( 3 q ) ! ( q ! ) 3 {\ displaystyle M_{q}={\frac {(6q)!}{(3q!)^{3 }}}, L q = 545140134 q + 13591409 {\displaystyle L_{q}=545140134q+13591409 }, X q = ( - 262537412640768000 ) q {\ displaystyle X_{q}=(-262537412640768000)^{q }}}}. Mq , Lq , X 라는q 용어는 다음과 같은 반복을 만족하며 다음과 같이 계산할 수 있다.
L q + 1 = L q + 545140134 어디에 L 0 = 13591409 X q + 1 = X q ⋅ ( − 262537412640768000 ) 어디에 X 0 = 1 M q + 1 = M q ⋅ ( ( 12 q − 2 ) ( 12 q − 6 ) ( 12 q − 10 ) q 3 ) 어디에 M 0 = 1 {\displaystyle {\reasonedat}{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)}{q^{3}\}\오른쪽)\,\,\,&#{where}\,\,\,\,M_{0}&=1\\\,[4pt]\end{ligedat}}}}}}}}}}}}}}}}}}. M 의q 연산은 다음과 같은 추가 용어 K 를q 도입하여 더욱 최적화할 수 있다.
K q + 1 = K q + 12 어디에 K 0 = − 6 M q + 1 = M q ⋅ ( K q 3 − 16 K q q 3 ) 어디에 M 0 = 1 {\displaystyle {\begin{aignedat}{4}K_{q+1}&=K_{q}+12\,\&#{where}\,\,\,\, K_{0}&}&=-6\[4pt]M_{q+1}&===}&=} M_{q}\cdot \left({\frac {K_{q}^{3}-16K_{q}}}}}\,\,&#{{q^{3}}}}}\,\&#{where}\,\,\{0}>\[12pt]\end{ligedat}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} 참고:
e π 163 ≈ 640320 3 + 743. 99999999999925 … {\displaystyle e^{\pi {\sqrt{sqrt}}\약 640320^{3}+743. 99999999999925\1909 } 및 640320 3 = 262537412640768000 {\displaystyle 640320^{3}=262537412640768000} 545140134 = 163 ⋅ 127 ⋅ 19 ⋅ 11 ⋅ 7 ⋅ 3 2 ⋅ 2 {\displaystyle 545140134=cdot 127\cdot 19\cdot 11\cdot 7\cdot 3^{2}\cdot 2} 13591409 = 13 ⋅ 1045493 13591409=13\cdot 1045493} 이러한 정체성은 π 과 관련된 라마누잔 의 일부 공식과 유사하며, [2] 라마누잔-사토 시리즈의 예다.
알고리즘의 시간 복잡도 는 O(n log ( n ) 3 ) {\ displaystyle O\left(n\log(n)^{3}\right)} 입니다. [10]
참고 항목 참조 ^ Chudnovsky, David; Chudnovsky, Gregory (1988), Approximation and complex multiplication according to ramanujan , Ramanujan revisited: proceedings of the centenary conference ^ a b c Baruah, Nayandeep Deka; Berndt, Bruce C.; Chan, Heng Huat (2009), "Ramanujan's series for 1/π : a survey", American Mathematical Monthly , 116 (7): 567–587, doi :10.4169/193009709X458555 , JSTOR 40391165 , MR 2549375 ^ Yee, Alexander; Kondo, Shigeru (2011), 10 Trillion Digits of Pi: A Case Study of summing Hypergeometric Series to high precision on Multicore Systems , Technical Report, Computer Science Department, University of Illinois, hdl :2142/28348 ^ Aron, Jacob (March 14, 2012), "Constants clash on pi day" , New Scientist ^ "22.4 Trillion Digits of Pi" . www.numberworld.org . ^ "Google Cloud Topples the Pi Record" . www.numberworld.org/ . ^ "The Pi Record Returns to the Personal Computer" . www.numberworld.org/ . ^ "Pi-Challenge - Weltrekordversuch der FH Graubünden - FH Graubünden" . www.fhgr.ch . Retrieved 2021-08-17 . ^ Milla, Lorenz (2018), A detailed proof of the Chudnovsky formula with means of basic complex analysis , arXiv :1809.00533 ^ "y-cruncher - Formulas" . www.numberworld.org . Retrieved 2018-02-25 .