ESIEE – Unité d’informatique IN101
et ERREURS NUMERIQUES
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 ´ 2n-1 + bn-2
´ 2n-2 + bn-3 ´ 2n-3 + ××× + b2 ´ 22 + b1
´ 21 + b0 ´ 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 ´ 2n-1 + bn-2 ´ 2n-2 + bn-3 ´ 2n-3 + ××× + b2 ´ 22 + b1
´ 21 + b0 ´ 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 ´ 23 + 1 ´ 22
+ 0 ´ 21 + 1 ´ 20
soit 5 en décimal.
La représentation sur 4 bits de 1101
vaut :
– 1 ´ 23 + 1 ´ 22
+ 0 ´ 21 + 1 ´ 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ébordement 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 :
" k Î [ 1 , 2n ] Ì 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 C++ il existe les types int et long. On peut connaître le nombre de bits alloués à une donnée d’un
type quelconque grâce à la fonction sizeof.
A noter qu’on ne gagne pas toujours en précision en passant de int à long car la norme ne garantit que : sizeof(int) £ sizeof(long) !
- 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 à e près
-
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
Albin MORELLE