추드노브스키 알고리즘

Chudnovsky algorithm

추드노브스키 알고리즘라마누잔π 공식을 바탕으로 π의 숫자를 계산하는 빠른 방법이다.그것은 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 , the j-function , and on the following rapidly convergent generalized hypergeometric series:[2]

이 공식에 대한 자세한 증거는 여기에서 확인할 수 있다.[9]

고성능 반복 구현의 경우 다음과 같이 단순화할 수 있음

시리즈를 구성하는 3개의 큰 정수 항(다항 용어 Mq, 선형 용어 Lq, 지수 용어q X)이 있으며, π은 다음과 같이 연속물의 합으로 나눈 상수 C와 같다.

= ( = m q X) - {\= {q {qq}\{{{{{{{{{{{{
=
= ( )!( )! ( ! )
= +
=(- )

Mq, Lq, X라는q 용어는 다음과 같은 반복을 만족하며 다음과 같이 계산할 수 있다.

Mq 연산은 다음과 같은 추가 용어 Kq 도입하여 더욱 최적화할 수 있다.

참고:

이러한 정체성은 π과 관련된 라마누잔의 일부 공식과 유사하며,[2] 라마누잔-사토 시리즈의 예다.

알고리즘의 시간 복잡도 ) O 입니다[10]

참고 항목

참조

  1. ^ Chudnovsky, David; Chudnovsky, Gregory (1988), Approximation and complex multiplication according to ramanujan, Ramanujan revisited: proceedings of the centenary conference
  2. ^ 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
  3. ^ 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
  4. ^ Aron, Jacob (March 14, 2012), "Constants clash on pi day", New Scientist
  5. ^ "22.4 Trillion Digits of Pi". www.numberworld.org.
  6. ^ "Google Cloud Topples the Pi Record". www.numberworld.org/.
  7. ^ "The Pi Record Returns to the Personal Computer". www.numberworld.org/.
  8. ^ "Pi-Challenge - Weltrekordversuch der FH Graubünden - FH Graubünden". www.fhgr.ch. Retrieved 2021-08-17.
  9. ^ Milla, Lorenz (2018), A detailed proof of the Chudnovsky formula with means of basic complex analysis, arXiv:1809.00533
  10. ^ "y-cruncher - Formulas". www.numberworld.org. Retrieved 2018-02-25.