L' algorithme de Chudnovsky est une méthode rapide pour calculer les chiffres de π, basée sur les formules de π de Ramanujan. Il a été publié par les frères Chudnovsky en 1988.

Il a été utilisé pour le calcul du record mondial de 2 700 milliards de chiffres de π en , 10 000 milliards de chiffres en , 22 400 milliards de chiffres en [1], 31 400 milliards de chiffres en . – [2], 50 000 milliards de chiffres le [3], 62 800 milliards de chiffres le [4], 100 000 milliards de chiffres le [5], et 105 000 milliards de chiffres le [6]..

Algorithme

modifier

L'algorithme est basé sur l'opposé du nombre de Heegner d=−163, la fonction j j(1+i1632)=−6403203, et sur la série hypergéométrique généralisée à convergence rapide ci-dessous: 1π=12∑k=0∞(−1)k(6k)!(545140134k+13591409)(3k)!(k!)3(640320)3k+3/2Une preuve détaillée de cette formule peut être trouvée ici[7] :

Cette identité est similaire à certaines formules de Ramanujan impliquant π, et est un exemple de série Ramanujan-Sato.

La complexité temporelle de l'algorithme est en O(n(log⁡n)3)[8].

Optimisations

modifier

La technique d'optimisation utilisée pour les calculs du record du monde est appelée division binaire.

Fractionnement binaire

modifier

Un facteur de 1/6403203/2 peut être retiré de la somme et simplifié en1π=142688010005∑k=0∞(−1)k(6k)!(545140134k+13591409)(3k)!(k!)3(640320)3k

Soit f(n)=(−1)n(6n)!(3n)!(n!)3(640320)3n, et en substituant dans la somme.1π=142688010005∑k=0∞f(k)⋅(545140134k+13591409)f(n)f(n−1) peut être simplifié en −(6n−1)(2n−1)(6n−5)10939058860032000n3, doncf(n)=f(n−1)⋅−(6n−1)(2n−1)(6n−5)10939058860032000n3f(0)=1 par définition de f, doncf(n)=∏j=1n−(6j−1)(2j−1)(6j−5)10939058860032000j3Cette définition de f n'est pas défini pour n=0, on calcule donc le premier terme de la somme et l'ajoute à la nouvelle définition de f en partant de n=11π=142688010005(13591409+∑k=1∞(∏j=1k−(6j−1)(2j−1)(6j−5)10939058860032000j3)⋅(545140134k+13591409))Soit P(a,b)=∏j=ab−1−(6j−1)(2j−1)(6j−5) et Q(a,b)=∏j=ab−110939058860032000j3, donc1π=142688010005(13591409+∑k=1∞P(1,k+1)Q(1,k+1)⋅(545140134k+13591409))Soit S(a,b)=∑k=ab−1P(a,k+1)Q(a,k+1)⋅(545140134k+13591409) et R(a,b)=Q(a,b)⋅S(a,b)π=4268801000513591409+S(1,∞)S(1,∞) est une limite qui ne peut être qu'approché, on calcule à la place S(1,n) et lorsque n se rapproches de ∞, l'approximation de π l'approximation s'améliore.π≈4268801000513591409+S(1,n)Par définition originale de R, S(a,b)=R(a,b)Q(a,b)π≈42688010005⋅Q(1,n)13591409Q(1,n)+R(1,n)

Calcul récursif des fonctions

modifier
  • P(a,b)=P(a,m)⋅P(m,b)
  • Q(a,b)=Q(a,m)⋅Q(m,b)
  • S(a,b)=S(a,m)+P(a,m)Q(a,m)S(m,b)
  • R(a,b)=Q(m,b)R(a,m)+P(a,m)R(m,b)

Construction de la récursion

modifier

Si b=a+1

  • P(a,a+1)=−(6a−1)(2a−1)(6a−5)
  • Q(a,a+1)=10939058860032000a3
  • S(a,a+1)=P(a,a+1)Q(a,a+1)⋅(545140134a+13591409)
  • R(a,a+1)=P(a,a+1)⋅(545140134a+13591409)

Code Python

modifier
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(chudnovsky(2))  # 3.141592653589793238462643384

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

Remarques

modifier
eπ163≈6403203+743.99999999999925…
6403203/24=10939058860032000
545140134=163⋅127⋅19⋅11⋅7⋅32⋅2
13591409=13⋅1045493

Voir aussi

modifier

Références

modifier
  1. ↑ « 22.4 Trillion Digits of Pi », www.numberworld.org
  2. ↑ « Google Cloud Topples the Pi Record », www.numberworld.org/, sur numberworld.org.
  3. ↑ « The Pi Record Returns to the Personal Computer », www.numberworld.org/, sur numberworld.org.
  4. ↑ (de) « Pi-Challenge - Weltrekordversuch der FH Graubünden - FH Graubünden », www.fhgr.ch, sur fhgr.ch (consulté le ).
  5. ↑ « Calculating 100 trillion digits of pi on Google Cloud », cloud.google.com (consulté le )
  6. ↑ Yee, « Limping to a new Pi Record of 105 Trillion Digits », NumberWorld.org, sur numberworld.org, (consulté le ).
  7. ↑ Lorenz Milla, « A detailed proof of the Chudnovsky formula with means of basic complex analysis », (arXiv 1809.00533)
  8. ↑ « Y-cruncher - Formulas », www.numberworld.org, sur numberworld.org (consulté le ).