Arithmétique multiprécision

L'arithmétique multiprécision désigne l'ensemble des techniques mises en œuvre pour manipuler dans un programme informatique des nombres (entiers, rationnels, ou flottants principalement) de taille arbitraire. Il s'agit d'une branche de l'arithmétique des ordinateurs.

On oppose l'arithmétique multi-précision à l'arithmétique en simple ou double précision, comme celle spécifiée par le standard IEEE 754 pour les nombres flottants. En effet, l'arithmétique simple ou double précision ne s'occupe que des nombres de 32 ou 64 bits, pour lesquels les opérations de base sont fournies par le processeur, alors que l'arithmétique multiprécision s'occupe des opérations sur des quantités de taille (nombre de chiffres) quelconque, pour lesquelles la seule limite est celle de la mémoire disponible.

Complexité des fonctions standard

De nombreux algorithmes ont été développés pour effectuer efficacement les opérations usuelles sur des nombres comportant un très grand nombre de chiffres ; nous en donnons quelques-uns, ainsi que leurs complexités, qui s'expriment en fonction de n, le nombre de chiffres des quantités manipulées.

Addition et soustraction

L'addition de deux nombres à n chiffres peut se faire en O(n) opérations avec une méthode naïve. Ce coût est asymptotiquement négligeable par rapport aux autres coûts, et est donc fréquemment négligé.

Multiplication

Les algorithmes de multiplication rapide de grands entiers sont au cœur de ce domaine. En effet, de nombreuses opérations plus complexes, à commencer par la division, utilisent la multiplication d'entiers comme brique de base, et l'efficacité des algorithmes utilisés repose de façon essentielle sur celle de la multiplication sous-jacente. On note $M(n)$ le coût de la multiplication de deux nombres à n chiffres.

Plusieurs méthodes améliorent la complexité de cette opération par rapport à la méthode de base ("poser une multiplication"). Les plus avancées sont l'algorithme de Schönhage-Strassen, qui donne $M(n)=O(n\log n\log \log n)$, et l'algorithme de Fürer, qui donne $M(n)=O(n\log n2^{\log ^{*}n})$.

Notons que ces complexités s'entendent asymptotiquement ; dans la pratique, les méthodes les plus simples (et de complexité asymptotique plus élevées) sont les plus rapides sur des petits exemples. Par exemple, la méthode de base est la plus rapide pour les nombres de quelques mots de 32 bits, l'algorithme de Karatsuba est le plus rapide pour les nombres de quelques douzaines de mots, et l'algorithme de Toom-Cook (3-Toom-Cook) est le plus rapide pour les nombres de quelques centaines de mots ; cependant, pour les nombres plus gros (plusieurs dizaines de milliers de mots), il faut bien utiliser l'algorithme de Schönhage-Strassen.

Mise au carré

Calculer a² est en général plus rapide que calculer ab, essentiellement car certaines quantités utilisées dans les algorithmes de multiplication sont simplifiées dans ce cas précis. Notons que le facteur d'accélération est au plus 2 (ie un carré coûte moitié moins qu'un produit), car l'on peut calculer un produit à partir de deux carrés en utilisant la formule $ab={\frac {(a+b)^{2}-(a-b)^{2}}{4}}$. Une bonne approximation est que le coût d'une mise au carré est environ égal à 0.67 fois le coût d'une multiplication.

Méthode de Newton

Rappelons la méthode de Newton pour calculer un nombre $z$ tel que $f(z)=0$ : elle consiste à générer la suite $(z_{k})_{k\in \mathbb {N} }$ par la récurrence

$z_{k+1}=z_{k}-{\frac {f(z_{k})}{f'(z_{k})}}.$

Pourvu que le premier itéré $z_{0}$ soit suffisamment proche d'un zéro $z$ de $f$ où la dérivé $f'(z)$ ne s'annule pas, la suite converge quadratiquement vers ce zéro, ce qui implique que le nombre de chiffres significatifs de $z_{k}$ qui coïncident avec ceux de $z$ (supposé non nul) est doublé à chaque itération asymptotiquement, ou encore que calculer $n$ chiffres de $z$ requiert $\log n$ étapes.

Si l'on note F(n) le coût de l'évaluation à n chiffres près de la fonction $f/f'$, ce qui précède semble donner un algorithme de complexité $O(F(n)\log n)$ pour calculer z à n chiffres près. Mais il est possible de faire mieux : puisqu'on sait que z_k n'a que 2^k chiffres exacts, il est superflu de calculer z_k+1 à n chiffres près. On calcule alors z₀ à 1 chiffre près, puis on effectue le calcul de z₁ à 2 chiffres près, etc., et z_k à 2^k chiffres près. On obtient toujours un résultat correct à la fin, grâce à la propriété d'auto-correction de la méthode de Newton. Le coût total est alors

$F(1)+F(2)+F(4)+...+F(2^{k})$ avec $2^{k}>n$ pour obtenir n chiffres exacts.

Si $F(n)\geq M(n)$, cette somme se simplifie et est en réalité en $O(F(n))$.

La morale est donc qu'utiliser la méthode de Newton en doublant à chaque étape la précision à laquelle on travaille fait que l'algorithme coûte autant (asymptotiquement) que la dernière étape. Une application de ce résultat est qu'une racine carrée et une inversion coûtent $O(M(n))$, c'est-à-dire que ces opérations ont le même coût asymptotique que la multiplication ; ce résultat s'obtient en appliquant la méthode de Newton aux fonctions f(x) = x² - z et f(x) = xz - 1.

Méthodes basées sur l'AGM

La moyenne arithmético-géométrique de deux nombres, notée ${\text{AGM}}(a,b)$, est définie par une suite qui converge quadratiquement ; c'est-à-dire qu'on peut calculer n chiffres exacts de ${\text{AGM}}(a,b)$ en $O(M(n)\log n)$ opérations. Cependant, l'AGM n'étant pas auto-corrective (au contraire de la méthode de Newton), on ne peut pas utiliser le procédé de la section précédente pour abaisser cette complexité.

Deux applications de l'AGM sont le calcul des décimales de π et le calcul de la fonction logarithme. En effet, pour le premier, l'algorithme de Brent-Salamin permet de calculer n décimales de $\pi$ via un calcul d'AGM, c'est-à-dire en $O(M(n)\log n)$ opérations. La seconde fonction est liée à l'AGM par la formule :

$\ln(z)={\frac {\pi }{2{\text{AGM}}\left(1,{\frac {4}{z}}\right)}}\left(1+\left({\frac {1}{x^{2}}}\right)\right)$

ce qui donne une approximation qui permet de calculer $\log z$ en $O(M(n)\log n)$ opérations.

On peut ensuite appliquer la méthode de Newton pour calculer la fonction exponentielle $\exp(z)$ en $O(M(n)\log n)$ opérations, ce qui donne également des algorithmes pour les fonctions trigonométriques.

Scindage binaire

Les algorithmes basés sur l'AGM, bien qu'asymptotiquement rapides, peuvent être relativement inefficaces ; en effet, la constante dans le O est relativement grande. Ainsi, pour des valeurs de n de taille faible voire moyenne, il est préférable d'utiliser la méthode de scindage binaire. Cette méthode permet de calculer certaines séries (dont celles définissant l'exponentielle et les fonctions trigonométriques) en scindant la somme en deux et en appelant la méthode récursivement sur chaque moitié. Sa complexité est au mieux $O(M(n)\log ^{2}n)$, mais la constante dans le O est plus faible que pour les méthodes basées sur l'AGM.

Bibliothèques de calcul multiprécision

Sur le plan technique, diverses bibliothèques fournissent des structures de données et des opérations efficaces pour le calcul multiprécision. Les plus répandues sont probablement GNU MP et GNU MPFR, toutes deux écrites en C. Le langage Java dispose de deux classes pour représenter des nombres arbitrairement grands : BigInteger pour les entiers et BigDecimal pour les nombres décimaux.

Notes et références

• (en) Donald Knuth, The Art of Computer Programming, vol. 2 : Seminumerical Algorithms, Reading (Mass.), Addison-Wesley, 762 p. (ISBN 978-0-201-89684-8, BNF 37532795), Section 4.3.1: The Classical Algorithms
• Richard Brent, Paul Zimmerman, Modern Computer Arithmetic, Cambridge University Press, 2010. (Chapitres 1 et 4.)

Voir aussi

• dc (desk calculator), une commande Unix qui permet les calculs avec une précision arbitraire en notation polonaise inverse
• bc, même genre, en notation courante