הצגת המקור של הדף "אלגוריתם צ'ודנובסקי"

'''אלגוריתם צ'ודנובסקי''' הוא [[אלגוריתם]] מהיר לחישוב הספרות של [[π|פאי (מספר)]]. האלגוריתם פורסם בשנת [[1989]] על ידי [[האחים צ'ודנובסקי|האחים דויד וגריגורי וולפוביץ' צ'ודנובסקי]]. האלגוריתם שימש לשבירת השיא העולמי לחישוב הספרות של פאי מספר פעמים: בשיאים שחישבו את 2.7 טריליון (כלומר 12^10) הספרות של פאי ב-[[2009]], את 10 טריליון הספרות ב-[[2011]], ב[[נובמבר]] [[2016]] חישבו בעזרת האלגוריתם 22.4 טריליון ספרות של פאי ובספטמבר 2018 עד ינואר 2019 חושבו באמצעותו  31.4 טריליון ספרות{{הערה|1=[http://www.numberworld.org/blogs/2019_3_14_pi_record/ Google Cloud Topples the Pi Record}}].

סיבוכיות האלגוריתם כדי לחשב <math>n</math> ספרות היא  <math>O(n \log^3 n)</math>.

האלגוריתם מבוסס על הטור האינסופי:
:<math> \frac{1}{\pi} = 12 \sum^\infty_{k=0} \frac{(-1)^k (6k)! (545140134k + 13591409)}{(3k)!(k!)^3 \left(640320\right)^{3k + 3/2}}\!</math>
אשר ניתן לפשטו לצורה 
<math> \frac{(640320)^{3/2}}{12\pi}=\frac{426880\sqrt{10005}}{\pi} = \sum^\infty_{k=0} \frac{(6k)! (545140134k + 13591409)}{(3k)!(k!)^3 \left(-262537412640768000\right)^{k}}\!</math>
יישנם שלושה ביטויים מסוגים שונים, שהם סדרות בקצבים שונים וקבוע: בקצב פולינומי M<sub>k</sub>, בקצב ליניארי L<sub>k</sub>, בקצב אקספוננציאלי X<sub>k</sub>, והקבוע C, שעל בסיסם ניתנת הנוסחה שהיא: 
:<math>\pi = C \left(\sum^\infty_{k=0} \frac{M_k \cdot L_k}{X_k}\right)^{-1}</math>,
כאשר:
<math>C = 426880\sqrt{10005}</math><br>
M<sub>k+1</sub> = M<sub>k</sub> * (12k+2) * (12k+6) * (12k+10) / (k+1)^3, M<sub>0</sub> = 1  [M<sub>k</sub> = (6k)! / ((3k)! * (k!)^3)]<br>
L<sub>k+1</sub> = L<sub>k</sub> + 545,140,134, L<sub>0</sub> = 13,591,409  [L<sub>k</sub> = 13591409 + 545140134*k]<br>
X<sub>k+1</sub> = X<sub>k</sub> * -262,537,412,640,768,000, X<sub>0</sub> = 1  [X<sub>k</sub> = (-640320)^3k = (-262537412640768000)^k]

ניתן אף לשפר את הנוסחה על ידי הצבה של:
K<sub>k+1</sub> = K<sub>k</sub> + 12, K<sub>0</sub> = 6<br>
M<sub>k+1</sub> = M<sub>k</sub> * (K<sub>k</sub>^3 - 16K<sub>k</sub>) / (k+1)^3 ,M<sub>0</sub> = 1
== דוגמת קוד בפייתון של האלגוריתם ==
<syntaxhighlight lang="python" line="1">
import decimal


def binary_split(a, b):
    if b == a + 1:
        Pab = -(6*a - 5)*(2*a - 1)*(6*a - 1)
        Qab = 10939058860032000 * a**3
        Rab = Pab * (545140134*a + 13591409)
    else:
        m = (a + b) // 2
        Pam, Qam, Ram = binary_split(a, m)
        Pmb, Qmb, Rmb = binary_split(m, b)
        
        Pab = Pam * Pmb
        Qab = Qam * Qmb
        Rab = Qmb * Ram + Pam * Rmb
    return Pab, Qab, Rab


def chudnovsky(n):
    """Chudnovsky algorithm."""
    P1n, Q1n, R1n = binary_split(1, n)
    return (426880 * decimal.Decimal(10005).sqrt() * Q1n) / (13591409*Q1n + R1n)


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

decimal.getcontext().prec = 100 # number of digits of decimal precision
for n in range(2,10):
    print(f"{n} = {chudnovsky(n)}")  # 3.14159265358979323846264338...

</syntaxhighlight>

==הערות שוליים==
{{הערות שוליים}}

[[קטגוריה:פאי]]
[[קטגוריה:אלגוריתמים|צ'ודנובסקי]]