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

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

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

אשר ניתן לפשטו לצורה 

יישנם שלושה ביטויים מסוגים שונים, שהם סדרות בקצבים שונים וקבוע: בקצב פולינומי 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
 דוגמת קוד בפייתון של האלגוריתם 
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...

הערות שוליים

קטגוריה:פאי
צ'ודנובסקי