Unité en dernière position

En informatique et en analyse numérique, l'unité en dernière position ou l'unité de plus faible précision (en anglais : ulp, unit in the last place) est l'espacement entre deux nombres en virgule flottante consécutifs, c'est-à-dire la valeur que représente le chiffre le moins significatif (chiffre le plus à droite) lorsqu'il vaut 1. Il est utilisé comme une mesure de la précision dans les calculs numériques^[1].

Définition

La définition la plus courante est la suivante : en base $b$ avec une précision $p$ , si $b^{e}\leq |x|<b^{e+1}$ , alors $\operatorname {ulp} (x)=b^{\max\{e,\,e_{\min }\}-p+1}$ ^[2], où $e_{\min }$ est l'exposant minimal des nombres normalisés. En particulier, $\operatorname {ulp} (x)=b^{e-p+1}$ pour les nombres normalisés, et $\operatorname {ulp} (x)=b^{e_{\min }-p+1}$ pour les nombres dénormalisés.

Une autre définition, suggérée par John Harrison, est légèrement différente : $\operatorname {ulp} (x)$ est la distance entre les deux nombres à virgule flottante les plus proches (consécutifs) $a$ et $b$ (c'est-à-dire satisfaisant $a\leq x\leq b$ et $a\neq b$ ), en supposant que l'étendue de l'exposant n'est pas bornée supérieurement^[3]^,^[4]. Ces définitions diffèrent seulement aux puissances signées de la base^[2].

La norme IEEE 754 — suivie par tous les matériels modernes en virgule flottante — exige que le résultat d’une opération arithmétique élémentaire (addition, soustraction, multiplication, division et racine carrée depuis 1985, et FMA depuis 2008) soit correctement arrondi, ce qui implique qu’en arrondi au plus proche, le résultat arrondi se situe à moins de 0,5 ulp du résultat mathématiquement exact, selon la définition de John Harrison ; inversement, cette propriété implique que la distance entre le résultat arrondi et le résultat mathématiquement exact est minimisée (mais pour les cas à mi-distance, elle est satisfaite par deux nombres à virgule flottante consécutifs). Des bibliothèques numériques réputées calculent les fonctions transcendantes de base entre 0,5 et environ 1 ulp. Seules quelques bibliothèques les calculent avec un écart de 0,5 ulp au maximum, ce problème étant complexe en raison du dilemme du fabricant de tables^[5].

Exemples

Exemple 1

Soit $x$ un nombre en virgule flottante positif et supposons que le mode d'arrondi actif soit arrondi au pair le plus proche, appelé $\operatorname {RN}$ . Si $\operatorname {ulp} (x)\leq 1$ , alors $\operatorname {RN} (x+1)>x$ . Sinon, $\operatorname {RN} (x+1)=x$ ou $\operatorname {RN} (x+1)=x+\operatorname {ulp} (x)$ , selon la valeur du chiffre le moins significatif et de l'exposant de $x$ . Ceci est démontré par le code Haskell suivant saisi dans une invite interactive :

> until (\x -> x == x+1) (+1) 0 :: Float
1.6777216e7
> it-1
1.6777215e7
> it+1
1.6777216e7

Ici on commence avec 0 en simple précision (binary32) et on ajoute 1 de façon répétée jusqu'à ce que l'opération ne change pas la valeur du résultat. Puisque le significande d'un nombre en simple précision contient 24 bits, le premier entier qui n'est pas exactement représentable est 2²⁴+1, et cette valeur s'arrondit en 2²⁴ en arrondi au pair le plus proche. Donc le résultat est égal à 2²⁴.

Exemple 2

L'exemple suivant en Java approxime $π$ sous forme d'une valeur virgule flottante en cherchant les deux valeurs encadrant $\pi$ : $p_{0}<\pi <p_{1}$ .

// π avec 20 chiffres décimaux
BigDecimal π = new BigDecimal("3.14159265358979323846");

// troncature vers un nombre en virgule flottante double précision
double p0 = π.doubleValue();
// -> 3.141592653589793  (hex: 0x1.921fb54442d18p1)

// p0 est plus petit que π, on cherche donc le nombre suivant représentable en double précision
double p1 = Math.nextUp(p0);
// -> 3.1415926535897936 (hex: 0x1.921fb54442d19p1)

Donc $\operatorname {ulp} (\pi )$ est déterminé comme $\operatorname {ulp} (\pi )=p_{1}-p_{0}$ .

// ulp(π) est la différence entre p1 et p0
BigDecimal ulp = new BigDecimal(p1).subtract(new BigDecimal(p0));
// -> 4.44089209850062616169452667236328125E-16
// (c'est exactement 2**(-51))

// le même résultat est obtenu en utilisant la fonction de librairie standard
double ulpMath = Math.ulp(p0);
// -> 4.440892098500626E-16 (hex: 0x1.0p-51)

Exemple 3

Un autre exemple, en Python, également saisi dans une invite interactive, est :

>>> x = 1.0
>>> p = 0
>>> while x != x + 1:
...   x = x * 2
...   p = p + 1
... 
>>> x
9007199254740992.0
>>> p
53
>>> x + 2 + 1
9007199254740996.0

Dans cas, on commence avec x = 1 et on le double de façon répétée jusqu'à ce que x = x + 1. De façon similaire à l'exemple 1, le résultat est 2⁵³ car le format virgule flottante double précision utilise une mantisse de 53 bits.

Références

↑ (en) David Goldberg, « What Every Computer Scientist Should Know About Floating-Point Arithmetic », ACM Computing Surveys, vol. 23, n^o 1,‎ mars 1991, p. 5–48 (DOI 10.1145/103162.103163 , S2CID 222008826) (avec l'addendum "Differences Among IEEE 754 Implementations": , ).
1 2 (en) Jean-Michel Muller, Nicolas Brunie, Florent de Dinechin, Claude-Pierre Jeannerod, Joldes Mioara, Vincent Lefèvre, Guillaume Melquiond, Nathalie Revol et Serge Torres, Handbook of Floating-Point Arithmetic, Birkhäuser, 2018 (1^re éd. 2010) (ISBN 978-3-319-76525-9, DOI 10.1007/978-3-319-76526-6)
↑ (en) John Harrison, « A Machine-Checked Theory of Floating Point Arithmetic » (consulté le 17 juillet 2013)
↑ (en) Jean-Michel Muller, « "On the definition of ulp(x)". INRIA Technical Report 5504 (archivé en novembre 2020) », ACM Transactions on Mathematical Software, vol. V, n^o N,‎ novembre 2005 (lire en ligne [PDF]).
↑ (en) William Kahan, « A Logarithm Too Clever by Half » (consulté le 14 novembre 2008)

Portail de l’informatique

[1] (en) David Goldberg, « What Every Computer Scientist Should Know About Floating-Point Arithmetic », ACM Computing Surveys, vol. 23, n^o 1,‎ mars 1991, p. 5–48 (DOI 10.1145/103162.103163 , S2CID 222008826) (avec l'addendum "Differences Among IEEE 754 Implementations": , ).

[hfpa2018-2] 1 2 (en) Jean-Michel Muller, Nicolas Brunie, Florent de Dinechin, Claude-Pierre Jeannerod, Joldes Mioara, Vincent Lefèvre, Guillaume Melquiond, Nathalie Revol et Serge Torres, Handbook of Floating-Point Arithmetic, Birkhäuser, 2018 (1^re éd. 2010) (ISBN 978-3-319-76525-9, DOI 10.1007/978-3-319-76526-6)

[3] (en) John Harrison, « A Machine-Checked Theory of Floating Point Arithmetic » (consulté le 17 juillet 2013)

[4] (en) Jean-Michel Muller, « "On the definition of ulp(x)". INRIA Technical Report 5504 (archivé en novembre 2020) », ACM Transactions on Mathematical Software, vol. V, n^o N,‎ novembre 2005 (lire en ligne [PDF]).

[5] (en) William Kahan, « A Logarithm Too Clever by Half » (consulté le 14 novembre 2008)

[1]

[2]

[3]

[4]

[5]