אלגוריתם צ'ודנובסקי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

אלגוריתם צ'ודנובסקי הוא אלגוריתם מהיר לחישוב הספרות של פאי (מספר). האלגוריתם פורסם בשנת 1989 על ידי האחים דויד וגריגורי וולפוביץ' צ'ודנובסקי. האלגוריתם שימש לשבירת השיא העולמי לחישוב הספרות של פאי מספר פעמים: בשיאים שחישבו את 2.7 טריליון (כלומר 12^10) הספרות של פאי ב-2009, את 10 טריליון הספרות ב-2011, בנובמבר 2016 חישבו בעזרת האלגוריתם 22.4 טריליון ספרות של פאי ובספטמבר 2018 עד ינואר 2019 חושבו באמצעותו 31.4 טריליון ספרות[1]].

סיבוכיות האלגוריתם כדי לחשב ספרות היא .

האלגוריתם מבוסס על הטור האינסופי:

אשר ניתן לפשטו לצורה יישנם שלושה ביטויים מסוגים שונים, שהם סדרות בקצבים שונים וקבוע: בקצב פולינומי Mk, בקצב ליניארי Lk, בקצב אקספוננציאלי Xk, והקבוע C, שעל בסיסם נתיתנת הנוסחה שהיא:

,

כאשר:
Mk+1 = Mk * (12k+2) * (12k+6) * (12k+10) / (k+1)^3, M0 = 1 [Mk = (6k)! / ((3k)! * (k!)^3)]
Lk+1 = Lk + 545,140,134, L0 = 13,591,409 [Lk = 13591409 + 545140134*k]
Xk+1 = Xk * -262,537,412,640,768,000, X0 = 1 [Xk = (-640320)^3k = (-262537412640768000)^k]

ניתן אף לשפר את הנוסחה על ידי הצבה של: Kk+1 = Kk + 12, K0 = 6
Mk+1 = Mk * (Kk^3 - 16Kk) / (k+1)^3 ,M0 = 1

דוגמת קוד בפייתון של האלגוריתם[עריכת קוד מקור | עריכה]

from decimal import Decimal as Dec, getcontext as gc

def PI(maxK=70, prec=1008, disp=1007): # parameter defaults chosen to gain 1000+ digits within a few seconds
    gc().prec = prec
    K, M, L, X, S = 6, 1, 13591409, 1, 13591409 
    for k in xrange(1, maxK+1):
        M = (K**3 - (K<<4)) * M / k**3 
        L += 545140134
        X *= -262537412640768000
        S += Dec(M * L) / X
        K += 12
    pi = 426880 * Dec(10005).sqrt() / S
    pi = Dec(str(pi)[:disp]) # drop few digits of precision for accuracy
    print "PI(maxK=%d iterations, gc().prec=%d, disp=%d digits) =\n%s" % (maxK, prec, disp, pi)
    return pi

Pi = PI()
print "\nFor greater precision and more digits (takes a few extra seconds) - Try"
print "Pi = PI(317,4501,4500)"
print "Pi = PI(353,5022,5020)"

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ [http://www.numberworld.org/blogs/2019_3_14_pi_record/ Google Cloud Topples the Pi Record