Arithmétique multiprécision

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é.

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 ${\displaystyle 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 ${\displaystyle M(n)=O(n\log n\log \log n)}$, et l'algorithme de Fürer, qui donne ${\displaystyle 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[2] ; cependant, pour les nombres plus gros (plusieurs dizaines de milliers de mots), il faut bien utiliser l'algorithme de Schönhage-Strassen.

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 ${\displaystyle 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[3].

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

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

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

Si l'on note F(n) le coût de l'évaluation à n chiffres près de la fonction ${\displaystyle f/f'}$, ce qui précède semble donner un algorithme de complexité ${\displaystyle 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[4]. Le coût total est alors

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

Si ${\displaystyle F(n)\geq M(n)}$, cette somme se simplifie et est en réalité en ${\displaystyle 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 ${\displaystyle O(M(n))}$, c'est-à-dire que ces opérations ont le même coût asymptotique que la multiplication[4] ; ce résultat s'obtient en appliquant la méthode de Newton aux fonctions f(x) = x² - z et f(x) = xz - 1.

La moyenne arithmético-géométrique de deux nombres, notée ${\displaystyle {\text{AGM}}(a,b)}$, est définie par une suite qui converge quadratiquement ; c'est-à-dire qu'on peut calculer n chiffres exacts de ${\displaystyle {\text{AGM}}(a,b)}$ en ${\displaystyle 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 ${\displaystyle \pi }$ via un calcul d'AGM, c'est-à-dire en ${\displaystyle O(M(n)\log n)}$ opérations. La seconde fonction est liée à l'AGM par la formule[5] :

${\displaystyle \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 ${\displaystyle \log z}$ en ${\displaystyle O(M(n)\log n)}$ opérations.

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

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é[6]. Sa complexité est au mieux ${\displaystyle 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.