ESIEE – Unité d’informatique IN101

 

 

 

REPRÉSENTATION DES NOMBRES

et ERREURS NUMÉRIQUES

 

 

Référence :

« Analyse numérique pour l’ingénieur », André Fortin, Editions de l’Ecole Polytechnique de Montréal

 

 

1. Rappel

Pour transformer un entier naturel N exprimé en base 10 dans sa représentation en base 2, il faut déterminer les chiffres binaires bi tels que :

            ( 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

On obtient successivement les valeurs des bits b0 , b1 , b2 , … , bn-2 , bn-1 par la méthode suivante :

            Tant que N =/= 0 faire

                        bit <- N modulo 2

                        N <- N / 2       // division entière

            FinTantQue

 

Exemple :

            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. Nombres entiers

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).

La tentation existe aussi parfois de quitter les entiers pour passer en réels en espérant étendre la plage de valeurs possibles. Ce choix ne serait pas judicieux pour deux raisons (voir section suivante) :

-         le nombre de chiffres significatifs de la mantisse d’un nombre réel est du même ordre de grandeur que celui d’un entier

-         les calculs en réels sont susceptibles de générer en plus des erreurs d’arrondis

 

 

3. Nombres réels

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éorique

de l’expression

Valeur effective

de 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