Arrondi correct
L'arrondi correct est un concept d'arithmétique approchée, employé principalement dans le domaine de l'arithmétique en virgule flottante sur ordinateur. Une opération mathématique est dite correctement arrondie lorsque le résultat approché qu'elle fournit est le résultat représentable le plus proche (au sens d'une certaine règle d'arrondi) du résultat mathématique exact.
La notion d'arrondi correct se distingue de celle d'arrondi fidèle, qui désigne l'un quelconque des deux nombres représentables qui encadrent le résultat exact. Ainsi, l'arrondi correct à l'entier du quotient de 151 par 100 est l'entier 2, tandis que 1 et 2 sont tous deux des arrondis fidèles.
La norme IEEE 754 d'arithmétique flottante emploie le concept d'arrondi correct pour assurer que les opérations de base sur les nombres en virgule flottante renvoient un résultat bien défini, indépendant de l'implémentation, et non simplement une approximation du résultat exact.
Pour les opérations arithmétiques (addition, soustraction, multiplication, division, racine carrée), des algorithmes simples permettent de déterminer l'arrondi correct. Mais pour les fonctions mathématiques, tout ce qu'on sait faire est de calculer une approximation du résultat avec une borne d'erreur, et le nombre de chiffres supplémentaires pour déterminer l'arrondi peut être a priori relativement grand. Par exemple[1], en considérant le format decimal64 (16 chiffres décimaux) en arrondi au plus près, on a exp(9.407822313572878·10⁻²) = 1.09864568206633850000000000000000278..., de sorte que si on calcule le résultat avec une précision de 33 chiffres décimaux, au sens avec une erreur d'au plus ±1 sur le 33e chiffre, on obtiendrait par exemple la valeur approchée 1.0986456820663385, donc un intervalle d'incertitude du type [1.09864568206633849999999999999999,1.09864568206633850000000000000001] (sans savoir où se situe la valeur exacte). On ne pourrait donc pas savoir si l'arrondi est 1.098645682066338 (arrondi de la borne inférieure au plus près) ou 1.098645682066339 (arrondi de la borne supérieure au plus près). Ce phénomène est appelé le dilemme du fabricant de tables, car il se posait à l'origine aux éditeurs de tables de valeurs numériques. Pour éviter ce problème, il faudrait ici calculer l'approximation avec une précision de 34 chiffres. Plus généralement, les cas les plus difficiles à arrondir sont ceux dont le résultat mathématique exact est extrêmement proche d'une discontinuité de la fonction d'arrondi (dans l'exemple ci-dessus, 1.0986456820663385). Deux problèmes se posent pour concevoir des algorithmes d'évaluation de fonctions mathématiques avec arrondi correct:
- La preuve que l'arrondi correct est toujours garanti. C'est un problème difficile en général. Grâce à un théorème de théorie des nombres, on peut prouver des bornes de l'ordre de plusieurs millions ou milliards de chiffres pour les fonctions élémentaires. Mais aucune borne n'est connue pour les fonctions spéciales (et l'existence de bornes est même un problème ouvert pour certaines fonctions). Dans la pratique, il suffit d'un peu plus du double de la précision du système, mais dans l'état actuel des connaissances, seule une recherche exhaustive (potentiellement trop coûteuse) permet de le prouver.
- La rapidité de l'algorithme. La plupart des cas peuvent être traités avec une précision un peu supérieure à celle du système, donc rapidement. Mais à l'inverse, certains cas peuvent demander une précision de l'ordre du double de celle du système, comme dans l'exemple ci-dessus, donc prendre beaucoup plus de temps à calculer.
Notes et références
- Vincent Lefèvre, Damien Stehlé and Paul Zimmermann. Worst Cases for the Exponential Function in the IEEE 754r decimal64 Format. Reliable Implementation of Real Number Algorithms: Theory and Practice, pages 114–126. Springer, 2008.