Comment l’ordinateur gère t’il les nombres ?

Dans un précédent post, nous avions introduit la problématique des arrondis de calcul et son impact sur les logiciels de simulation, notamment quand ces derniers sont exécutés dans des environnements massivement parallèles. Nous avions alors expliqué brièvement que tous les nombres réels n’étaient pas représentables exactement en machine, et que de fait, il était primordial de s’assurer de la qualité et de la validité des résultats produits par les chaines de traitements numériques. Dans cet article, nous présentons l’arithmétique des ordinateurs de manière plus détaillée.

Arithmétique Flottante IEEE 754 

Les problèmes numériques présentés dans le post précédent ne constituent pas une véritable surprise. N’importe quelle donnée est représentée sur un ordinateur par un nombre fini N de bits. La valeur d’un bit est soit 1 soit 0 ; une donnée représentée sur N bits ne pourra prendre alors que 2N valeurs possibles, le nombre N de bits dépendant du processeur utilisé et du type de donnée. Cette forme de représentation entraîne une limitation dès lors des calculs numériques sur les nombres réels.  En fait, ce type de représentation équivaut à un passage d’un ensemble de nombres réels ℝ (ensemble continu) vers l’ensemble des nombres flottants F  (ensemble fini). En d’autres termes, les algorithmes que nous implémentons sur ordinateur sont initialement conçus pour les nombres réels, mais sont exécutés avec des nombres flottants.

RversF

Le calcul sur ordinateur est donc assez différent du calcul mathématique qu’il est sensé représenté. Pour harmoniser les résultats, les concepteurs de machines et des langages informatiques ont dû faire des choix sur la représentation des nombres réels et la manière dont ils seront manipulés. C’est ainsi qu’ils ont introduit la norme IEEE 754, qui est le standard utilisé de nos jours pour la représentation flottante. Il importe alors, avant de concevoir toute chaine de calcul numérique, de s’interroger sur la façon dont tout ordinateur moderne gère le passage  des nombres réels ℝ vers les nombres flottants F. David Golberg s’était penché longuement sur la question dans son célèbre article intitulé “What every computer scientist should know about floating-point arithmetic”.

La représentation flottante 

L’arithmétique des nombres réels sur ordinateur est dite arithmétique à virgule flottante. Un nombre x est représenté en virgule flottante en base β >1 par un triplé (s, m, e) tel que :  x = (-1)s × m × βe

  • s  {0, 1} est son signe (0 pour le positif, 1 pour le négatif) ;
  • m est sa mantisse en base β représentée sous la forme d0.d1d2…dp−1 et p la précision telle que  0 ≤  di <β et donc 0 ≤  m <β
  •  e son exposant, un entier compris entre emin et emax.

Par exemple en base 10, le nombre 1234,56 peut être représenté  comme  x = (-1)0 × 1,23456 × 103 tel que  s = 0, m = 1,23456 et e = 3.

La norme IEEE 754

Pendant longtemps, les représentations avaient un même principe général mais différaient dans le détail des choix selon la taille de mantisse, la base utilisée et la plage d’exposant couverte. Le résultat d’une opération arithmétique différait alors suivant l’ordinateur ou le langage utilisé. Pour harmoniser les résultats, la norme IEEE 754 a été introduite en 1985 (ANSI/IEEE) puis révisée en 2008 (IEEE Computer Society). Cette norme fixe la représentation des nombres et le comportement des opérations élémentaires pour l’arithmétique à virgule flottante. La norme définit également les formats des données, les valeurs spéciales, les modes d’arrondi, la précision des opérations de base et les règles de conversion. Elle a pour objectifs de permettre la conception de programmes portables, de rendre les programmes déterministes d’une machine à une autre, de conserver des propriétés mathématiques et de gérer correctement les arrondis et les conversions.

La norme définit cinq formats de base pour la représentation des flottants :

  • en représentation binaire (β = 2) binary32, binary64, binary128 sur respectivement 32, 64et 128 bits ;
  • en représentation décimale (β = 10) decimal64, decimal128.

A ces formats, s’ajoutent le binary16 (précision moitié) et decimal32 qui sont considérés comme des « formats d’échange » (interchange format). Le Tableau 1 récapitule la spécification des trois principaux formats binaires. Tous les formats (binaire et décimal) sont présentés dans le document officiel de la norme.

Tableau 1 Les trois principaux formats IEEE 754

Format

Appellation

Répartition des bits

Signe + mantisse + exposant

emin

emax

binary32

Simple précision

1+23+8

-126

127

binary64

Double précision

1+52+11

−1022

1023

binary128

Quadruple précision

1+112+15

−16382

16383

Malgré l’existence de cette norme, il est impossible de représenter exactement tous les nombres réels sur ordinateur. Si x et y sont deux nombres représentables en machine, alors le résultat d’une opération entre x et y n’est, en général, pas représentable en machine. On utilise alors une valeur approchée (un arrondi) c’est à dire renvoyer vers un des nombres représentables voisins. L’utilisation de l’arrondi de calcul introduit alors une incertitude dont la propagation peut être source de résultats erronés. Le standard IEEE 754 spécifie quatre modes d’arrondi :

  • Arrondi vers + ∞: RU(x)
  • Arrondi  vers −∞ : RD(x)
  • Arrondi vers 0 : RZ(x)
  • Arrondi au plus près : RN(x) le nombre est arrondi à la valeur la plus proche. C’est le mode d’arrondi par défaut.

Les arrondis vers ±∞ ou 0 sont dits arrondis dirigés car ils sont dirigés dans une direction donnée. Une conséquence des différents modes d’arrondis est qu’une fois le mode choisi, le résultat d’une opération est parfaitement spécifié. On parle alors d’arrondi correct. La norme IEEE 754 impose l’arrondi correct pour les 4 opérations de base (addition, soustraction, multiplication, division) ainsi que pour la racine carrée. Il est difficile d’obtenir l’arrondi correct pour les autres fonctions mathématiques (cos, sin, log, exp, etc). Pour ces fonctions, la norme n’impose rien. Dans ces cas, si y est le résultat exact recherché, on retourne soit RD(y) soit RU(y). On parle de résultat fidèle (faithful result ou faithful rounding). Il est intéressant de lire à ce sujet, le chapitre 3 de (De Dinechin) qui est consacré à l’arrondi correct dans la bibliothèque mathématique.

Quelles conséquences pour la qualité numérique des résultats ?

La qualité d’un résultat est généralement confondue avec la précision de celui-ci. Cependant, il convient de distinguer la précision d’un résultat (accuracy en anglais) calculé de la précision de calcul (precision en anglais) :

  • La précision d’un résultat fait référence à l’erreur (relative ou absolue) commise pendant l’approximation (une suite de calcul) d’une quantité.
  • la précision du calcul désigne l’erreur relative commise pendant une opération arithmétique élémentaire (+,, ×, ÷). En arithmétique flottante, la précision de chaque opération (de fait erreur relative commise) est majorée par l’unité d’arrondi notée u ou eps (machine epsilon). En double précision, eps est égal à eps = 2−53 ≈10−16.

De fait, la précision de calcul (encore appelée précision de travail) est confondue avec l’unité d’arrondi. Le problème majeur du calcul flottant est la propagation des erreurs d’arrondi. A chaque arrondi, on perd a priori un peu de qualité numérique, on parle d’erreur d’arrondi. Même si une opération isolée retourne le meilleur résultat possible, une suite de calculs peut conduire à d’importantes erreurs du fait du cumul des erreurs d’arrondi. Un résultat final d’un calcul comprenant plusieurs opérations peut être éloigné de la valeur exacte, voire de signe contraire.

Les principales sources d’erreurs d’arrondi sont l’élimination catastrophique, l’absorption et l’accumulation des erreurs.

  • L’élimination catastrophique (couramment appelée cancellation) est le principal problème du calcul flottant. Elle arrive au cours de l’évaluation d’une expression impliquant une soustraction, ou l’addition de deux nombres de signes opposés lorsque les deux nombres sont très proches en valeur absolue. Dans ce cas, la plupart des bits de poids forts des opérandes vont s’annuler entre eux. L’ensemble des bits du résultat final peut être sans rapport avec la valeur que l’on souhaite calculer. En d’autres termes, la valeur du résultat étant petite devant les opérandes, si ceux-ci sont eux-mêmes des résultats de calculs avec des erreurs d’arrondi, l’erreur relative commise sur le résultat final est encore plus grande.
  • Le phénomène d’absorption est généralement noté lors de l’addition de deux nombres ayant des ordres de grandeurs très différents. Le résultat de l’addition peut être assez proche du nombre très grand, on perdra donc la trace du plus petit des deux nombres. La combinaison de ces deux phénomènes (élimination catastrophique et absorption) peut tourner à la catastrophe. Par exemple en simple précision, si a = 1 et b = 2−30 alors a + b = 1 et (a + b) − a = 0.  Aussi,  remarquons qu’en modifiant légèrement l’ordre des opérations, on obtient le bon résultat : (a  a) + b = 2−30    …..  
  • La propagation des erreurs est également un problème important. Une erreur commise sur un résultat res, peut entraîner une plus grande erreur quand le dernier résultat res est utilisé dans un nouveau calcul. Lorsque les erreurs du premier ordre sont très significatives, elles peuvent engendrer des erreurs de second ordre énormes.

Théoriquement, ces problèmes entraînent la perte des propriétés algébriques (par exemple la perte de l’associativité) et la perte de la notion d’ensemble continu (les réels sont approchés par un ensemble discret) et ont un impact important sur les résultats des algorithmes numériques.

Conclusion :

La norme IEEE a permis d’harmoniser la gestion des nombres flottants sur  l’ordinateur. Toutefois, comme nous l’avions expliqué pour la gestion des arrondis il ne s’agit que de recommandations. Dans un prochain article, nous nous intéresserons à l’implémentation de la norme sur les processeurs actuels. La perte des propriétés mathématiques que nous introduisons brièvement ici seront également abordés dans un prochain post.

Livres de référence : 

  1. Higham, N. Accuracy and Stability of Numerical Algorithms. second. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2002.
  2. Muller, J-M, et al. Handbook of Floating-Point Arithmetic. Birkhauser Boston, 2010.

Quelques liens pour aller plus loin :

Groupe de travail sur la norme IEEE 754

Willian Kahan « père » de l’IEEE 754

Validlab

Informations sur les différentes implémentations d’IEEE 754 sur diverses plateformes

Convertisseur binaire interactif à précisions simple et double selon la norme IEEE 754

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *