Nathalie Revol, INRIA ;
Fabienne Jézéquel, LIP6.
 
(Cet article fait partie de notre dossier JDEV 2013 : Développer pour calculer)
 
Les grandeurs réelles sont le plus souvent manipulées dans l’ordinateur sous la forme de nombres en virgule flottante. Mais les flottants ne sont qu’une approximation des réels : les identifier aveuglément aux réels expose à des bugs qui peuvent aller bien au-delà de la petite imprécision numérique. A contrario, les flottants ne sont pas responsables de tous les problèmes numériques – contrairement à une légende parfois bien répandue dans la communauté !

L’arithmétique flottante est aujourd’hui standardisée par la norme IEEE-754, adoptée en 1985 et révisée en 2008. Cette norme définit exactement les formats des nombres flottants et le comportement des opérations arithmétiques sur ces nombres. Cependant, quelques comportements inattendus peuvent se produire, imputables à des particularités architecturales, à une certaine “philosophie” des langages de programmation ou à la quête d’optimisation du temps d’exécution par les compilateurs, au détriment de la qualité numérique. Sur la base de ce constat, la session “Précision” avait deux objectifs : identifier et expliquer des comportements surprenants, d’une part, et d’autre part mettre en garde le programmeur, de façon à ce qu’il puisse se prémunir contre les erreurs en les anticipant.

L’atelier qui a précédé l’exposé avait pour but de présenter deux approches permettant soit d’estimer la précision, soit de fournir un encadrement garanti (mais potentiellement trop large) du résultat. Ces outils, utilisés avec discernement, permettent de diagnostiquer et éventuellement de localiser les pertes de précision. Des pistes pour remédier à ces pertes de précision ont été proposées.

L’exemple qui a servi de fil rouge pendant l’atelier est une expression arithmétique conçue pour conduire à des résultats erronés en arithmétique flottante :
(333 + 3/4)*b^6 + a^2*(11*a^2*b^2 – b^6 – 121*b^4 -2) + 11/2*b^8 + a/2b
avec a = 77617.0 et b = 33096.0.

Dans cet exemple dû à S.M. Rump, une évaluation en arithmétique flottante simple précision (où les nombres sont représentés sur 32 bits) fournit la valeur ≈ -2.34 . 10^29. En double précision, c’est-à-dire avec des nombres représentés sur 64 bits, on obtient la valeur -1.10 . 10^21. Avec d’autres parenthésages, sur des architectures différentes, on trouve les valeurs ≈7.09 . 10^29 ou ≈ 1.17 en simple précision. Autrement dit, ni l’ordre de grandeur ni même le signe ne sont connus. En double précision, on retrouve souvent la valeur ≈ 1.17, ce qui semble indiquer qu’il s’agit là d’une bonne approximation de la valeur exacte (cf. listing 1).

Or cette valeur exacte est ≈ -0.82739605994682136814116509547981629 ; aucune des valeurs ci-dessus ne le laissait présager.

Le premier outil présenté pendant l’atelier, CADNA, permet d’étudier et de diagnostiquer la sensibilité numérique d’un calcul. Il met œuvre l’arithmétique stochastique discrète (ASD), méthode automatique d’analyse d’erreur d’arrondi fondée sur une approche probabiliste (cf. listing 2). L’ASD consiste à exécuter un programme plusieurs fois de manière synchrone, en utilisant un mode d’arrondi aléatoire, ce qui permet d’estimer le nombre de chiffres significatifs exacts. En utilisant CADNA, les calculs sont menés en triple, avec un arrondi choisi aléatoirement pour chaque opération. Les chiffres communs aux différents résultats sont considérés comme étant corrects avec une forte probabilité. Dans l’exemple de Rump, CADNA indique à raison que le résultat calculé n’a aucun chiffre correct. CADNA permet ainsi d’estimer la qualité numérique des résultats, de détecter les instabilités numériques générées pendant l’exécution et d’optimiser les critères de convergence des algorithmes itératifs.

Le second outil présenté est MPFI (cf. listing 3). Il s’agit d’une bibliothèque implantant l’arithmétique par intervalles avec une précision de calcul arbitrairement élevée. Le principe de l’arithmétique par intervalles est de remplacer les nombres par des intervalles et de calculer avec ces intervalles. La propriété fondamentale de cette arithmétique est l’inclusion : si les intervalles en entrée contiennent les valeurs exactes des données, alors les résultats calculés sont garantis contenir les valeurs exactes des résultats cherchés.

L’arithmétique par intervalles peut être implémentée en utilisant l’arithmétique flottante tout en préservant la propriété d’inclusion grâce à l’emploi d’arrondis dits “dirigés”. Pouvoir faire varier la précision de calcul permet de manipuler des intervalles de largeur réglable. L’intérêt d’avoir une précision variable est que si les intervalles en entrée sont de largeur très fine, les résultats calculés sont également très précis.

Sur l’exemple de Rump, MPFI renvoie des intervalles très larges, soit 3.10^{31} et 10^{22} en simple et double précision respectivement. Ces intervalles contiennent 0 si bien que même le signe du résultat est inconnu. Cela permet de suspecter un problème numérique. Dès que les calculs sont effectués sur 122 bits ou plus, le résultat devient un intervalle très fin, qui est un encadrement très précis de la valeur exacte, avec 35 chiffres décimaux ou plus.

Pour aller plus loin : http://devlog.cnrs.fr/jdev2013/t7a4

Voir également l’école Précision et Reproductibilité en Calcul Numérique qui s’est tenue à Fréjus en mars 2013.
 
(Dossier JDEV 2013 : Développer pour calculer : article précédent | suivant)
 

William Kahan a été le moteur historique de la standardisation des nombres flottants, et sa page web donne de nombreux exemples de leurs bons et mauvais usages.

D. Goldberg propose une introduction didactique et concise à l’arithmétique flottante dans son article What every computer scientist should know about floating-point arithmetic paru dans ACM Computing Surveys, vol. 23 no. 1, pp 5-48, 1991.

D. Monniaux propose un survol des (mauvaises) surprises qu’offre l’arithmétique flottante dans son article The pitfalls of verifying floating-point computations paru dans em TOPLAS, vol. 30 no. 3, article 12, 2008.

Une somme assez complète sur l’arithmétique flottante est l’ouvrage coordonné par J.-M. Muller : Handbook of Floating-Point Arithmetic. Birkhäuser Boston, 2010.

L’arithmétique stochastique est décrite notamment dans l’article de J. Vignes Discrete stochastic arithmetic for validating results of numerical software paru dans Numerical Algorithms, vol. 37, pp 377–390, 2004.

La bibliothèque CADNA est présentée par F. Jézéquel et J.M. Chesneaux dans l’article CADNA: a library for estimating round-off error propagation, paru dans Computer Physics Communications, vol. 178, no. 12, pp 933–955, 2008. Elle est par ailleurs disponible sur le site de lip6.

On trouvera une introduction récente à l’arithmétique par intervalles dans l’ouvrage de W. Tucker : Validated Numerics: A Short Introduction to Rigorous Computations. Princeton University Press, 2011.

On trouvera une introduction à la bibliothèque MPFI dans l’article de N. Revol and F. Rouillier Motivations for an Arbitrary Precision Interval Arithmetic and the MPFI Library paru dans Reliable Computing, vol. 11 no. 4, pp 275-290, 2005.

Pour consulter les travaux de S.M. Rump évoqués ici, consultez les deux articles Computer-assisted proofs and Self-Validating Methods, pp. 195-240, in Handbook on Accuracy and Reliability in Scientific Computation (B. Einarsson ed.), SIAM, 2005 ; et Verification methods: Rigorous results using floating-point arithmetic in Acta Numerica, vol. 19, pp. 287-449, 2010.