Arithmétique de précision arbitraire

En informatique , l'arithmétique de précision arbitraire , également appelée arithmétique bignum , arithmétique de précision multiple ou parfois arithmétique de précision infinie , indique que les calculs sont effectués sur des nombres dont la précision en chiffres n'est potentiellement limitée que par la mémoire disponible du système hôte. Cela contraste avec l' arithmétique à précision fixe plus rapide que l'on trouve dans la plupart des unités logiques arithmétiques (UAL), qui offrent généralement entre 8 et 64 bits de précision.

Plusieurs langages de programmation modernes ont une prise en charge intégrée des bignums, les nombres entiers et les nombres à virgule flottante de précision arbitraire . Plutôt que de stocker les valeurs sous forme d'un nombre fixe de bits lié à la taille du registre du processeur , ces implémentations utilisent généralement des tableaux de chiffres de longueur variable .

La précision arbitraire est utilisée dans les applications où la vitesse de calcul n'est pas un facteur limitant, ou lorsque des résultats précis avec de très grands nombres sont nécessaires. Il ne faut pas la confondre avec le calcul symbolique fourni par de nombreux systèmes de calcul formel , qui représentent les nombres par des expressions telles que π ·sin(2) et peuvent ainsi représenter n'importe quel nombre calculable avec une précision infinie.

Une application courante est la cryptographie à clé publique , dont les algorithmes utilisent généralement l'arithmétique avec des entiers comportant des centaines de chiffres. Une autre application est dans les situations où des limites artificielles et des dépassements seraient inappropriés. Elle est également utile pour vérifier les résultats de calculs à précision fixe et pour déterminer les valeurs optimales ou quasi optimales des coefficients nécessaires dans les formules, par exemple celui qui apparaît dans l'intégration gaussienne .

L'arithmétique de précision arbitraire est également utilisée pour calculer des constantes mathématiques fondamentales telles que π jusqu'à des millions de chiffres ou plus et pour analyser les propriétés des chaînes de chiffres ou plus généralement pour étudier le comportement précis de fonctions telles que la fonction zêta de Riemann où certaines questions sont difficiles à explorer via des méthodes analytiques. Un autre exemple est le rendu d'images fractales avec un grossissement extrêmement élevé, comme celles trouvées dans l' ensemble de Mandelbrot .

L'arithmétique à précision arbitraire peut également être utilisée pour éviter le dépassement de capacité , qui est une limitation inhérente à l'arithmétique à précision fixe. Similairement à l'affichage du compteur kilométrique d'une automobile qui peut passer de 99999 à 00000, un entier à précision fixe peut présenter un retournement si les nombres deviennent trop grands pour être représentés au niveau de précision fixe. Certains processeurs peuvent plutôt gérer le dépassement de capacité par saturation , ce qui signifie que si un résultat n'est pas représentable, il est remplacé par la valeur représentable la plus proche. (Avec une saturation non signée de 16 bits, l'ajout de tout montant positif à 65535 donnerait 65535.) Certains processeurs peuvent générer une exception si un résultat arithmétique dépasse la précision disponible. Si nécessaire, l'exception peut être interceptée et récupérée, par exemple, l'opération peut être redémarrée dans un logiciel à l'aide d'une arithmétique à précision arbitraire.

Dans de nombreux cas, la tâche ou le programmeur peut garantir que les valeurs entières d'une application spécifique ne deviendront pas suffisamment grandes pour provoquer un dépassement de capacité. De telles garanties peuvent être basées sur des limites pragmatiques : un programme de fréquentation scolaire peut avoir une limite de tâche de 4 000 élèves. Un programmeur peut concevoir le calcul de manière à ce que les résultats intermédiaires restent dans les limites de précision spécifiées.

Certains langages de programmation tels que Lisp , Python , Perl , Haskell , Ruby et Raku utilisent, ou ont la possibilité d'utiliser, des nombres de précision arbitraire pour toutes les opérations arithmétiques sur les entiers. Bien que cela réduise les performances, cela élimine la possibilité de résultats incorrects (ou d'exceptions) dus à un simple dépassement de capacité. Cela permet également de garantir que les résultats arithmétiques seront les mêmes sur toutes les machines, quelle que soit la taille de mot d'une machine particulière . L'utilisation exclusive de nombres de précision arbitraire dans un langage de programmation simplifie également le langage, car un nombre est un nombre et il n'est pas nécessaire que plusieurs types représentent différents niveaux de précision.

L'arithmétique de précision arbitraire est considérablement plus lente que l'arithmétique utilisant des nombres qui tiennent entièrement dans les registres du processeur, car ces derniers sont généralement implémentés dans l'arithmétique matérielle tandis que les premiers doivent être implémentés dans le logiciel. Même si l' ordinateur ne dispose pas de matériel pour certaines opérations (comme la division entière ou toutes les opérations à virgule flottante) et qu'un logiciel est fourni à la place, il utilisera des tailles de nombres étroitement liées aux registres matériels disponibles : un ou deux mots seulement. Il existe des exceptions, comme certaines machines à longueur de mot variable des années 1950 et 1960, notamment les séries IBM 1620 , IBM 1401 et Honeywell 200 , qui pouvaient manipuler des nombres limités uniquement par la mémoire disponible, avec un bit supplémentaire qui délimitait la valeur.

Les nombres peuvent être stockés dans un format à virgule fixe ou dans un format à virgule flottante sous forme de mantisse multipliée par un exposant arbitraire. Cependant, comme la division introduit presque immédiatement des séquences de chiffres qui se répètent à l'infini (comme 4/7 en décimal ou 1/10 en binaire), si cette possibilité se présente, soit la représentation sera tronquée à une taille satisfaisante, soit des nombres rationnels seront utilisés : un grand entier pour le numérateur et pour le dénominateur . Mais même avec le plus grand commun diviseur divisé, l'arithmétique avec des nombres rationnels peut devenir très rapidement difficile à manier : 1/99 − 1/100 = 1/9900, et si 1/101 est ensuite ajouté, le résultat est 10001/999900.

La taille des nombres de précision arbitraire est limitée en pratique par le stockage total disponible et le temps de calcul.

De nombreux algorithmes ont été développés pour effectuer efficacement des opérations arithmétiques sur des nombres stockés avec une précision arbitraire. En particulier, en supposant que N chiffres sont utilisés, des algorithmes ont été conçus pour minimiser la complexité asymptotique pour les nombres N grands .

Les algorithmes les plus simples sont ceux pour l'addition et la soustraction , où l'on ajoute ou soustrait simplement les chiffres en séquence, en reportant si nécessaire, ce qui donne un algorithme O( N ) (voir la notation O majuscule ).

La comparaison est également très simple. Comparez les chiffres de poids fort (ou les mots machine) jusqu'à ce qu'une différence soit trouvée. Il n'est pas nécessaire de comparer le reste des chiffres/mots. Le pire des cas est ( N ) , mais il peut être effectué beaucoup plus rapidement avec des opérandes de même ampleur.

Pour la multiplication , les algorithmes les plus simples utilisés pour multiplier des nombres à la main (comme enseigné à l'école primaire) nécessitent ⁽ N2 ) opérations , mais des algorithmes de multiplication qui atteignent une complexité de O( Nlog ( N )log(log( N ))) ont été conçus, tels que l' algorithme de Schönhage-Strassen , basé sur des transformées de Fourier rapides , et il existe également des algorithmes avec une complexité légèrement inférieure mais avec des performances réelles parfois supérieures pour des nombres N plus petits . La multiplication de Karatsuba est un de ces algorithmes.

Pour la division , voir algorithme de division .

Pour une liste d'algorithmes ainsi que des estimations de complexité, voir complexité computationnelle des opérations mathématiques .

Pour des exemples en assembleur x86 , voir les liens externes.

Dans certains langages tels que REXX et ooRexx , la précision de tous les calculs doit être définie avant d'effectuer un calcul. D'autres langages, tels que Python et Ruby , étendent automatiquement la précision pour éviter tout débordement.

Le calcul des factorielles peut facilement produire des nombres très grands. Cela ne pose pas de problème pour leur utilisation dans de nombreuses formules (telles que les séries de Taylor ) car elles apparaissent avec d'autres termes, de sorte que, compte tenu de l'ordre d'évaluation, les valeurs de calcul intermédiaires ne posent pas de problème. Si des valeurs approximatives des nombres factoriels sont souhaitées, l'approximation de Stirling donne de bons résultats en utilisant l'arithmétique à virgule flottante. La plus grande valeur représentable pour une variable entière de taille fixe peut être dépassée même pour des arguments relativement petits, comme le montre le tableau ci-dessous. Même les nombres à virgule flottante sont rapidement dépassés, il peut donc être utile de reformuler les calculs en termes de logarithme du nombre.

Mais si des valeurs exactes pour de grandes factorielles sont souhaitées, alors un logiciel spécial est nécessaire, comme dans le pseudo-code qui suit, qui implémente l'algorithme classique pour calculer 1, 1×2, 1×2×3, 1×2×3×4, etc. les nombres factoriels successifs.

constantes: Limite = 1000 % Chiffres suffisants. Base = 10 % La base de l'arithmétique simulée. FactorialLimit = 365 % Nombre cible à résoudre, 365 ! tdigit : Tableau[0:9] de caractères = ["0","1","2","3","4","5","6","7","8","9"] variables: digit: Tableau[1:Limit] de 0..9 % Le grand nombre. carry, d: Entier % Assistants pendant la multiplication. last: Entier % Index dans les chiffres du grand nombre. text: Tableau[1:Limit] de caractère % Bloc-notes pour la sortie. digit[*] := 0 % Efface tout le tableau. last := 1 % Le grand nombre commence par un seul chiffre, digit[1] := 1 % son seul chiffre est 1.
pour n := 1 à FactorialLimit : % Procédez par étapes pour produire 1!, 2!, 3!, 4!, etc. carry := 0 % Commence une multiplication par n. 
pour i := 1 jusqu'à finir : % Avance sur chaque chiffre. d := digit[i] * n + carry % Multiplie un seul chiffre. digit[i] := d mod Base % Conserve le chiffre de poids faible du résultat. carry := d div Base % Reporte au chiffre suivant.
while carry > 0 :  % Stocke le report restant dans le grand nombre. 
if last >= Limit : error("overflow") dernier := dernier + 1 % Un chiffre supplémentaire. chiffre[dernier] := mod de transport Base carry := carry div Base % Supprimez le dernier chiffre de la retenue. text[*] := " " % Préparez maintenant la sortie. 
for i := 1 to last: % Traduire du binaire en texte. text[Limit - i + 1] := tdigit[digit[i]] % Inversion de l'ordre. 
print text[Limit - last + 1:Limit], " = ", n, "!" 

En prenant cet exemple en compte, un certain nombre de détails peuvent être abordés. Le plus important est le choix de la représentation du grand nombre. Dans ce cas, seules des valeurs entières sont nécessaires pour les chiffres, donc un tableau d'entiers à largeur fixe est adéquat. Il est pratique que les éléments successifs du tableau représentent des puissances supérieures de la base.

La deuxième décision la plus importante concerne le choix de la base arithmétique, ici dix. Il y a de nombreuses considérations à prendre en compte. La variable scratchpad d doit pouvoir contenir le résultat d'une multiplication à un seul chiffre plus la retenue de la multiplication du chiffre précédent. En base dix, un entier de seize bits est certainement adéquat car il permet jusqu'à 32767. Cependant, cet exemple triche, dans la mesure où la valeur de n n'est pas elle-même limitée à un seul chiffre. Cela a pour conséquence que la méthode échouera pour n > 3200 environ. Dans une implémentation plus générale, n utiliserait également une représentation à plusieurs chiffres. Une deuxième conséquence du raccourci est qu'une fois la multiplication à plusieurs chiffres terminée, la dernière valeur de retenue peut devoir être reportée sur plusieurs chiffres d'ordre supérieur, et pas seulement sur un seul.

Il y a aussi le problème de l'impression du résultat en base dix, pour une considération humaine. Comme la base est déjà dix, le résultat pourrait être affiché simplement en imprimant les chiffres successifs du tableau digit , mais ils apparaîtraient avec le chiffre d'ordre le plus élevé en dernier (de sorte que 123 apparaîtrait comme "321"). L'ensemble du tableau pourrait être imprimé dans l'ordre inverse, mais cela présenterait le nombre avec des zéros non significatifs ("00000...000123"), ce qui peut ne pas être apprécié, donc cette implémentation construit la représentation dans une variable texte avec des espaces, puis l'imprime. Les premiers résultats (avec un espacement tous les cinq chiffres et une annotation ajoutée ici) sont :

Cette implémentation pourrait utiliser plus efficacement l'arithmétique intégrée de l'ordinateur. Une escalade simple consisterait à utiliser la base 100 (avec des modifications correspondantes au processus de traduction pour la sortie), ou, avec des variables informatiques suffisamment larges (comme des entiers 32 bits), nous pourrions utiliser des bases plus grandes, comme 10 000. Travailler dans une base de puissance de 2 plus proche des opérations d'entiers intégrées de l'ordinateur offre des avantages, bien que la conversion vers une base décimale pour la sortie devienne plus difficile. Sur les ordinateurs modernes typiques, les additions et les multiplications prennent un temps constant indépendamment des valeurs des opérandes (tant que les opérandes tiennent dans des mots machine uniques), il y a donc de gros gains à regrouper autant d'un grand nombre que possible dans chaque élément du tableau de chiffres. L'ordinateur peut également offrir des fonctionnalités pour diviser un produit en un chiffre et le reporter sans nécessiter les deux opérations mod et div comme dans l'exemple, et presque toutes les unités arithmétiques fournissent un indicateur de report qui peut être exploité dans l'addition et la soustraction à précision multiple. Ce genre de détail est le nerf de la guerre des programmeurs de code machine, et une routine bignumber en langage assembleur appropriée peut s'exécuter plus rapidement que le résultat de la compilation d'un langage de haut niveau, qui ne fournit pas d'accès direct à de telles fonctionnalités mais mappe plutôt les instructions de haut niveau à son modèle de la machine cible à l'aide d'un compilateur optimisant.

Pour une multiplication à un seul chiffre, les variables de travail doivent pouvoir contenir la valeur (base−1) ² + retenue, où la valeur maximale de la retenue est (base−1). De même, les variables utilisées pour indexer le tableau de chiffres sont elles-mêmes limitées en largeur. Une façon simple d'étendre les indices serait de traiter les chiffres du grand nombre en blocs de taille pratique de sorte que l'adressage se fasse via (bloc i , chiffre j ) où i et j seraient de petits entiers, ou bien, on pourrait passer à l'utilisation de techniques de grand nombre pour les variables d'indexation. En fin de compte, la capacité de stockage de la machine et le temps d'exécution imposent des limites à la taille du problème.

Le premier ordinateur professionnel d'IBM, l' IBM 702 (une machine à tubes à vide ) du milieu des années 1950, implémentait l'arithmétique entière entièrement au niveau matériel sur des chaînes de chiffres de n'importe quelle longueur comprise entre 1 et 511 chiffres. La première implémentation logicielle répandue de l'arithmétique à précision arbitraire était probablement celle de Maclisp . Plus tard, vers 1980, les systèmes d'exploitation VAX/VMS et VM/CMS ont offert des fonctionnalités bignum sous forme d'un ensemble de fonctions de chaîne dans un cas et dans les langages EXEC 2 et REXX dans l'autre.

Une première implémentation à grande échelle fut disponible via l' IBM 1620 de 1959-1970. Le 1620 était une machine à chiffres décimaux qui utilisait des transistors discrets, mais il disposait d'un matériel (qui utilisait des tables de recherche ) pour effectuer des opérations arithmétiques sur des chaînes de chiffres d'une longueur pouvant aller de deux à n'importe quelle mémoire disponible. Pour l'arithmétique à virgule flottante, la mantisse était limitée à cent chiffres ou moins, et l'exposant était limité à deux chiffres seulement. La plus grande mémoire fournie offrait 60 000 chiffres, mais les compilateurs Fortran pour le 1620 se sont contentés de tailles fixes telles que 10, bien qu'elles puissent être spécifiées sur une carte de contrôle si la valeur par défaut n'était pas satisfaisante.

Dans la plupart des logiciels informatiques, l'arithmétique de précision arbitraire est implémentée en appelant une bibliothèque externe qui fournit des types de données et des sous-routines pour stocker des nombres avec la précision demandée et pour effectuer des calculs.

Les différentes bibliothèques ont différentes façons de représenter les nombres de précision arbitraire. Certaines bibliothèques fonctionnent uniquement avec des nombres entiers, d'autres stockent des nombres à virgule flottante dans diverses bases (puissances décimales ou binaires). Plutôt que de représenter un nombre sous forme de valeur unique, certaines stockent les nombres sous forme de paire numérateur/dénominateur ( rationnels ) et certaines peuvent représenter entièrement des nombres calculables , mais seulement jusqu'à une certaine limite de stockage. Fondamentalement, les machines de Turing ne peuvent pas représenter tous les nombres réels , car la cardinalité de dépasse la cardinalité de .