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 — par opposition aux nombres « machine » auxquels s'appliquent les opérations fournies par le processeur. La taille dont il est question est le nombre de chiffres utilisés pour représenter le nombre : ainsi, en arithmétique multiprécision, il n'est guère limité que par la mémoire disponible, tandis que les opérations arithmétiques des processeurs usuels portent sur des entiers et des flottants d'un à quelques mots machines[1].

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

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

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

Voir aussi[modifier | modifier le code]