Chudnovského algoritmus - Chudnovsky algorithm

The Chudnovského algoritmus je rychlá metoda pro výpočet číslic π, na základě Ramanujan Je π vzorce. To bylo zveřejněno Chudnovští bratři v roce 1988^[1] a byl použit v světový rekord výpočty 2,7 ​​bilionu číslic π v prosinci 2009,^[2] 10 bilionů číslic v říjnu 2011,^[3][4] 22,4 bilionu číslic v listopadu 2016,^[5] 31,4 bilionu číslic v září 2018 – lednu 2019,^[6] a 50 bilionů číslic 29. ledna 2020.^[7]

Algoritmus je založen na negovaném Heegnerovo číslo ${displaystyle d = -163}$, j-funkce ${displaystyle scriptstyle jleft ({frac {1+ {sqrt {-163}}} {2}} ight) = - 640320 ^ {3}}$a dále rychle konvergentní zobecněná hypergeometrická řada:^[2]

${displaystyle {frac {1} {pi}} = 12sum _ {q = 0} ^ {infty} {frac {(-1) ^ {q} (6q)! (545140134q + 13591409)} {{3q)! ( q!) ^ {3} vlevo (640320ight) ^ {3q + 3/2}}}}$

Podrobný důkaz tohoto vzorce naleznete zde:^[8]

U vysoce výkonné iterativní implementace to lze zjednodušit na

${displaystyle {frac {(640320) ^ {3/2}} {12pi}} = {frac {426880 {sqrt {10005}}} {pi}} = součet _ {q = 0} ^ {infty} {frac { (6q)! (545140134q + 13591409)} {(3q)! (Q!) ^ {3} vlevo (-262537412640768000ight) ^ {q}}}}$

Existují 3 velké celočíselné výrazy (multinomický výraz M_q, lineární člen L_qa exponenciální člen X_q), které tvoří sérii a π rovná se konstanta C děleno součtem řady, jak je uvedeno níže:

${displaystyle pi = rozštěp (součet _ {q = 0} ^ {infty} {frac {M_ {q} cdot L_ {q}} {X_ {q}}} večer) ^ {- 1}}$, kde:

${displaystyle C = 426880 {sqrt {10005}}}$,

${displaystyle M_ {q} = {frac {(6q)!} {(3q)! (q!) ^ {3}}}}$,

${displaystyle L_ {q} = 545140134q + 13591409}$,

${displaystyle X_ {q} = (- 262537412640768000) ^ {q}}$.

Podmínky M_q, L_q, a X_q uspokojit následující opakování a lze je vypočítat jako takové:

${displaystyle {egin {alignedat} {4} L_ {q + 1} & = L_ {q} +545140134 ,, && {extrm {where}} ,, L_ {0} && = 13591409 [4pt] X_ {q + 1} & = X_ {q} cdot (-262537412640768000) && {extrm {where}} ,, X_ {0} && = 1 [4pt] M_ {q + 1} & = M_ {q} cdot left ({frac {(12q + 2) (12q + 6) (12q + 10)} {(q + 1) ^ {3}}} ight) ,, && {extrm {where}} ,, M_ {0} && = 1 [4pt] konec {alignedat}}}$

Výpočet M_q lze dále optimalizovat zavedením dalšího termínu K._q jak následuje:

${displaystyle {egin {alignedat} {4} K_ {q + 1} & = K_ {q} +12 ,, && {extrm {where}} ,, K_ {0} && = 6 [4pt] M_ {q + 1} & = M_ {q} cdot left ({frac {K_ {q} ^ {3} -16K_ {q}} {(q + 1) ^ {3}}} ight) ,, && {extrm {where} } ,, M_ {0} && = 1 [12pt] konec {alignedat}}}$

Všimněte si, že

${displaystyle e ^ {pi {sqrt {163}}} přibližně 640320 ^ {3} + 743,9999999999992525 bodů}$ a

${displaystyle 640320 ^ {3} = 262537412640768000}$

${displaystyle 545140134 = 163cdot 127cdot 19cdot 11cdot 7cdot 3 ^ {2} cdot 2}$

${displaystyle 13591409 = 13cdot 1045493}$

Tato identita je podobná některým z Ramanujan vzorce zahrnující π,^[2] a je příkladem a Série Ramanujan – Sato.

The časová složitost algoritmu je ${displaystyle O (nlog (n) ^ {3})}$.^[9]

Viz také

• Borweinův algoritmus
• Numerické aproximace π
• Série Ramanujan – Sato

Reference