Représentation des nombres réels en informatique

En introduction
I) Nombres à virgule en base b
    1) Ecriture décimale en base 10
    2) Ecriture à virgule en base b
    3) Ensemble des réels ayant une écriture à virgule finie en base b
    4) Ecriture normalisée en base b, mantisse et exposant
    5) Nombres réels en informatique
    6) Nombres flottants (ou nombres à virgule flottante)
II) Nombres flottants
    1) Flottants sur 32 bits ou sur 64 bits
    2) Description des nombres flottants en informatique (norme IEEE 754)
    3) Caractéristiques des nombres flottants
III) Arrondi flottant d'un nombre réel
    1) Quelques propriétés des flottants
    2) Arrondi au plus proche d'un nombre réel
    3) Ecart entre deux flottants positifs successifs, unit in the last place (ulp)
    4) Ecart absolu, écart relatif entre un réel x et son arrondi flottant
IV) Erreurs dans les calculs sur les nombres flottants
    1) Qu'est-ce qu'un bon résultat ?
    2) Erreurs d'arrondi
    3) Erreurs de dépassement de capacité
    4) Erreur d'élimination (ou cancellation)
    5) Erreur d'absorption
    6) Erreurs de comparaison
    7) Attention aux réflexes mathématiques
    8) Conclusion

En introduction...

  Regardons et analysons les résultats des quelques calculs suivants:

>>> 0.1 + 0.1 + 0.1
0.30000000000000004
# Tiens, ça commence fort...

>>> 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1
0.6
# Normal, mais incompatible avec le résultat précédent

>>> (0.1 + 0.1 + 0.1) + (0.1 + 0.1 + 0.1)
0.6000000000000001
# Incompatible avec les deux résultats précédents >>> 0.1 + (0.2 + 0.3)
0.6
>>> (0.1 + 0.2) + 0.3
0.6000000000000001
# Pas de doutes, l'addition n'est pas associative

>>> (0.1 * 0.2) * 0.3
0.006000000000000001
>>> 0.1 * (0.2 * 0.3)
0.006
# Et la multiplication non plus

>>> 1000*(0.1 + 0.2)
300.00000000000006
>>> 1000*0.1 + 1000*0.2
300.0
# La multiplication n'est pas distributive par rapport à l'addition

>>> 1000 * ((1 + 3**(-30)) - 1)
4.884981308350689e-12
>>> 1000 * (1 + 3**(-30)) - 1000
4.888534022029489e-12
>>> 1000 * (3**(-30))
4.856935749618861e-12
# Ces trois calculs sont fortement incompatibles entre eux...
# Quelle est la meilleure façon de faire ce calcul ?

>>> 10**14 + 1.23456789
100000000000001.23
# Les gros mangent les petits...

  Les propriétés de base (associativité, distributivité) de l'addition et de la multiplication ne sont plus vraies dans le monde numérique. Le dernier exemple prouve que selon la manière dont un calcul est mené, le résultat peut être très différent.
  L'objet de ce chapitre est d'expliquer tout cela et d'apprendre à organiser un calcul numérique de la meilleure manière possible.

I) Nombres à virgule en base b

1) Ecriture décimale en base 10

  En base 10, la base habituelle, le nombre x = ± a n a n - 1 ... a 0 , d 1 d 2 ... d p (avec a i , d i ∈ {0,...,9}) est l'écriture décimale du nombre réel y = ± ( Σ i = 0 n a i 10 i + Σ k = 1 p d k 10 k )   .
  On identifie y et sa représentation décimale x , donc on peut écrire: ± a n a n - 1 ... a 0 , d 1 d 2 ... d p = ± ( Σ i = 0 n a i 10 i + Σ k = 1 p d k 10 k )   

Par exemple: 52,34 = 5 10 1 + 2 10 0 + 3 1 10 + 4 1 10 2

2) Ecriture à virgule en base b

  En base b , le nombre x = ± ( a n a n - 1 ... a 0 , d 1 d 2 ... d p ) b (avec a i , d i ∈ {0,..., b - 1}) est l'écriture à virgule en base b du nombre réel y = ± ( Σ i = 0 n a i b i + Σ k = 1 p d k b k )   .
  On identifie y et sa représentation à virgule en base b , donc on peut écrire: ± ( a n a n - 1 ... a 0 , d 1 d 2 ... d p ) b = ± ( Σ i = 0 n a i b i + Σ k = 1 p d k b k )

Par exemple: ( 1010 , 011 ) 2 = 2 3 + 2 1 + 1 2 2 + 1 2 3 = 10,375

3) Ensemble des réels ayant une écriture à virgule finie en base b

  Tous les nombres réels n'ont pas une représentation à virgule finie (avec un nombre fini de chiffres après la virgule) en base b. Seuls les nombres de l'ensemble D b = { k b n / k Z et n N } ont une représentation à virgule finie en base b.

  En base 10, seuls les nombres décimaux usuels (les éléments de D 10 ) ont une écriture à virgule finie.

4) Ecriture normalisée en base b, mantisse et exposant

  Tout nombre x D b non nul s'écrit de façon unique x = ± m b e avec m D b , m [ 1 , b [ et e Z .

L'écriture précédente est l'écriture normalisé en base b du nombre x .  On appelle m   la mantisse de x et e l'exposant de x .

  Cette écriture normalisée n'est qu'un décalage de la virgule. par exemple:

En base 10:  52,34 = 5 , 234 10 1 (m = 5.234 et e = 1)
En base 2: ( 1010 , 011 ) 2 = ( 1 , 010011 ) 2 2 3   (m = ( 1 , 010011 ) 2 et e = 3)

5) Nombres réels en informatique

  En informatique, les nombres "réels" sont une partie de l'ensemble D 2 des nombres à virgule finie en base 2.
  Ils seront représentés par leur écriture normalisée   x = ± m 2 e avec m D 2 , m [ 1 , 2 [ et e Z .
  La mantisse m et l'exposant e auront un nombre limité de chiffres, dépendant du nombre total de bits avec lesquels on veut représenter les "réels" informatiques.
  
  Comme m ∈ [1,2[, la mantisse m s'écrit toujours  m = ( 1 , ... ) 2 . Son premier bit est toujours 1.

6) Nombres flottants (ou nombres à virgule flottante)

  Dans la suite, on appellera nombres flottants l'ensemble des nombres x à virgule en base 2 ayant une écriture normalisée du type x = ± m 2 e avec m D 2 , m [ 1 , 2 [ et e Z ,  avec m et e dans une certaine plage, précisée dans le paragraphe suivant.

II) Nombres flottants

1) Flottants sur 32 bits ou sur 64 bits

  On veut représenter un nombre flottant (normalisé)  x sur un certain nombre de bits (32 ou 64 typiquement aujourd'hui). Il faut partager les bits disponibles entre:
    • le signe de x (facile, un bit suffit)
    • l'exposant de x
    • la mantisse de x

  La norme IEEE 754 de1985, complétée en 2008, (Institute of Electrical and Electronics Engineers) décrit entre autres la représentation informatique des nombres flottants sur 32 bits (simple précision) et 64 bits (double précison)
  Pour 32 bits, la répartition signe/exposant/mantisse est 32 = 1 + 8 + 23 et pour 64 bits, la répartition est 64 = 1 + 11 + 52 .

  Dans les deux cas, le premier bit de la mantisse (parfois appelé bit caché) vaut toujours 1 et n'est pas compté dans la mantisse.

2) Description des nombres flottants en informatique (norme IEEE 754)

a) Définitions

Le nombre x codé sur 32 bits sous la forme x = s e 1 e 2 ... e 8 m 1 m 2 ... m 23 est le nombre flottant x = ± m 2 e avec :
     •   s = 0 si x > 0 et s = 1 si x < 0 . Le bit s est le bit de signe.
     •   e = ( e 1 ... e 8 ) 2 - 127 .  Les bits e 1 ... e 8 sont les bits d'exposant et  e { - 127 , ... , + 128 } .
     •   m = ( 1 , m 1 ... m 23 ) 2 . Les bits m 1 ... m 23 sont les bits de mantisse .

On appelle ces nombres les nombres flottants (normalisés)  "simple précision".

Le nombre x codé sur 64 bits sous la forme x = s e 1 e 2 ... e 11 m 1 m 2 ... m 52 est le nombre flottant x = ± m 2 e avec :
     •   s = 0 si x > 0 et s = 1 si x < 0 . Le bit s est le bit de signe.
     •   e = ( e 1 ... e 11 ) 2 - 1023   . Les bits e 1 ... e 11 sont les bits d'exposant et e { - 1023 , ... , + 1024 } .
     •   m = ( 1 , m 1 ... m 52 ) 2 . Les bits m 1 ... m 52 sont les bits de mantisse.

On appelle ces nombres les nombres flottants (normalisés)  "double précision".

b) Conversion flottant - réel

Le nombre flottant x codé sur 64 bits sous la forme x = s e 1 e 2 ... e 11 m 1 m 2 ... m 52 est le nombre réel x = ± ( 1 + Σ k = 1 52 m k 2 k ) ( 2 ( e 1 e 2 .. e 11 ) 2 - 1023 ) .
Par exemple: prouver que 10.375 "=" 0|10000000010|010011000...0

c) Zéro, infini, nombres dénormalisés et nombres NaN

zero et l'infini sont codés de la façon suivante:
    (1) ± zéro est codé sous la forme ±0 "=" s 0...0 0...0 avec s = 0 ou s =1.
    (2) ± ∞ est codé sous la forme ±∞ "=" s 1...1 0...0 avec s = 0 ou s =1.

  Pour les nombres codés sur 32 bits, E = ( e 1 ... e 8 ) 2 ∈ {0,...255}, donc e ∈ {-127,...,+128}, mais les cas E = 0 et E = 255 = ( 11111111 ) 2 sont réservés à des cas particuliers: le cas x = 0 , x = , les nombres dénormalisés et les nombres NaN (Not a Number) (voir plus loin)
  Pour les nombres codés sur 64 bits, E = ( e 1 ... e 11 ) 2 ∈ {0,...2047}, donc e ∈ {-1023,...,+1024}, mais les cas E = 0 et E = 2047 = ( 11111111111 ) 2 sont réservés à des cas particuliers: le cas x = 0 , x = , les nombres dénormalisés et les nombres NaN.
  L'étude des nombres dénormalisés et des nombres NaN peut dans un premier temps être laissée de côté.

d) Nombres dénormalisés, nombres NaN (Not a Number)

  Lorsque E = ( 0 ... 0 ) 2 , le nombre est  dénormalisé: le premier bit (le bit caché) de la mantisse est nul. Les nombres dénormalisés servent à assurer une transition "douce" entre le plus petit flottant normalisé et zéro.
  Le nombre x codé sur 32 bits sous la forme x = s 0 ... 0 m 1 m 2 ... m 23 est le nombre flottant x = ± m 2 - 126   avec   m = ( 0 , m 1 ... m 23 ) 2 .
  Le nombre x codé sur 64 bits sous la forme x = s 0 ... 0 m 1 m 2 ... m 52 est le nombre flottant x = ± m 2 - 1022 avec   m = ( 0 , m 1 ... m 52 ) 2 .
  Lorsque E = ( 1 ... 1 ) 2 ,  et m ≠ 0, le nombre est  appelé nombre NaN: ces nombres sont utilisés pour des erreurs de calcul , par exemple   2 0 ou - 2 .

3) Caractéristiques des nombres flottants 64 bits

Flottant  64 bits Exposant  (11 bits) Mantisse  (52 bits)   Valeur Exacte Valeur approchée    Ecart / prédécesseur   
0     00000000000 0...0   0        0         
Plus petit dénormalisé 00000000000 0...01 2 - 1074 4.94 × 10 - 324 2 - 1074 = 4.94 × 10 - 324
Plus grand dénormalisé 00000000000 1...1 2 - 1022 - 2 - 1074 2.22507*10^^-308 2 - 1074 = 4.94 × 10 - 324
Plus petit normalisé 00000000001 0...0 2 - 1022 2.22507*10^^-308 2 - 1074 = 4.94 × 10 - 324
Prédécesseur de 1 01111111110 1...1 1 - 2 - 53 0.9999999999999999. 2 - 53 = 1.11 × 10 - 16
1 01111111111 0...0   1    1 2 - 53 = 1.11 × 10 - 16
Successeur de 01111111111 0...01 1 + 2 - 52 1.0000000000000002. 2 - 52 = 2.22 × 10 - 16
Plus grand normalisé 11111111110 1...1 2 1024 - 2 971 1.79769 × 10 308 2 971 = 2. × 10 292
+∞ 11111111111 0...0                     
Plus petit   NaN 11111111111 0...01                     
Plus grand NaN 11111111111 1...1                     

  On notera dans la suite F l'ensemble des nombres flottants.

III) Arrondi flottant d'un nombre réel

1) Quelques propriétés des flottants

L'ensemble F des nombres flottants a les caractéristiques importantes suivantes:
    (1) Il y a un nombre FINI de flottants.
    (2) Il y a un plus petit et un plus grand flottant strictement positif (idem pour strictement négatif).
    (3) Chaque flottant a un prédécesseur et un successeur (sauf le plus petit et le plus grand).
    (4) L'écart entre deux flottants qui se suivent n'est pas constant.

On peut donc écrire   F = { x 1 , ... , x N avec x 1 < x 2 < ... < x N }   .  On a x 1 = - x N

2) Arrondi au plus proche d'un nombre réel

  Presqu'aucun réel n'est dans F. Lorsqu'un réel comme 1 3 ou sin(45) ou ln 2 qui n'est pas dans F arrive dans le calculateur (saisi au clavier, récupéré dans un fichier de données ou résultat d'un calcul, etc...) ce réel est converti, on dit arrondi, en un élément de F.

  Il y a plusieurs possibilités, mais celle qui est adoptée par défaut est l'arrondi au plus proche, avec en cas d'équidistance celui dont la mantisse est paire. Précisons:
Notons   F = { x 1 , ... , x N avec x 1 < x 2 < ... < x N } l'ensemble des flottants.

Soit x R avec x [ x 1 , x N [ .  Il existe un unique i { 1 , ... , N - 1 } tel que x i x < x i + 1 . Alors l'arrondi au plus proche de x , noté A ( x ) , est:
     (1) A ( x ) = x i lorsque  x ∈ [ x i , x i + x i + 1 2 [  
      (2) A ( x ) = x i + 1 lorsque  x ∈ ] x i + x i + 1 2 , x i + 1 ] .
    (3) Lorsque x = x i + x i + 1 2 , A ( x ) = x i ou A ( x ) = x i + 1 : A ( x ) est celui des deux dont la mantisse est paire (se termine par 0)
    
Pour savoir où "est" x dans l'intervalle [ x i , x i + 1 [ l'ordinateur doit avoir une valeur aprochée de x avec des bits supplémentaires dans la mantisse.

3) Ecart entre deux flottants positifs successifs, unit in the last place (ulp)

L'ulp  (unit in  the last place) d'un flottant x i positif est l'écart qui le sépare du flottant immédiatement supérieur x i + 1 . Dans tous les cas, x i + 1 - x i = 2 - 52 2 e , avec e l'exposant de x i .  
On étend cette définition d'ulp aux nombres réels positifs: si   x ∈ [ 2 e , 2 e + 1 [ (avec e Z), on pose ulp ( x ) = 2 - 52 2 e

4) Ecart absolu, écart relatif entre un réel x et son arrondi flottant

En notant A ( x ) l'arrondi flottant de x , alors:
    (1) L'écart absolu entre x et A ( x ) est A ( x ) - x 1 2 ulp ( | x | ) ε | x | avec ε = 2 - 53 10 - 16 .
     (2)  L'écart relatif entre x et son arrondi flottant A ( x ) est | A ( x ) - x x | ε avec ε = 2 - 53

Avec x = 10 9 3 , A ( x ) - x x 10 - 16 3 10 - 8   en double précision.

IV) Erreurs dans les calculs sur les nombres flottants

1) Qu'est-ce qu'un bon résultat ?

  On considère un calcul sur des nombres réels. Le résultat exact (pas calculable en général...) est R exact , le résultat donné par l'ordinateur est R ordi .  La question que l'on doit se poser est: quel est au maximum l'erreur l'erreur relative e r = R exact - R ordi R exact dans l'évaluation du résultat ?
  Les calculs du III) nous montrent que la valeur idéale est e r = 2 - 53 , mais on va voir que parfois on en est très loin.

2) Erreurs d'arrondi

a) Erreur d'arrondi

  Le  résultat d'une opération op (avec op + , - , , / ) entre deux flottants x , y F ou d'une fonction f "usuelle"   ( f , sin , exp , ln , n , ( ) n ... . )   appliquée à un flottant x n'est presque jamais un élément de F.
  Il faut donc arrondir le résultat de op ( x , y ) ou de f ( x ) .  L'erreur commise en arrondissant le résultat s'appelle l'erreur d'arrondi dans le calcul.

b) Le meilleur arrondi: arrondi correct

  Le meilleur arrondi, appelé arrondi correct, du calcul op ( x , y ) ou f ( x ) est l'arrondi informatique du calcul EXACT de op ( x , y ) ou de f ( x ) lorsque x , y F .
  La norme IEEE 754 exige que ce soit le cas pour les opérations   + , - , , / , la fonction et le recommande pour les autres fonctions usuelles (sin, exp, ln,...).
  En pratique, ces recommandations sont très délicates à mettre en œuvre pour toutes les fonctions usuelles.

c) Erreurs d'arrondi dans les calculs sur les nombres réels "sauvages"

  Etant donnés x , y R , op un opérateur ou f une fonction, on veut calculer op ( x , y ) ou f ( x ) . Si (c'est presque toujours le cas), les nombres x et y ne sont pas dans F, alors le calculateur arrondira déjà x et y avant de faire les calculs.
  Le résultat calculé de op ( x , y ) ou de f ( x ) sera A ( op ( A ( x ) , A ( y ) ) ou A ( f ( A ( x ) ) ) . Cet arrondi préalable au calcul peut avoir des conséquences importantes, voir catastrophiques sur le résultat dans dans le cas de la soustraction ou de l'addition (voir la suite) .
  Pour la multiplication, la division (hors division par 0 ou erreur d'underflow), on peut admettre que les conséquences de ces erreurs d'arrondi sont négligeables.

3) Erreurs de dépassement de capacité

Lorsque le résultat final ou un résultat intermédiaire d'un calcul sort de la plage des nombres normalisés, une erreur se produit:
    (1) l'erreur d'overflow pour les dépassements  (en valeur alsolue) vers le haut: le }résultat} dépasse le plus grand nombre normalisé. Le calcul s'arrête avec un message d'erreur pour l'utilisateur.
    (2) l'erreur d'underflow pour les dépassements (en valeur alsolue) vers le bas (vers 0):  le }résultat} est inférieur au plus petit nombre normalisé. Le calcul se poursuit, le résultat est alors un nombre dénormalisé, ou 0, avec un message interne dans le programme de calcul qui permet éventuellement d'effectuer des opérations complémentaires ou un traitement différent du calcul.

4) Erreur d'élimination (ou cancellation)

a) Quand se produit-elle ?

  L'erreur d'élimination (cancellation en anglais) se produit lorsqu'on soustrait deux nombres x et y proches l'un de l'autre. Elle peut être catastrophique.

Par exemple:

>>> a = (1 + 3**-33) - 1
>>> b = 3**(-33)
>>> print(a, b, (a - b) / b)
2.220446049250313e-16 1.79886509245143e-16 0.23435940725514182
# L'erreur relative commise dans le calcul de a est de 23 % : énorme !

b) Comment éviter les d'erreurs d'élimination ?

  Pour éviter les erreurs d'élimination, il faut absolument éviter dans un calcul de soustraire des nombres trop proches. Le calcul doit être bien mené.

5) Erreur d'absorption

a) Quand se produit-elle ?

  L'erreur d'absorption se produit lorsqu'on soustrait ou additionne deux nombres x et y d'ordres de grandeurs très différents. Si x y , alors x + y y et on "perd" totalement ou partiellement x .
  En particulier, si x y , alors   ( x + y ) - y est très différent de x . (erreur d'élimination)

x + y = y ( 1 + x y ) . Lorsque x y < 2 - 53 alors 1 + x y = 1 et x est totalement absorbé par y .

Cette erreur d'absorption est volontairement faite dans un cours de physique, lorsqu'on "néglige" une quantité devant une autre dans un calcul.

b) Ordre de grandeur

  On peut retenir qu'approximativement:

  En base 10: avec x et y écrits sous forme normalisés avec 16 chiffres significatifs dans leur mantisse en base 10, lorsque x y < 10 - n , le calcul de z = x + y ignore les n derniers chiffres de x .
  Lorsque n 16 l'erreur d'absorption est partielle, elle est totale ( z = y ) lorsque n > 16 .

Par exemple, si x y 10 - 5 , on perd environ 1/3 des chiffres de x en calculant x + y .

a = (10**-5) * 8 / 7
b = 1 + a
a = 1.1428571428571429e-05 b = 1.0000114285714286

c) Quelles sont les conséquences d'une erreur d'absorption ?

Les conséquences d'une erreur d'absorption sont importantes lorsque:
    (1) elle est suivie d'une erreur délimination :  s i x y , alors   ( x + y ) - y est très différent de x
    (2) on cherche à évaluer une somme de très nombreux termes: il faut organiser le calcul pour faire la somme du plus petit terme jusqu'au plus grand, pour perdre le moins possible les "informations" apportées par les petits nombres.

e) Comment éviter les d'erreurs d'absorption  

  On ne peut souvent pas les éviter: il faut être capable d'en estimer les conséquences éventuelles. L'addition n'étant pas associative, il vaut mieux sommer les termes du plus petit au plus grand.

6) Erreurs de comparaison

a) Quand se produit-elle ?

  L'erreur de comparaison peut se produire lors d'un test d'égalité de deux flottants x et y . Ces deux valeurs devant mathématiquement être égales sont, suite à des erreurs d'arrondi, numériquement différentes, et vice versa.
  Ou encore lorsqu'on teste si x > y avec deux valeurs x et y très proches.

Par exemple:

0.1 + 0.1 + 0.1 == 0.3
False

Retenir:

  Le test d'égalité x = y ou de différence x y entre deux flottants x et y est un non sens informatique .

b) Quelles sont les conséquences d'une erreur de comparaison ?

De telles erreurs peuvent entraîner des boucles sans fin ou des erreurs de branchement conditionnel dans un programme.

c) Comment éviter les d'erreurs de comparaison ?  

Pour savoir, dans le cas "critique" où x et y sont très proches, si x = y , il vaut mieux tester si 1 - y x < ε , avec par exemple   ε = 2 - 51 .

7) Attention aux réflexes mathématiques dans les calculs numériques

•  L'addition n'est plus associative: ( a + b ) + c a + ( b + c ) en général
•  La multiplication n'est plus distributive par rapport à l'addition: a ( b + c ) a b + a c en général

8) Conclusion

   Les calculs (dont les comparaisons) sur les nombres réels doivent être organisés au mieux, et il faut avoir en tête les divers écueils qui peuvent les faire capoter (ce n'est pas très grave: on s'en aperçoit) ou dérailler (c'est beaucoup plus insidieux).  

© 2015 - Eric Obermeyer      Powered by