Formule de Brent-Salamin

La formule de Brent-Salamin est une formule donnant une bonne approximation de π. La formule fut trouvée indépendamment par Richard P. Brent 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 œuvre 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é

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_{n}b_{n}}}.$

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

$\pi _{n}={\frac {2a_{n+1}^{2}}{1-\sum _{k=0}^{n}2^{k}c_{k}^{2}}}.$

Alors la suite (π_n) converge par valeurs inférieures vers π, 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 exactes à une étape est environ le double du nombre de décimales exactes à l'étape précédente. 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 π avec 45 millions de décimales. La complexité asymptotique du calcul de P décimales de π 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 π

La formule de Brent-Salamin a été utilisée lors de nombreux records de calcul de décimales de π 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 ; 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. 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 π_n, soit 4P chiffres sans compter les éventuelles quantités intermédiaires.

Depuis quelques années, les records de calculs de décimales de π 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 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), et en janvier 2020 50 trillion de chiffres par Timothy Mullican. 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 π. 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.

Références

• Jonathan M. Borwein, Peter B. Borwein. Pi and the AGM. Wiley, New York, 1987.