Le « dilemme du fabricant de tables » ou comment calculer juste  

Certaines idées reçues ont la vie dure, en informatique comme ailleurs. L'une d'entre elles porte sur la fiabilité que l'on attribue au calcul sur ordinateur, par rapport au calcul à la main. Calculer sans l'ombre d'une erreur, un jeu d'enfant pour les ordinateurs ? Pas vraiment !

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.

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 .

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

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 dont 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  !

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 cas de la simple précision est suffisamment simple, avec « seulement » 2³² 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 2⁶⁴ 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 : 2^x et log₂ 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 !