Il est très difficile d’écrire un très gros programme informatique sans laisser au moins une erreur à l’intérieur. Heureusement, les erreurs sont souvent soit facilement détec­ta­bles (et donc vite corrigées), soit peu dange­reuses. Il arrive hélas parfois qu’une erreur pouvant avoir des conséquences graves passe inaperçue lors des tests du programme. Ceci peut être particulièrement préoccupant lorsque l’erreur est localisée dans l’un des programmes ou des circuits qui effectuent les opérations arithmétiques en machine : en effet, ces programmes ou ces circuits sont utilisés très souvent, par de nombreux logiciels, et parfois dans ce qu’on appelle des applica­tions « critiques », comme le contrôle d’un véhicule ou d’un processus potentiellement dangereux. Bien entendu, les erreurs dangereuses ne sont pas toutes arithmétiques, mais c’est sur celles-ci que nous nous concentrerons.

Donnons quelques exemples particulièrement frappants d’erreurs récentes en arithmétique des ordinateurs.

• Dans la version 6.0 du système de calcul formel Maple, si on entrait :

21474836480413647819643794

la « quantité » affichée et mémorisée était :

413647819643790)+’—.(—.(

• L’opérateur de division de la première version du processeur Pentium d’Intel donnait parfois des résultats incor­rects. Par exemple le calcul de

8391667/12582905

donnait 0.666869... au lieu de 0.666910... Ce problème a fait couler beaucoup d’encre en 1994. Il ne semble toutefois pas qu’il ait eu des consé­quences graves… autrement que, peut-être, pour la carrière de l’ingé­nieur qui a commis la bévue.

• En 1998, à bord du navire lance-missiles américain USS Yorktown, un membre de l’équipage a par erreur tapé un « zéro » sur un clavier, au lieu d’une valeur non nulle. Ceci a provoqué une division par zéro. C’est d’habitude un problème bénin, mais visiblement le programmeur de l’ap­pli­cation utilisée n’avait pas songé que ce problème pourrait arriver. Il s’en est suivi une cascade d’erreurs qui a fini par entraîner l’arrêt du système de propulsion du bateau.

Il y a de nombreux autres exemples de systèmes donnant des résultats incorrects à cause d’une mauvaise implantation de l’arithmétique. Ne paniquons pas : de tels problèmes restent rares. Ils ne le sont toutefois pas assez pour que l’on puisse complètement les négliger.

Il arrive que des erreurs proviennent d’une mauvaise spécification : les diverses équipes travaillant sur un même projet, ou encore le concepteur et l’utilisateur d’un programme ne se sont pas suffisamment mis d’accord sur ce que doit faire exactement le programme. Par exemple, 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).

Même lorsque le système informatique n’est pas en cause, certains calculs sont intrinsèquement difficiles et conduiront à des er­reurs, même sur des machines irréprochables.

Considérons la suite de nombres 3/2, 5/3, 9/5, 17/9, etc., où chaque nouveau terme se calcule comme suit :

• on appelle $x$ l’avant-dernière valeur calculée, et $y$ la dernière ;
• le nouveau terme vaut
  \[ 2003 - \frac{6002}{y} + \frac{4000}{xy}. \]

Par exemple, si on veut calculer le terme qui vient après $17/9$, on pose $x = 9/5$, $y = 17/9$, et on trouve aisément
\[ 2003 - \frac{6002}{y} + \frac{4000}{xy} = 33/17. \]

Cette suite de nombres tend vers 2 (ce qui veut dire que les termes $u_n$ 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).

\[ \begin{array}{lll} n & \mbox{Valeur calculée} & \mbox{Valeur exacte} \\ 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 \\ \end{array} \]

En annexe, le lecteur matheux trouvera une explication de ce comportement étrange.

La virgule flottante

La plupart des systèmes informatiques repré­sentent les nombres réels dans le format « virgule flottante ».
Ce format est très proche de la « notation scientifique » des calculatrices. L’idée est la suivante : on utilisera une base $B$ (qui vaut 2 sur la plupart des ordinateurs [1]), et plutôt que de représenter un très petit nombre avec beaucoup de zéros à gauche ou un très grand nombre avec beaucoup de zéros à droite, on préfère représenter les nombres à l’aide d’un signe, d’une mantisse (qui est un nombre réel compris entre 1 et $B$) et un exposant (qui est un nombre entier). Le nombre représenté est égal à la mantisse fois $B$ puissance l’exposant. Par exemple en base 10 la masse de l’électron vaut
$9,109381 \times 10^{-31}$ Kg. Le signe est positif, la mantisse est 9,109381 et l’exposant est –31. Cette représentation est bien plus commode que

0,0000000000000000000000000000009109381

En base 2, le nombre $\pi$ s’écrit
\[1,100100100001111110\cdots \times 2^1\]
La mantisse est $1,100100100001111110\cdots$ et l’exposant est 1.

Comme nous l’avons dit auparavant, nos ordinateurs, à de rares exceptions près, représentent les nombres en base 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 (voir photo [2]), construite à une cinquantaine d’exem­plaires dans les années 60, qui utilisait la base 3. Des informations sur cette machine peu­vent être trouvées sur Internet.

Le lecteur qui voudrait connaître la base utilisée par sa machine peut le faire en utilisant le programme décrit ci-dessous.

Programme de calcul de la base utilisée de manière interne par un système. Ce programme, inventé par Malcolm, nécessite que les variables $A$ et $B$ soient représentées en virgule flottante (le type real ou float des langages de programmation courants). Le symbole « $\leftarrow$ » représente l’affectation (le « = » du langage C, ou le « := » de Pascal ou Maple).

$A \leftarrow 1$ ;

$B \leftarrow 1$ ;

Tant que $((A+1)-A)-1 = 0$ faire $A \leftarrow 2*A$ ;

Tant que $((A+B)-A)-B \neq 0$ faire $B \leftarrow B+1$ ;

Imprimer $B$.

Le lecteur devinera-t-il comment ce programme fonctionne ?

Une piste pour le lecteur matheux qui voudrait prouver ce programme : si $\beta$ est la base du système virgule flottante utilisé et $p$ le nombre de chiffres de mantisse, montrer qu’à la fin de la première boucle « tant que », $A$ vérifie $\beta^p \leq A < \beta^{p+1}$.

On ne dispose en pratique que d’un nombre fini de chiffres pour représenter les mantisses et les exposants.
Un nombre $x$ est alors écrit en virgule flottante, en base 2 et avec $n$ chiffres de mantisse lorsqu’il est représenté par un signe $s$ (qui vaut +1 ou –1), une mantisse $M$ qui s’écrit $m_0,m_1m_2 \cdots m_{n-1}$ (il y a $n$ chiffres de base 2) et un exposant $E$ qui est un nombre entier tels que
\[ x = s \times M \times 2^E. \]

Les premiers systèmes implantant l’arithmé­tique virgule flottante étaient très divers et en général très mauvais. Il n’était pas rare qu’en une seule opération arithmétique, on perde plusieurs chiffres de précision. Sur certaines machines, une multiplication par 1 pouvait conduire à un dépassement de capacité. Un standard datant de 1985, la norme IEEE 754, est venu mettre bon ordre dans cette pagaille. Il doit beaucoup à l’influence de William Kahan, professeur à l’Université de Californie à Berkeley, qui a obtenu la médaille Turing pour ses travaux sur l’arithmétique virgule flottante. La norme IEEE 754 a été révisée en 2008. Nous utiliserons ici le vocabulaire de la version de 1985 de la norme, qui est mieux connu, pour l’instant, des utilisateurs.

Les deux principaux formats de nombres virgule flottante définis par la norme IEEE 754 sont le format simple précision (pour lequel $n=24$) et le format double précision (pour lequel $n=53$). En comptant les chiffres binaires (appelés bits) utilisés pour représenter le signe et l’exposant, un nombre simple précision est représenté sur 32 bits et un nombre double précision sur 64 bits. Par la suite, un format étant choisi, on appellera nombre machine un nombre exactement représentable dans ce format.

L’arrondi correct

La norme IEEE 754 spécifie en particulier comment doivent être faits les arrondis. En effet, lorsque l’on effectue une opération portant sur des nombres machine (par exemple, une multiplication), il est rare que le résultat exact de l’opération soit égal à un nombre machine. On doit alors l’arrondir, c’est-à-dire fournir un nombre machine proche du résultat exact. Plusieurs stratégies sont alors 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 par défaut), ou le nombre machine immédiatement supérieur au résultat exact (on parle alors d’arrondi par excès). Chacune de ces stratégies s’appelle un mode d’arrondi. La norme IEEE 754 propose 4 modes d’arrondis différents (les trois que nous venons de citer, plus un arrondi vers zéro). L’utilisateur doit en début de calcul en choisir un [3], qui sera appelé mode d’arrondi actif. La 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 ensuite arrondi suivant le mode d’arrondi actif.

Cette propriété est appelée exigence d’arrondi correct. Elle présente de nombreux avantages :

• le comportement d’un programme n’utilisant que les opérations $+$, $-$, $\times$, $\div$, et $\sqrt{}$ est parfaitement prévisible. On peut élaborer des preuves, qui permettent de prédire de manière certaine des propriétés. Un exemple classique (et très utile en pratique) est le lemme de Sterbenz : si $X$ et $Y$ sont des nombres machine positifs tels que $X/2 \leq Y \leq 2X$, alors le calcul de $X-Y$ s’effectue exactement (ce qui signifie que le nombre $X-Y$ est un nombre machine : il n’est pas nécessaire de l’arrondir). Ce résultat est vrai dans n’importe quelle base, dès que l’arithmétique est avec arrondi correct. Plusieurs chercheurs (dont John Harrison d’Intel, et Sylvie Boldo et Guillaume Melquiond, de l’INRIA) travaillent activement sur la preuve formelle de programmes utili­sant l’arithmétique virgule flot­tante. Ce travail pionnier devrait permettre de garantir le bon comportement de parties critiques d’un programme numérique. La preuve formelle est également le seul moyen de garantir qu’un opérateur arithmétique (par exemple un diviseur) fait bien ce que l’on souhaite.

• La définition des opérations arithmé­tiques étant indépendante de la ma­chine utilisée, si deux machines diffé­rentes effectuent le même calcul sans changer l’ordre des opérations, elles obtiendront le même résultat. Ceci facilite grandement ce qu’on appelle la portabilité des programmes (qui est le problème de faire fonction­ner sur une machine donnée un pro­gramme conçu sur une autre machine).

Le dilemme du fabricant de tables

Dans la version de 1985 de la norme IEEE 754, cette exigence d’arrondi correct n’est pas formulée en ce qui concerne les autres fonctions que $+$, $-$, $\times$, $\div$, et $\sqrt{}$. Une conséquence de l’absence de spécification de ces fonctions est que parfois, certains systèmes donnent des résultats étranges lorsqu’on les calcule.

Si ces fonctions n’étaient pas spécifiées, c’est à cause d’une difficulté connue sous le nom de Dilemme du Fabricant de Tables. Essayons de décrire sommairement ce problème.
On s’intéresse à l’évaluation des fonctions dites « élémen­taires » (sinus, exponen­tielle, logarithme, tangente, etc. : ce sont des fonctions très importantes en mathématiques mais il n’est pas nécessaire de les connaître pour comprendre la suite). Cette évaluation ne peut s’ef­fec­tuer qu’en cal­culant une approximation du résultat (à l’exception de cas particuliers comme $\log(1)=0$, on ne peut calculer la valeur exacte). Tout le problème est alors de savoir si en arrondissant l’approximation, on obtiendra le même résultat que celui qu’on aurait en arrondissant la valeur exacte.
Imaginons par exemple une machine fonction­nant 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\cdots \]
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.

Considérons également l’exemple suivant, 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 $x$ qui s’écrit

\[0,011111111001110110011101110011100111010000111101101101\]
en base 2 est égal à

\[0,01111010011001010100000111001100001100010001101001010111111111111111111111111111111111111111111111111111111111111111111100001011101001\cdots \]

dans cette dernière écriture, le chiffre « 1 » apparaît de manière consécutive 66 fois après le 53ème chiffre. Ceci signifie que cette valeur est très proche du nombre machine

\[B = 0,0111101001100101010000011100110 00011000100011010010110\]

Pour pouvoir calculer $\sin x$ en arrondi par défaut sans risquer de se tromper, il faudra faire les calculs intermédiaires avec au moins 120 chiffres dans ce cas-là. Si les calculs inter­médiaires ne se font pas avec suffisamment de précision, l’erreur effectuée lors de l’appro­xi­ma­tion ne permet pas de déterminer si le résul­tat exact est inférieur ou supérieur à $B$. C’est ce problème qu’on appelle le Dilemme du Fabri­cant de Tables, car à l’origine, il s’est posé aux éditeurs de tables de valeurs de fonctions numériques.

Afin de pouvoir écrire un programme efficace de calcul d’une fonction $f$ avec arrondi correct, il faut donc déterminer la précision à laquelle on doit faire les calculs intermédiaires pour être sûr que le Dilemme du Fabricant de Tables ne se produira jamais. Pour les fonctions les plus simples (addition, soustraction, multipli­cation, division et racine carrée) ce problème se résout facilement : c’est pour cela que la version de 1985 de la norme IEEE 754 impose qu’elles doivent être arrondies correctement. Mais ce n’est pas le cas des autres fonctions, plus « compliquées ». Pour ces fonctions, les meilleurs résultats con­nus ne sont pas utilisables aisément : en appliquant un théo­rème de théorie des nombres récent, dû à Yuri Nesterenko (de l’Université de Moscou) et Michel Waldsch­midt (de l’Université Paris 6), on peut prouver que pour arrondir correctement l’exponen­tielle, le logarithme, le sinus ou le cosinus dans le format « double précision », il « suffit » de faire les calculs intermédiaires avec une précision allant de plusieurs millions à plu­sieurs milliards de chiffres. Ceci n’est pas totalement impossible (voir l’annexe), mais le temps de calcul et la consommation mémoire sont évidemment très importants. Et pourtant des argu­ments probabilistes nous permettent d’être presque certains qu’un peu plus d’une centaine de chiffres suffisent.

Explorer 18446744073709551616 cas

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 étant suffisamment simple (il y a « seulement » $2^{32} = 4294967296$ valeurs à tester par fonction, ce qui prend au plus quelques jours), nous nous sommes principalement intéressés à la double précision, d’autant plus que c’est le format le plus utilisé actuellement. Il y a $2^{64} = 18446744073709551616$ nombres machine dans ce format, et tester ces nombres un par un pour chacune des fonctions usuelles (sinus, cosinus, tangente, arctangente, logari­thme, exponen­tielle) demanderait trop de temps (quelques siècles sur un gros réseau de machines actuelles).

L’un d’entre nous, Vincent Lefèvre, a conçu un algorithme pour tester globalement un ensemble de nombres machine sur un petit intervalle, en approchant efficacement 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 quelques années (!) de calcul sur des machines de l’École Nor­ma­le Supérieure de Lyon, cela nous a permis d’obtenir un certain nombre de résultats pour la double précision, dont le « pire cas » donné plus haut, avec notamment des résultats complets pour certaines fonctions (exponen­tielle et logarithme, $2^x$ et $\log_2(x)$).

Les programmes sont actuellement en train d’être améliorés de façon à pouvoir compléter nos résultats en double précision, voire obtenir certains résultats dans le format dit « double précision étendue » (80 bits), pour lequel il y a $1208925819614629174706176$ nombres machine possibles.

Damien Stehlé (du CNRS, actuellement à la Macquarie University et à l’Université de Sydney, en Australie) et Paul Zim­mermann (de l’INRIA), ont récemment mis au point un algorithme basé sur des travaux de Coppersmith, qui sont ordinairement utilisés dans le domaine de la cryptographie. Cet algorithme permet d’obtenir une meilleure complexité théorique que celui de Vincent Lefèvre, ce qui signifie qu’il sera d’autant plus intéressant que la précision est grande. Les résultats déjà obtenus sont prometteurs. Malgré ceci, sauf avancée théorique majeure en théorie des nombres, le cas de la quadruple précision (nombres de 128 bits) semble toujours inaccessible, à cause du trop gros nombre de valeurs à tester. Les meilleurs algorithmes connus demanderaient, sur une machine actuelle, plusieurs milliards d’années.

Conclusion

L’arithmétique de nos machines évolue : bien­tôt toutes les fonctions usuelles (et plus seule­ment les quatre opérations arithmétiques et la racine carrée) pourront être avec « arrondi correct », tout au moins dans les formats « simple précision » et « double précision ». D’ailleurs, en partie suite à nos travaux, la révision de la norme IEEE 754, qui date d’août 2008, recommande maintenant (sans l’imposer toutefois) l’arrondi correct des principales fonctions mathématiques. Nous espérons qu’il en résultera une meilleure qualité et une meilleure portabilité des programmes numé­riques. Et pourtant… les programmes numériques sont de plus en plus gros, conçus par des équipes de plus en plus nombreuses : la probabilité qu’une erreur se glisse quelque part ne peut que croître, sauf peut-être si l’utilisation d’outils de preuve formelle, pour valider des « parties critiques » bien isolées, se généralise. La communauté informatique (et même de manière plus générale une bonne partie de la communauté scientifique) est maintenant confrontée au formidable défi de la complexité : comment comprendre le fonctionnement, comment garantir le bon comportement, d’un dispositif, ou d’un program­me, ou d’une machine composé de milliers (si ce n’est de millions) de parties interagissantes ?