ESIEE – Unité d’informatique IN101
et ERREURS NUMÉRIQUES
Référence :
« Analyse numérique pour l’ingénieur »,
André Fortin, Editions de l’Ecole Polytechnique de Montréal
( N )10
= ( bn-1bn-2 bn-3 … b2b1b0
)2
c’est-à-dire
N = bn-1 x 2n-1 + bn-2 x 2n-2 +
bn-3 x 2n-3 + … + b2 x 22 + b1 x 21
+ b0 x 20
Tant que N =/= 0 faire
bit
<- N modulo 2
N <- N / 2 // division
entière
Avec N = ( 100
)10 on a :
100 / 2 = 50 reste
0 -> b0 = 0
50 / 2 = 25 reste
0 -> b1 = 0
25 / 2 = 12 reste
1 -> b2 = 1
12 / 2 =
6 reste 0 -> b3 = 0
6 / 2 =
3 reste 0 -> b4 = 0
3 / 2 =
1 reste 1 -> b5 = 1
1 / 2 = 0 reste 1 -> b6 = 1
L’entier décimal 100 s’écrit 1100100
en base 2, ce qu’on notera :
( 100
)10 = (1100100 )2
2.1-
Représentation des entiers relatifs
La représentation en complément à 2 est la plus fréquemment utilisée. Si on dispose
d’un mot de n bits (bn-1bn-2
bn-3 … b2b1b0)
pour exprimer un entier relatif N, on pose :
N = – bn-1 x 2n-1
+ bn-2 x 2n-2 + bn-3 x 2n-3 + … + b2 x 22
+ b1 x 21 + b0 x 20
A noter le signe négatif devant le terme bn-1. Il s’en suit :
N >= 0 <=>
bn-1 = 0
N < 0 <=>
bn-1 = 1
Les entiers positifs sont donc représentés par 0
suivi de leur expression en binaire naturel sur n-1 bits. Pour obtenir la
représentation d’un nombre négatif, il suffit de lui ajouter 2n-1 et
de transformer le résultat en binaire sur n-1 bits, puis de lui adjoindre le
bit bn-1 de valeur 1.
Sur n bits on peut représenter tout entier du
segment [– 2n-1 ,
+ 2n-1 – 1 ].
Exemples :
La représentation sur 4 bits de 0101
vaut :
– 0 x 23 + 1 x 22
+ 0 x 21 + 1 x 20
soit 5 en
décimal.
La représentation sur 4 bits de 1101
vaut :
– 1 x 23 + 1 x 22
+ 0 x 21 + 1 x 20
soit – 8 +
5 = – 3.
La représentation binaire de – 6
sera 1 suivi de la représentation sur 3 bits de :
– 6 + 23
= 2
qui est 010. On aura donc (– 6 )10 = (
1010 )2 dans la
représentation en complément à 2
2.2- Erreur de
débordement arithmétique d’entier
Un débordement arithmétique d’entier survient quand
un entier théorique à représenter tombe hors de la plage des valeurs
représentables en machine (c’est-à-dire hors du segment [– 2n-1 , + 2n-1
– 1 ] de Z si on a à faire à une
représentation binaire en complément à 2).
Exemples :
Supposons n = 5.
La représentation sur 5 bits
de +15
vaut 01111. Ajouter 1 au nombre binaire
01111 donne 10000. Or 10000 est la représentation sur 5 bits de –16. Ainsi, par débordement arithmétique
d’entier, +15 + 1 = –16 !
La représentation sur 5 bits de -16 vaut 10000. Retrancher 1 au nombre binaire 10000 donne 01111. Or 01111 est la représentation sur 5 bits de +15. Ainsi, par débordement arithmétique d’entier, –16 – 1 = +15 !
Une somme d’entiers positifs peut ainsi, suite à un débordement arithmétique, fournir une valeur négative ; de même, une somme d’entiers négatifs peut, par débordement, donner une valeur positive !
Pour des raisons d’efficacité, afin de ne pas
pénaliser les temps de réponses de tout calcul, les systèmes ne surveillent pas
en général les débordements arithmétiques d’entiers. Si donc un débordement se
produit, il ne provoquera pas d’erreur fatale (erreur provoquant l’arrêt du
programme), mais … le résultat obtenu sera faux.
Le débordement arithmétique d’entiers vérifie les
propriétés suivantes :
Quel que soit k appartenant
à [ 1 , 2n ] inclus dans
N, on a :
( – 2n-1 – k ) théorique = ( 2n-1
– k ) machine par
débordement négatif
( 2n-1 – 1 + k ) théorique
= ( – 2n-1 – 1 + k ) machine par débordement positif
Si le nombre de bits normalement attribué à un
entier ne suffit pas pour une application donnée, il est parfois possible
d’utiliser un type d’entier plus étendu. Ainsi en Java, il existe 4 types d’entiers
(de 1 à 4 octets).
- les calculs en réels sont susceptibles de générer en plus des erreurs d’arrondis
3.1- Représentation
des réels
L’IEEE (Institute for Electrical
and Electronic Engineers) a
défini une représentation des nombres réels couramment utilisée. Un réel simple précision est représenté sur 32
bits (ex : type float en C++), un réel double précision sur 64 bits
(ex : type double en C++). La
représentation en simple précision (respectivement double précision) est
construite comme suit :
-
le premier bit code le signe du nombre ( 0
pour +, 1 pour – )
-
les 8 (respectivement 11) bits suivants déterminent l’exposant avec un
excès de 127 (respectivement 1023),
-
et les 23 (respectivement 52) derniers bits sont pour la mantisse
normalisée. Une mantisse est normalisée quand elle est de la forme 1,…. . Le
premier bit de la mantisse normalisée étant toujours à 1, il n’est donc pas
nécessaire de mémoriser ce bit. Les 23 bits (respectivement 52) mémorisés
correspondent donc à une précision réelle de 24 bits (respectivement 53).
Les 32 bits de la représentation en
simple précision
( d1d2d3 ××× d31d32)2
désignent le nombre décimal
( – 1)d1 ´ 2(d2d3
××× d9)2 ´ 2–127 ´ (1,d10d11
××× d32)2
La norme IEEE traite le nombre réel 0.0 de façon particulière.
Exemple 1
:
Les 32 bits
suivants (simple précision) :
1100 0001 1110 0000 0000 0000 0000
0000
représentent
:
( –
1)1 ´ 2(10000011)2 ´ 2–127 ´ (1,11)2
= – 2131 ´ 2–127 ´ ( 1 + 2–1 + 2–2 )
= – 16 ´ 1,75
= – 28,0
Exemple 2 :
Déterminons la
représentation en simple précision du nombre décimal (30,0625)10
La partie entière (30)10
vaut (11110)2 en binaire et la partie fractionnaire (0,0625)10
vaut (0,0001)2 . On a ainsi :
(30,0625)10 = (11110,0001)2 =
(1,1110 0001)2 ´ 24
Dans la dernière expression
la mantisse est normalisée et le bit 1 à gauche de la virgule n’est pas conservé
en mémoire. L’exposant 4 est décalé de 127 pour devenir 131, soit (1000 0011)2 sur 8 bits.
Enfin, (30,0625)10
étant positif, le bit d1 de plus fort poids sera 0.
(30,0625)10 sera
donc représenté en simple précision par :
0 1000 0011 1110 0001 0000 0000
0000 000
3.2- Erreur de
débordement arithmétique de réel
Un débordement arithmétique de réel survient quand
un réel théorique à représenter dépasse le plus grand nombre réel représentable
en machine. L’erreur générée est fatale et provoque l’arrêt immédiat du
programme.
Exemple : division par 0.
3.3- Erreur
d’arrondi
Un erreur d’arrondi survient
quand un réel théorique à représenter tombe strictement entre deux nombres
réels voisins représentables en machine.
Ces erreurs sont plus sournoises. Elles ne provoquent pas d’erreur d’exécution (ni erreur fatale ni avertissement) mais peuvent conduire, directement ou par propagation, à des résultats erronés.
Exemple 1
:
Le nombre (1,4)10 est représenté en double précision par
0 011 1111 1111
0110 0110 0110 0110 0110 0110
0110 0110 0110 0110 0110
0110 0110
Or cette représentation n’est qu’une approximation car le motif 0110 qui apparaît dans la mantisse devrait se répéter à l’infini. L’erreur d’arrondi est donc ici une erreur intrinsèque à la représentation des nombres réels en machine.
Exemple 2
:
Soient x et y deux réels en double
précision de valeurs respectives 10+12 et 10– 11
Expression évaluée |
Valeur théoriquede l’expression |
Valeur effectivede l’expression avec x = 10+12 et y = 10– 11 |
( ( x – x ) + y ) / y |
1.0 |
1.0 |
( x + ( y – x )
) / y |
1.0 |
0.0 |
Dans la deuxième forme de
l’expression, ( y – x ) est arrondi à – x lors du calcul, ce qui conduit à un résultat
nul erroné.
Cet exemple montre notamment qu’à cause des erreurs d’arrondi, les règles habituelles d’associativité et de commutativité des opérateurs peuvent ne plus être valables en arithmétique réelle !
Quelques conseils peuvent être utiles en pratique :
-
il ne faut jamais comparer l’égalité stricte de deux réels mais
toujours les comparer à ε près
(par exemple, |x-y|<10-6)
-
il faut éviter d’additionner des nombres réels d’ordres de grandeur
très différents
-
il faut éviter de soustraire des résultats entachés d’erreurs et ayant
des valeurs voisines
-
programmer et comprendre l'exercice 3 de ce TP
Albin MORELLE