Arithmétique multiprécision

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

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[1], 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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

Article détaillé : Algorithme de 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 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 , et l'algorithme de Fürer, qui donne .

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.

Mise au carré[modifier | modifier le code]

Calculer 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 . 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].

Méthode de Newton[modifier | modifier le code]

Rappelons la méthode de Newton pour calculer un nombre tel que  : elle consiste à générer la suite par la récurrence

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

Si l'on note F(n) le coût de l'évaluation à n chiffres près de la fonction , ce qui précède semble donner un algorithme de complexité pour calculer z à n chiffres près. Mais il est possible de faire mieux : puisqu'on sait que zk n'a que 2k chiffres exacts, il est superflu de calculer zk+1 à n chiffres près. On calcule alors z0 à 1 chiffre près, puis on effectue le calcul de z1 à 2 chiffres près, etc., et zk à 2k 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

avec pour obtenir n chiffres exacts.

Si , cette somme se simplifie et est en réalité en .

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 , 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^2 - z et f(x) = xz - 1.

Méthodes basées sur l'AGM[modifier | modifier le code]

La moyenne arithmético-géométrique de deux nombres, notée , est définie par une suite qui converge quadratiquement ; c'est-à-dire qu'on peut calculer n chiffres exacts de en 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 Pi et le calcul de la fonction logarithme. En effet, pour le premier, l'algorithme de Brent-Salamin permet de calculer n décimales de via un calcul d'AGM, c'est-à-dire en opérations. La seconde fonction est liée à l'AGM par la formule[5] :

ce qui donne une approximation qui permet de calculer en opérations.

On peut ensuite appliquer la méthode de Newton pour calculer la fonction exponentielle en opérations, ce qui donne également des algorithmes pour les fonctions trigonométriques.

Scindage binaire[modifier | modifier le code]

Article détaillé : 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é[6]. Sa complexité est au mieux , 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[modifier | modifier le code]

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[modifier | modifier le code]

  1. Par exemple, en langage C et dans le cas d'une architecture 64 bits, le plus grand entier est le long long int stocké sur 8 octets (valeur maximale de 264, environ 1,8x1019).
  2. Richard Brent, Paul Zimmerman, Modern Computer Arithmetic, Cambridge University Press, 2010 ; figure 1.1, page 12.
  3. Richard Brent, Paul Zimmerman, ibid. ; figure 1.2, page 13.
  4. a et b Richard Brent, Paul Zimmerman, ibid., Chapitre 4.2
  5. Richard Brent, Paul Zimmerman, ibid., Chapitre 4.8
  6. Richard Brent, Paul Zimmerman, ibid., Chapitre 4.9

(en) Donald Knuth, The Art of Computer Programming, vol. 2 : Seminumerical Algorithms (ISBN 0-201-89684-2), Section 4.3.1: The Classical Algorithms

  • Richard Brent, Paul Zimmerman, Modern Computer Arithmetic, Cambridge University Press, 2010. (Chapitres 1 et 4.)

Voir aussi[modifier | modifier le code]