Algorithme de Chudnovski
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 décembre 2009, 10 000 milliards de chiffres en octobre 2011, 22 400 milliards de chiffres en novembre 2016[1], 31 400 milliards de chiffres en septembre 2018. – janvier 2019[2], 50 000 milliards de chiffres le 29 janvier 2020[3], 62 800 milliards de chiffres le 14 août 2021[4], 100 000 milliards de chiffres le 21 mars 2022[5], et 105 000 milliards de chiffres le 14 mars 2024[6].
Algorithme
[modifier | modifier le code]L'algorithme est basé sur l'opposé du nombre de Heegner , la fonction j , et sur la série hypergéométrique généralisée à convergence rapide ci-dessous: Une preuve détaillée de cette formule peut être trouvée ici :
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 [7].
Optimisations
[modifier | modifier le code]La technique d'optimisation utilisée pour les calculs du record du monde est appelée division binaire.
Fractionnement binaire
[modifier | modifier le code]Un facteur de peut être retiré de la somme et simplifié en
Soit , et en substituant dans la somme. peut être simplifié en , donc par définition de , doncCette définition de n'est pas défini pour , on calcule donc le premier terme de la somme et l'ajoute à la nouvelle définition de en partant de Soit et , doncLaisser et est une limite qui ne peut être qu'approché, on calcule à la place et lorsque se rapproches de , l'approximation de l'approximation s'améliore.Par définition originale de ,
Calcul récursif des fonctions
[modifier | modifier le code]Construction de la récursion
[modifier | modifier le code]Si
Code Python
[modifier | modifier le code]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 | modifier le code]Voir aussi
[modifier | modifier le code]- Série Ramanujan-Sato
- Formule Bailey – Borwein – Plouffe
- L'algorithme de Borwein
- Approximations de π
Références
[modifier | modifier le code]- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Chudnovsky algorithm » (voir la liste des auteurs).
- « 22.4 Trillion Digits of Pi », www.numberworld.org
- « Google Cloud Topples the Pi Record », www.numberworld.org/
- « The Pi Record Returns to the Personal Computer », www.numberworld.org/
- « Pi-Challenge - Weltrekordversuch der FH Graubünden - FH Graubünden », www.fhgr.ch (consulté le )
- « Calculating 100 trillion digits of pi on Google Cloud », cloud.google.com (consulté le )
- Yee, « Limping to a new Pi Record of 105 Trillion Digits », NumberWorld.org, (consulté le )
- « y-cruncher - Formulas », www.numberworld.org (consulté le )