Le « dilemme du fabricant de tables » ou comment calculer juste
L’arithmétique virgule flottante est en fait un jeu fort complexe, où les sources d’erreurs se multiplient à l’envi. Pourtant, un calcul fiable est indispensable pour garantir le bon comportement d’un dispositif, d’un programme ou d’une machine, pour assurer la qualité d’un système informatique, et pour une ribambelle d’applications avides de calcul en temps réel. Parmi elles, le contrôle d’un véhicule, d’un avion, d’un satellite, d’un missile, d’un processus dangereux, d’un système complexe constitué de milliers de parties interagissantes.
La plupart des systèmes informatiques représentent les nombres réels dans le format« virgule flottante ». L’ordinateur manipule en effet des quantités finies, et pour le calcul numérique, on est obligé de manipuler les réels de manière approchée. Un nombre non nul est représenté à l’aide d’un signe, d’une mantisse (un nombre réel compris entre 1 et B, B étant la base) et d’un exposant. Pour la quasi totalité des ordinateurs actuels, la base est 2 (les seuls chiffres utilisés sont 0 et 1).
La plupart des calculatrices de poche (ainsi que le logiciel Maple) utilisent toutefois la base 10, et il a même existé une machine russe, la machine SETUN, construite à une cinquantaine d’exemplaires dans les années 60, qui utilisait la base 3.
Des information, en anglais, sur cette machine, peuvent être trouvées ici.
Le format virgule flottante permet de représenter une plage de valeurs très grande, aussi bien de très petits que de très grands nombres. Il simplifie les calculs internes pour l’ensemble des opérations.
Par exemple :
• En base 10, la masse de l’électron vaut 9,109381 x 10-31 kg. Le signe est positif, la mantisse est 9,109381 et l’exposant est – 31. Une représentation bien plus commode qu’une ribambelle de 31 zéros.
• En base 2, le nombre π s’écrit : 1,100100100001111110… x 21
La mantisse est 1,100100100001111110… et l’exposant est 1.
L’erreur est-elle humaine ?
De l’implémentation de l’arithmétique dans les programmes ou les circuits à la spécification même des tâches, les sources d’erreur sont multiples. C’est ainsi que la sonde Mars Climate Orbiter s’est écrasée sur Mars en septembre 1999 à cause d’une étourderie ahurissante : une partie des concepteurs des logiciels supposait que l’unité de mesure était le mètre, et l’autre partie que c’était le pied (l’unité anglaise). Souvenons-nous aussi du fameux bug du Pentium. Hélas, même avec un système informatique irréprochable, la plupart des calculs conduisent inévitablement à des erreurs, heureusement repérables dans la majorité des cas. En effet, le résultat d’une opération sur ordinateur ne peut presque jamais être représenté exactement. Les nombres représentables exactement, qui forment un sous-ensemble des nombres rationnels, sont appelés nombres machine. Tous les autres doivent être arrondis, c’est-à-dire fournir un nombre machine proche du résultat exact. Une succession d’arrondis peut conduire à des résultats extravagants.
Considérons la suite de nombres u0, u1, u2… définie par :
u0 = 3/2 = 1,5
u1 = 5/3 = 1,6666666…
un+1 = 2003 – 6002/un + 4000/un un-1
La suite tend vers 2 (ce qui veut dire que les termes un s’approchent de plus en plus de 2 lorsque n croît). Pourtant si on calcule ces termes sur n’importe quel ordinateur (sauf avec un système qui fait du calcul exact avec des nombres rationnels), on aura l’impression qu’elle tend vers 2000.
Par exemple, la table suivante montre ce qu’on obtient avec une arithmétique virgule flottante de base 10 avec une précision de 10 chiffres (comme celle d’une calculette, par exemple).
| n | Valeur calculée | Valeur exacte arrondie |
| 2 | 1,800001 | 1,800000000 |
| 3 | 1,890000 | 1,888888889 |
| 4 | 3,116924 | 1,941176471 |
| 5 | 756,3870306 | 1,969696970 |
| 6 | 1996,761549 | 1,984615385 |
| 7 | 1999,996781 | 1,992248062 |
| 8 | 1999,999997 | 1,996108949 |
| 9 | 2000,000000 | 1,998050682 |
| 10 | 2000,000000 | 1,999024390 |
Plusieurs modes d’arrondis sont possibles : on peut chercher à fournir le nombre machine le plus proche du résultat exact, (on parle alors d’arrondi au plus près), ou le nombre machine immédiatement inférieur au résultat exact (on parle alors d’arrondi vers -∞), ou le nombre machine immédiatement supérieur au résultat exact (on parle alors d’arrondi vers +∞), ou enfin un arrondi vers zéro. Avant une série d’opérations, un mode d’arrondi est choisi une fois pour toutes, c’est le mode d’arrondi actif.
Avec une norme, tous égaux devant le calcul !
À la fin des années soixante-dix, chaque ordinateur avait sa propre représentation interne pour les nombres à virgule flottante. Or l’arithmétique à virgule flottante possède des subtilités et des difficultés inégalement maîtrisées par un constructeur moyen. Il arrivait qu’en une seule opération arithmétique, on perde plusieurs chiffres de précision. Sur certaines machines, une simple multiplication par 1 pouvait conduire à un dépassement de capacité ! Pour remédier à cette situation, l’IEEE a proposé en 1985 un standard, la norme IEEE 754.
La norme proposée en 1985 par l’IEEE doit beaucoup à l’influence de William Kahan, professeur à l’Université de Californie à Berkeley. Ce dernier a d’ailleurs obtenu en 1989 la Médaille Turing, la plus haute récompense décernée à un informaticien, à l’instar du Prix Nobel ou de la Médaille Fields pour les mathématiques.
Cette norme permet les échanges de données en virgule flottante entre ordinateurs, et fournit aussi un modèle rodé aux constructeurs qui élaborent des processeurs ou des coprocesseurs dédiés qui effectuent des calculs en virgule flottante.
Le standard IEEE 754 définit quatre formats, dont trois utilisés en pratique :
• simple précision sur 32 bits
• double précision sur 64 bits, le format le plus utilisé actuellement
et les deux formats étendus,
• le format étendu simple précision qui n’est quasiment plus utilisé,
• et le format étendu double précision sur 80 bits. Ce format est utilisé en interne par les processeurs, pour minimiser les erreurs d’arrondi.
(Plus d’informations ici, en anglais, sur la norme et les formats.)
Cette norme exige que pour les quatre opérations arithmétiques (addition, soustraction, multiplication et division) et la racine carrée, le système se comporte comme si le résultat d’une opération était calculé exactement, puis arrondi selon le mode d’arrondi actif.
Cette exigence, appelée arrondi exact, comporte de nombreux avantages : les résultats sont plus précis, les logiciels plus facilement portables (de l’ordinateur de développement aux ordinateurs grand public), des propriétés mathématiques sont préservées, on peut construire et prouver des algorithmes utilisant ces propriétés, tenir des raisonnements théoriques et obtenir des encadrements certains de résultats.
Le dilemme du fabricant de tables
Mais la norme IEEE 754 n’avance aucune spécification sur les fonctions élémentaires (sinus, tangente, exponentielle, logarithme…), pour cause de complexité. Leur évaluation ne peut s’effectuer qu’en calculant une approximation du résultat (à l’exception de cas particuliers comme log(1) = 0).
Table de logarithmes.
Extrait du fascicule de Bouvart et Ratinet, édité en 1957.
Les chercheurs du domaine de l’arithmétique des ordinateurs développent des stratégies pour garantir l’arrondi exact des fonctions élémentaires avec un coût de calcul raisonnable. Ils relèvent ainsi un défi majeur de l’arithmétique des ordinateurs connu sous le nom du « dilemme du fabricant de tables », car à l’origine, le problème s’est posé aux éditeurs de tables de valeurs de fonctions numériques.
Voici, en substance, le casse-tête. Le résultat d’une fonction élémentaire peut être a priori très proche d’un nombre machine ou du milieu de deux nombres machine consécutifs, et si les calculs intermédiaires ne sont pas effectués avec suffisamment de précision, on ne saura pas comment arrondir. Il faut donc définir la précision nécessaire aux calculs intermédiaires pour que le « dilemme du fabricant de tables » ne se produise jamais. Mais cette précision est souvent difficile à obtenir !
Imaginons par exemple une machine fonctionnant en base dix (B = 10), avec des mantisses de 6 chiffres, et supposons que l’on veuille arrondir au plus près. On cherche le sinus du nombre machine 2,18998. Ce sinus vaut 0,81435250000019… Il est donc presque égal au milieu des nombres machine x = 0,814352 et y = 0,814353. Pour savoir si on doit retourner x ou y comme résultat du calcul, il faut calculer ce sinus avec une précision d’environ 13 chiffres.
Autre exemple :
En base 2, avec une mantisse sur 53 chiffres (ceci correspond à la double précision de la norme IEEE 754), le sinus du nombre machine z qui s’écrit 0,011111111001110110011101110011100111010000111101101101
est égal à 0,01111010011001010100000111001100001100010001101001010
111111111111111111111111111111111111111111111111111111111111111111100001011101001…
Dans cette dernière écriture, le bit « 1 » apparaît de manière consécutive 66 fois après le 53ème bit. Ceci signifie que cette valeur est très proche du nombre machine Z = 0,011110100110010101000001110011000011000100011010010110
Pour pouvoir calculer sin x en arrondi vers moins l’infini sans risquer de se tromper, il faudra faire les calculs intermédiaires avec au moins 120 chiffres dans ce cas-là. Si les calculs intermédiaires ne se font pas avec suffisamment de précision, l’erreur effectuée lors de l’approximation ne permet pas de déterminer si le résultat exact est inférieur ou supérieur à Z : un plongeon dans le « dilemme du fabricant de tables ».
De quelques siècles à quelques années de calcul
La seule solution connue actuellement pour trouver la précision minimale nécessaire aux calculs intermédiaires consiste à effectuer une recherche exhaustive pour chaque fonction et chaque précision cible. Il faut chercher les « pires cas », c’est-à-dire les nombres machine pour lesquels l’évaluation de la fonction demandera la plus grande précision intermédiaire.
Le pire cas est le nombre flottant le plus difficile à arrondir parce qu’il se trouve le plus près du milieu de deux nombres machine (pour l’arrondi au plus près) ou d’un nombre machine (pour les arrondis vers moins l’infini et vers plus l’infini).
De manière imagée, si on illustre les nombres machine par des poteaux régulièrement espacés, un pire cas pour l’arrondi au plus proche est si près du milieu de deux poteaux qu’il faudrait un mètre d’une précision extrême pour décider de quel poteau il est le plus proche. Pour le pire cas donné précédemment (exemple de sin z), le rapport est d’environ 266, ce qui fait environ 1020. La précision serait donc une fraction de la taille d’un proton…
Le cas de la simple précision est suffisamment simple, avec « seulement » 232 c’est-à-dire 4294967296 valeurs à tester par fonction, ce qui prend au plus quelques jours ! Mais le format le plus utilisé actuellement est la double précision, qui nécessite de tester 264 valeurs, soit 18446744073709551616 nombres machine. Les tester un par un prendrait quelques siècles sur un gros réseau de machines actuelles !
Un chercheur en arithmétique des ordinateurs, Vincent Lefèvre, a conçu un algorithme pour tester globalement un ensemble de nombres machine sur un petit intervalle, en approchant la courbe de la fonction à tester par un segment de droite et en cherchant une minoration de la distance de ce segment aux sommets d’une grille régulière. Au bout de seulement quelques années (!) de calcul sur des machines de l’École normale supérieure de Lyon, un certain nombre de résultats en double précision ont été trouvés, dont le très recherché « pire cas ». Certaines fonctions (exponentielle et logarithme : 2x et log2 x, log(x) et exp(x)) ont même été entièrement décryptées, ainsi que leurs pires cas. Pour les autres fonctions, les résultats sont restreints à un intervalle.
Prochaines étapes de ces recherches de haut vol : obtenir certains résultats dans le format étendu double précision, pour lequel 1208925819614629174706176 nombres machine doivent être testés !
Newsletter
Le responsable de ce traitement est Inria. En saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles et à ce que vos données soient collectées et stockées comme décrit dans notre politique de confidentialité
Niveau de lecture
Aidez-nous à évaluer le niveau de lecture de ce document.
Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !
