Epsilon d'une machine

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'epsilon d'un microprocesseur donne la limite supérieure de l'erreur d'approximation relative causé par l'arrondi des calculs de ce microprocesseur en arithmétique à virgule flottante. Cette valeur est une caractéristique de l'arithmétique des ordinateurs dans le domaine de l'analyse numérique, et par extension dans le sujet de la science computationnelle. L'epsilon est aussi appelé macheps ou unité d'arrondi. Il est parfois noté à l'aide du symbole grec epsilon ou gras Romain u.

Valeur pour les unités matérielles standard d'arithmétique à virgule flottante[modifier | modifier le code]

Les valeurs d'epsilon standards suivantes s'appliquent pour le matériel implémentant les normes IEEE de calcul en virgule flottante:

IEEE 754 - 2008 Nom usuel type de donnée C++ Base Précision   Epsilon[notes 1]   Epsilon[notes 2]
binary16 demi-précision short 2 11 (un des bits est implicite) 2−11 ≈ 4.88e-04 2−10 ≈ 9.77e-04
binary32 simple précision
float 2 24 (un des bits est implicite) 2−24 ≈ 5.96e-08 2−23 ≈ 1.19e-07
binary64 double précision double 2 53 (un des bits est implicite) 2−53 ≈ 1.11e-16 2−52 ≈ 2.22e-16
précision étendue (en) _float80[1] 2 64 2−64 ≈ 5.42e-20 2−63 ≈ 1.08e-19
binary128 quadruple précision _float128[1] 2 113 (un des bits est implicite) 2−113 ≈ 9.63e-35 2−112 ≈ 1.93e-34
decimal32 simpe précision décimale _Decimal32[2] 10 7 5 × 10−7 10−6
decimal64 double précision décimale _Decimal64[2] 10 16 5 × 10−16 10−15
decimal128 quadruple précision décimale _Decimal128[2] 10 34 5 × 10−34 10−33

Définition formelle[modifier | modifier le code]

Une procédure d'arrondi est une procédure de choix de la représentation d'un nombre réel dans un système de numération en virgule flottante. Pour un certain nombre de système et une procédure d'arrondi, la machine epsilon est le maximum de l'erreur relative de la procédure d'arrondi choisie.

Certaines informations sont nécessaires pour calculer la valeur en partant de la définition de l'erreur relative. Un système de numération à virgule flottante est caractérisé par une base et par une précision, c'est-à-dire le nombre de chiffres de composant la mantisse (y compris les éventuels bits implicites). Les nombres représentés avec un exposant constant sont espacés d'une valeur de. L'espacement est donc constant à l'intérieur d'intervalles dont les bornes sont les puissances entières de; Pour une puissance de donnée, la précision pour l'intervalle dont elle est la borne inférieure est b fois plus importante que celle dont elle est la borne supérieure.

L'epsilon étant une borne pour l'erreur d'approximation relative, il suffit de prendre en compte les nombres positifs d'exposant . Pour l'arrondi usuel, vers le nombre le plus proche, l'erreur d'approximation absolue est au plus la moitié de l'espacement, c'est-à-dire . Cette valeur est la plus grande valeur possible pour le numérateur de l'erreur relative. Le dénominateur de la formule est le nombre à arrondir, qui devrait être aussi petit que possible pour que l'erreur relative soit grande. La pire erreur relative se produit donc quand l'arrondi est appliqué à des nombres de la forme ou  est compris entre et . Tous ces nombres sont arrondis vers avec l'erreur relative . Le maximum est atteint pour à l'extrémité haute de cet intervalle. Le dénominateur, de valeur , est négligeable en comparaison du numérateur, il est donc négligé pour simplifier, et la formule est utilisée comme formule de calcul de l'epsilon. L'erreur relative est la plus grande pour les nombres qui s'arrondissent vers , ce qui permet de nommer l'epsilon aussi parfois unit roundoff (arrondi vers l'unité) ce qui signifie approximativement "erreur relative maximale possible lors de l'arrondi vers l'unité".

Ainsi, l'espacement maximal entre nombre à virgule flottante normalisé et un nombre normalisé adjacent est [3].

Modèle arithmétique[modifier | modifier le code]

L'Analyse numérique utilise l'epsilon de la machine pour étudier les effets de l'erreur d'arrondi. Les valeurs réelles des erreurs de l'arithmétique de la machine sont en général bien trop compliqués pour être étudié directement, un modèle simple est donc utilisé. La norme arithmétique de l'IEEE  définit que toutes les opérations en virgule flottante sont calculées en supposant qu'il est possible d'effectuer les opérations avec une précision infinie, puis en supposant que le résultat soit arrondi à un nombre à virgule flottante. Supposons que sont des nombres à virgule flottante, que  est une opération arithmétique sur des nombres à virgule flottante, telle que l'addition ou la multiplication, et que est l'opération effectuée avec une précision infinie. Selon la norme, l'ordinateur calcule Par définition de l'epsilon, l'erreur relative de l'arrondi est au plus de sa magnitude, de sorte que , en magnitude absolue, est égal au plus à epsilon. Les livres par Demmel et Higham dans les références peuvent être consultés pour voir comment ce modèle est utilisé pour l'analyse des erreurs d'algorithmes comme l'élimination de Gauss.

Variantes de la définition[modifier | modifier le code]

La norme ne définit pas les termes de machine epsilon (epsilon de la machine) et unit roundoff (unité d'arrondi). Il en résulte qu'il existe des variantes pour les définitions qui sont parfois utilisées en pratique, au risque une certaine confusion.

La définition donnée ici pour machine epsilon est celle du professeur James Demmel (en) dans ses notes de cours[4] et son logiciel d'algèbre linéaire LAPACK package[5], et par des articles de recherche scientifique sur le calcul numérique[6] et de certains logiciels de calcul scientifiques[7]. La plupart des analystes numériques utilisent les termes (en anglais) machine epsilon et unit roundoff comme des termes synonymes de la définition présentée ici.

La définition suivante est beaucoup plus répandue à l'extérieur du milieu universitaire : l'epsilon est défini comme le plus petit nombre qui, ajouté à un, donne un résultat différent de un. Avec cette définition, l'epsilon est égal à la valeur de l'unité à la dernière place (en) par rapport à 1, c'est-à-dire[8] pour la procédure d'arrondi au plus proche u. La prévalence de cette définition vient de son utilisation dans la norme ISO du langage C, en particulier la définition des constantes concernant les types à virgule flottante[9],[10] et celles équivalentes d'autres langages de programmation[11],[12]. Il est également largement utilisé dans le monde des logiciels de calcul scientifique[13],[14],[15], dans la littérature sur les nombres et le calcul[3],[16],[17],[18] et d'autres ressources académiques[19],[20].

Comment déterminer l'epsilon[modifier | modifier le code]

Dans les cas où les bibliothèques standard ne fournissent pas de valeurs pré-calculées (comme <float.h (en)> le fait avec FLT_EPSILON, DBL_EPSILON et LDBL_EPSILON en C et <limits> avec std::numeric_limits<T>::epsilon() en C++), la meilleure manière de déterminer l'epsilon d'une machine est de se référer à la table ci-dessus, et utiliser la formule de puissance appropriée. Le calcul est souvent donné comme un exercice dans les manuels d'apprentissage. Les exemples suivants utilisent la définition de la distance des nombres à virgule flottante à 1, et celle d'unité d'arrondi.

Notez que les résultats dépendent du type de nombre à virgule flottante, comme le float, double, long double, ou des types équivalents dans les autres langages de programmation, des compilateurs et bibliothèques utilisés, et finalement de la plate-forme ou sera exécuté le programme.

Certains formats pris en charge par le microprocesseur peuvent ne pas être pris en charge par le compilateur choisi et/ou par le système d'exploitation. D'autres types sont parfois émulés par la bibliothèque d'exécution, y compris parfois en mode arithmétique à précision arbitraire, disponible dans certains langages et bibliothèques.

Au sens strict le terme de machine epsilon désigne la précision 1+eps directement prise en charge par le processeur (ou le coprocesseur), et non une précision 1+eps prise en charge par un compilateur spécifique pour un système d'exploitation spécifique, sauf s'il est connu pour utiliser le meilleur format.

Les types à virgule flottante de la norme IEEE 754 ont la propriété, lorsque réinterprété comme des entiers codés en complément à deux entier de la même taille, de croître de manière monotone sur les valeurs positives et de décroître de manière monotone sur les valeurs négatives (voir la représentation binaire des floats 32 bits (en)). Ils ont aussi la propriété que 0 < |f(x)| < ∞, et |f(x+1) − f(x)| ≥ |f(x) − f(x-1)| (où f(x) est l'interprétation de x en complément à 2 mentionnée au dessus). Dans les langages qui permettent la réinterprétation de type (en) tout en utilisant IEEE 754-1985, nous pouvons exploiter tout ceci pour calculer un epsilon en temps constant. Par exemple, en C:

typedef union {
  long long i64;
  double d64;
} dbl_64;
double machine_eps (double value)
{
    dbl_64 s;
    s.d64 = value;
    s.i64++;
    return s.d64 - value;
}
typedef union {
  long long i64;
  double d64;
} dbl_64;
double machine_eps (double value)
{
    dbl_64 s;
    s.d64 = value;
    s.i64++;
    return s.d64 - value;
}

Le résultat est de même signe que value. Si un résultat positif est toujours souhaité l'instruction de retour de cette routine peut être remplacé par :

    return (s.i64 < 0 ? value - s.d64 : s.d64 - value);
    return (s.i64 < 0 ? value - s.d64 : s.d64 - value);

Pour les doubles en 64 bits, le résultat est 2.220446e-16, soit 2-52 comme prévu.

Approximation[modifier | modifier le code]

L'algorithme suivant, très simple, peut être utilisé pour trouver une approximation de l'epsilon d'une machine, un facteur deux (un ordre de grandeur) de sa valeur réelle, par une recherche linéaire.

epsilon = 1.0;

tant que (1.0 + 0.5 * epsilon) ≠ 1.0:
 epsilon = 0.5 * epsilon

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. selon le prof. Demmel, LAPACK, Scilab
  2. selon le prof. Higham; la norme C ISO; les constantes définies par les langages C, C++ et Python, Mathematica, MATLAB et Octave; divers manuels universitaires - voir ci-dessous pour la dernière définition
  1. a et b Floating Types - Using the GNU Compiler Collection (GCC)
  2. a, b et c Decimal Float - Using the GNU Compiler Collection (GCC)
  3. a et b Higham, Nicholas (2002).
  4. (en) « Basic Issues in Floating Point Arithmetic and Error Analysis »
  5. « LAPACK Users' Guide Third Edition »,
  6. David Goldberg, « What Every Computer Scientist Should Know About Floating-Point Arithmetic », ACM Computing Surveys, vol. 23, no 1,‎ (lire en ligne)
  7. « Scilab documentation - number_properties - determine floating-point parameters »
  8. notez qu'ici p est défini comme la précision, càd le nombre total de bits de la mantisse en incluant le bit de poids fort implicite. C'est le cas notamment dans la table ci-dessus
  9. Jones, Derek M. (2009).
  10. « "float.h reference at cplusplus.com" »
    la documentation de référence de l’en-tête "float.h" exposant les fonctions de manipulation des nombres en virgule flottante en langage C
  11. « std::numeric_limits reference at cplusplus.com »
    une documentation de la bibliothèque standards du langage C++ concernant les valeurs extrêmes des types de données numériques que le langage utilise, qui sont calculés en fonction de la machine pour laquelle le programme est compilé
  12. « Python documentation - System-specific parameters and functions »
    Documentation du langage python sur les fonctions de sa bibliothèque qui exposent des valeurs qui dépendent du système sur lequel le programme python est exécuté
  13. « Mathematica documentation: $MachineEpsilon »
    la documentation d'une constante du logiciel de calcul mathématique Mathematica qui expose l’epsilon de la machine
  14. « Matlab documentation - eps - Floating-point relative accuracy »
    la documentation du logiciel de calcul Matlab qui documente la précision des calculs
  15. « Octave documentation - eps function »
    Documentation du logiciel octave documentant la fonction permettant de récupérer la valeur de l’epsilon
  16. Alfio Quarteroni, Riccardo Sacco et Fausto Saleri, Méthodes numériques pour le calcul scientifique,
  17. William H. Press, Saul A. Teukolsky, William T. Vetterling et Brian P. Flannery, Numerical Recipes, p. 890
  18. Gisela Engeln-Müllges et Fritz Reutter, Numerical Algorithms with C,
  19. Robert M. Corless, « The Machine Epsilon »,
  20. « MCS 471 Computer Problem 1 »,

Liens externes[modifier | modifier le code]