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 en mars 14, 2024[6].
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].
La technique d'optimisation utilisée pour les calculs du record du monde est appelée division binaire.
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
, donc
Cette 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
, donc
Laisser
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
,
Si
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...