Formule de Brent-Salamin

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La formule de Brent-Salamin est une formule donnant une bonne approximation de pi. La formule fut trouvée indépendamment par Richard Brent (de) et Eugene Salamin (en) en 1976. Elle exploite les liens entre les intégrales elliptiques et la moyenne arithmético-géométrique ; sa démonstration aurait été connue de Gauss, mais la mise en oeuvre d'une telle formule est très difficile sans ordinateur personnel et arithmétique multiprécision. On l'appelle également la méthode de Gauss-Legendre.

Énoncé[modifier | modifier le code]

Posons a_0 = 1 et b_0 = \sqrt{2}/2, et définissons les suites (a_n), (b_n) comme les suites adjacentes qui convergent vers la moyenne arithmético-géométrique de 1 et \sqrt{2}/2 :


a_{n+1} = \frac{a_n+b_n}{2}, \qquad b_{n+1} = \sqrt{a_nb_n}.

On définit également la suite (c_n) par la formule c_n = \sqrt{a_n^2-b_n^2} = c_{n-1}/4a_n. Posons


\pi_n = \frac{2 a_{n+1}^2}{1 - \sum_{k=0}^n 2^k c_k^2}.

Alors la suite (\pi_n) converge par valeurs inférieures vers \pi, et on a


\pi - \pi_n \leq \frac{\pi^2 2^{n+4} e^{-\pi 2^{n+1}}}{\text{AGM}(1, \sqrt{2}/2)^2}

La convergence de cet algorithme est très rapide, puisqu'il s'agit d'une convergence quadratique. Ainsi, le nombre de décimales exacte à une étape est environ le double du nombre de décimales exactes à l'étape suivante. L'algorithme donne successivement 1, 4, 9, 20, 42, 85, 173, 347 et 697 décimales exactes ; seulement 25 itérations sont nécessaires pour calculer une approximation de pi avec 45 millions de décimales[1]. La complexité asymptotique du calcul de P décimales de \pi avec cet algorithme est ainsi de O(\mathcal{M}(P) \log P), avec \mathcal{M}(P) la complexité de la multiplication sur des nombres à P chiffres.


Utilisation dans le calcul de décimales de pi[modifier | modifier le code]

La formule de Brent-Salamin a été utilisée lors de nombreux records de calcul de décimales de pi depuis sa conception, notamment pour les records établis sur supercalculateurs. Le premier record établi à l'aide de cette formule est celui de Yasumasa Kanada, qui obtint plus de 10 millions de décimales en 1982[2] ; Kanada et son équipe obtinrent plusieurs records dans les années 80 à 2000, toujours en utilisant la formule de Brent-Salamin. Le dernier record établi à l'aide de cette formule est celui Daisuke Takahashi et al., qui calculèrent en 2009 plus de 2 756 milliards de décimales à l'aide de la formule de Brent-Salamin en une trentaine d'heures[3]. Les calculs furent vérifiés à l'aide de l'algorithme de Borwein, un algorithme à la convergence quartique. Cet algorithme nécessite des bibliothèques de calcul multi-précision, et demandent beaucoup de mémoire : pour un résultat à précision P, il faut stocker la valeur de a_n, b_n, c_n et \pi_n, soit 4P chiffres sans compter les éventuelles quantités intermédiaires.

Depuis quelques années, les records de calculs de décimales de pi ont été établis par des calculs sur ordinateurs personnels, et avec des méthodes différentes de celle de Brent-Salamin. Le premier record de la sorte est celui de Fabrice Bellard[4] avec 2 699 milliards de décimales ; les records suivants furent établis à l'aide du programme y-cruncher, le dernier étant détenu par "houkouonchi" (13 300 milliards)[5]. Ce programme, ainsi que le record de Fabrice Bellard, utilisent la formule de Chudnowsky, donnée par une série convergeant vers l'inverse de pi. La convergence de cette série est plus lente (vitesse linéaire, environ 14 chiffres par nouveau terme calculé) et la complexité asymptotique de l'évaluation de cette série moins bonne que celle de Brent-Salamin ; cependant, en pratique, l'utilisation du scindage binaire pour sommer cette série est plus rapide, et l'algorithme se prête mieux à des techniques de checkpointing, qui permettent à l'exécution du programme d'être plus résiliente[6].


Références[modifier | modifier le code]

  1. David H. Bailey, Jonathan M. Borwein, Peter B. Borwein, Simon Plouffe, The quest for pi, juin 1996.
  2. Boris Gourévitch, La quête des décimales de pi.
  3. Page personnelle de Daisuke Takahashi
  4. Annonce du record de Fabrice Bellard.
  5. Page de y-cruncher.
  6. Description des avantages et difficultés rencontrées lors du record de 2013.