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 de chiffres de π en , de chiffres en , de chiffres en , de chiffres en . – , de chiffres le , de chiffres le , de chiffres le , et de chiffres le ..
Algorithme 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 .
Optimisations La technique d'optimisation utilisée pour les calculs du record du monde est appelée division binaire.
Fractionnement 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 , 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 , doncSoit 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
Construction de la récursion Si
Code Python 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
Voir aussi
Série Ramanujan-Sato Formule Bailey – Borwein – Plouffe L'algorithme de Borwein Approximations de π
Références
Catégorie:Algorithme