Compléments d’arithmétique

Avant d’aborder d’autres opérations arithmétiques que l’addition et la division, il est intéressant de voir comment python supportent les nombres en notation binaire. Python supporte à la fois les conversions de décimal en binaire et vice-versa ainsi que les fonctions booléennes.

En python, on peut facilement entrer un nombre en représentation binaire en le préfixant par 0b et l’inverse avec la fonction bin comme dans l’exemple ci-dessous.

a=0b00100111
print(a)   # affiche 39
print(bin(39)) # affiche 0b100111

Le langage python supporte également les opérations booléennes bit à bit. Les principales sont listées ci-dessous:

• En python AND(a,b) s’écrit a & b

• En python OR(a,b) s’écrit a | b

• En python NOT(a) s’écrit ~ a

• En python XOR(a,b) s’écrit a ^ b

Il est aussi possible de demander à python d’effectuer des décalages à gauche et à droite. Ainsi, x << p décale la représentation binaire de x de p positions vers la gauche. De la même façon, y >> p décale la représentation binaire de y de p positions vers la droite.

Ces notations nous seront utiles pour présenter certains algorithmes dont ceux de la multiplication et de la division.

Multiplication des naturels

Dans le chapitre précédent, nous avons vu les opérations de base qui sont l’addition et la soustraction. Pour supporter la multiplication, nous pourrions construire une table de vérité et utiliser des portes AND, OR et NOT. Malheureusement, ce serait assez fastidieux pour supporter une multiplication sur 32 bits. Nous allons travailler comme pour l’addition, c’est-à-dire essayer de séparer la multiplication en une suite de calculs simples. Pour l’addition, nous avions pu travailler sur des opérations sur un bit. Malheureusement nous ne pourrons pas faire de même pour la multiplication. Par contre, il est assez facile de se rendre compte qu’une multiplication est une série d’additions. Comme nous savons déjà comment construire ces additions, nous allons pouvoir nous appuyer sur elles pour construire des circuits permettant de multiplier deux nombres entiers.

L’opération de multiplication \(a \times b\) prend deux arguments. Le premier, \(a\) est appelé le multiplicateur. Le second, \(b\) est appelé le multiplicande. Le résultat de la multiplication est appelé le produit. La multiplication se définit sur base de l’addition :

\(a \times b = \overbrace{b + b + ... + b}^{a~fois}\)

La multiplication et la division étant des opérations complexes, le livre de référence a choisi des les supporter par du logiciel. Il est intéressant de construire ces algorithmes simples en python de façon à bien comprendre comment ces opérations sont réalisées. Les ordinateurs modernes contiennent bien entendu des circuits électroniques qui implémentent ces opérations arithmétiques de façon efficace.

Pour l’opération de multiplication, un point important à prendre en compte est que la multiplication de deux nombres encodés sur n bits retourne un nombre qui peut nécessiter jusqu’à \(2 \times n\) bits. Pour s’en convaincre, il suffit de considérer les naturels encodés sur 8 bits. Le carré du plus grand de ces naturels, \(11111111\) (255 en décimal), vaut \(65025\) dont la représentation binaire est \(1111111000000001\).Lorsque l’on calcule \(A_{n-1}A_{n-2}...A_{2}A_{1}A_{0} \times B_{m-1}B_{m-2}...B_{2}B_{1}A_{0}\), le résultat est stocké sur \(m+n\) bits.

Avant d’aborder la multiplication en général, il est intéressant de considérer la multiplication par une puissance de 10. En notation décimale, pour multiplier le nombre \(C_{n-1}C_{n-2}...C_{2}C_{1}C_{0}\) par \(10^{k}\), il suffit d’insérer k fois le chiffre 0 à droite du nombre de façon à obtenir \(C_{n-1}C_{n-2}...C_{2}C_{1}C_{0}\overbrace{0..0}^{k~fois}\).

Avant d’aborder la multiplication binaire, regardons le cas particulier de la multiplication d’un nombre par 2. Si \(B_{n}B_{n-1}..B_{2}B_{1}B_{0}\) est un naturel en notation binaire, alors on peut facilement calculer le double de ce naturel en décalant tous les bits d’une position vers la gauche. Mathématiquement, on pourrait écrire que \(2 \times B_{n}B_{n-1}..B_{2}B_{1}B_{0} = B_{n}B_{n-1}..B_{2}B_{1}B_{0}0\). Cette relation est correcte et peut s’étendre à toute puissance positive de 2. Ainsi, \(2^{k} \times B_{n-1}B_{n-2}..B_{2}B_{1}B_{0} = B_{n-1}B_{n-2}..B_{2}B_{1}B_{0}\overbrace{00..0}^{k}\).

Note

Les décalages sont plus rapides que les multiplications

Les opérations de décalage beaucoup plus rapide que la multiplication entière, mais il faut les utiliser correctement. Lorsque l’on manipule des nombres stockés sur un nombre fixe de bits, il faut être attentif à deux points. Tout d’abord, le résultat de la multiplication doit pouvoir être stocké sur le même nombre de bits que l’opérande. Ainsi, si l’on travaille en représentant des naturels sur 8 bits, alors on peut calculer \(2 \times 37\) en décalant 00100101 vers la gauche, ce qui donne \(01001010\). Par contre, le décalage de 00100101 de trois positions vers la gauche donne comme résultat \(00101000\), c’est-à-dire \(40\) en notation décimale.

Le deuxième problème est que cette technique ne fonctionne pas avec tous les entiers signés. Considérons cette fois les quartets. Le quartet 1011 représente la valeur \(-5\) en notation décimale. Si on décale ce quartet d’une position vers la gauche, on obtient 0110 qui correspond à la valeur positive \(6\). Les décalages sont donc à utiliser avec précautions.

Sur base de la définition de la multiplication comme une séquence d’additions, on pourrait utiliser un algorithme simple comme celui qui est présenté ci-dessous.

def mult(multiplicande,multiplicateur):
    produit=0
    for i in range(multiplicateur):
        produit = produit + multiplicande
    return produit

Cet algorithme est inefficace lorsque le multiplicateur est grand. Son temps d’exécution augmente avec le multiplicateur. Comme la multiplication est commutative, on pourrait l’accélérer en comparant les deux facteurs à multiplier comme dans le code ci-dessous.

def mult(multiplicande,multiplicateur):
    produit=0
    if (multiplicateur<multiplicande) :
        for i in range(multiplicateur):
            produit = produit + multiplicande
    else:
        for i in range(multiplicande):
            produit = produit + multiplicateur
    return produit

Cette approche reste inefficace. Essayons de l’améliorer. Prenons comme exemple la multiplication \(123 \times 456\) en notation décimale. Celle-ci peut également s’écrire \(123 \times ( 6 \times 10^{0} + 5 \times 10^{1} + 4 \times 10^{2})\). Pour simplifier la discussion, considérons le cas simple où le multiplicande, bien qu’étant en notation décimale, ne contient que des chiffres 1 et 0.

Lorsque l’on calcule \(123 \times 101\), on calcule en fait \(123 \times ( 1 \times 10^{0} + 0 \times 10^{1} + 1 \times 10^{2})\). En distribuant, on obtient \(123 \times 1 \times 10^{0} + 123 \times 0 \times 10^{1} + 123 \times 1 \times 10^{2}\). Cette séquence d’additions peut se représenter graphiquement comme dans Fig. 26. Cette représentation nous permet d’insister sur deux points importants de la réalisation de cette multiplication « en calcul écrit ». Premièrement, à chaque étape on multiplie le multiplicande par un chiffre du multiplicateur. Deuxièmement, multiplier le multiplicande par une puissance de dix revient à le décaler vers la gauche.

Fig. 26 Une multiplication en notation décimale

Prenons un second exemple en notation binaire avec deux naturels sur 4 bits: \(11\) en notation décimale dont la représentation binaire est \(1011\) et \(10\) dont la représentation binaire est \(1010\). Leur produit vaut \(110\) en notation décimale. Lorsque l’on multiplie ces deux quartets, on obtient un résultat qui est stocké sur un octet. Le résultat est obtenu par une succession d’additions sur 8 bits. Il s’obtient en utilisant un algorithme qui fonctionne comme suit:

0. Initialisation. Le résultat est initialisé à \(0\).

1. Etape 0. L’algorithme examine le bit de poids faible du multiplicateur (\(B_0\)). Celui-ci valant zéro, on ajoute la valeur \(0 \times 2^{0} \times 00001011 = 00000000\) au résultat intermédiaire.

2. Etape 1. L’algorithme examine le bit \(B_1\) du multiplicateur. Celui valant 1, nous devons ajouter au résultat intermédiaire la valeur \(1 \times 2^{1} \times 00001011\). En notation binaire, les multiplications par une puissance de deux se réalisent facilement via un décalage vers la gauche. Dans ce cas, \(2^{1} \times 00001011 = 00010110\). Le résultat intermédiaire vaut maintenant \(00010110\).

3. Etape 2. L’algorithme examine le bit \(B_2\) du multiplicateur. Celui-ci valant zéro, on ajoute la valeur \(0 \times 2^{2} \times 00001011 = 00000000\) au résultat intermédiaire.

4. Etape 3. L’algorithme examine le bit de poids fort (\(B_3\)) du multiplicateur. Celui valant 1, nous devons ajouter au résultat intermédiaire la valeur \(1 \times 2^{3} \times 00001011\) soit \(01011000\). Le résultat intermédiaire vaut maintenant \(01101110\). C’est le résultat final.

Fig. 27 présente la succession d’additions de façon plus lisible.

Fig. 27 Une multiplication en notation binaire

Pour implémenter cette addition dans un programme python, nous pouvons utiliser le principe décrit ci-dessus avec trois variables :

• le multiplicande

• le multiplicateur

• le produit intermédiaire

Pour multiplier le multiplicateur à chaque étape, il suffit de le décaler d’un bit vers la gauche. De la même façon, pour pouvoir tester successivement les différents bits du multiplicande, il suffit de le décaler d’un bit vers la droite à chaque étape. Le programme ci-dessous présente cet algorithme en python.

def lowest_order_bit(x):
    return x & 0b0001

def mult(multiplicande,multiplicateur):
    resultat=0b00000000
    for i in range(4):
        if lowest_order_bit(multiplicateur) == 1:
            resultat = resultat + multiplicande
        multiplicande = multiplicande << 1
        multiplicateur = multiplicateur >>1
    return resultat

Cet algorithme est beaucoup plus efficace que notre première solution naïve. Le nombre d’additions qui sont calculées dépend uniquement du nombre de bits utilisés pour représenter chacun des nombres à additionner. Sur un ordinateur, ce nombre de bits est une constante.

Il est facile d’étendre cet algorithme pour supporter les entiers positifs et négatifs. Le plus simple est de d’abord déterminer le signe du résultat et ensuite d’utiliser l’algorithme ci-dessous pour multiplier les valeurs absolues des nombres. Pour rappel, la multiplication de deux nombres de même signe donne un résultat positif tandis que le résultat est négatif si ils sont de signes opposés.

Exercices

1. En utilisant l’algorithme ci-dessus, calculez \(7*9\).

2. En utilisant l’algorithme ci-dessus, calculez \((-4)*(-5)\).

2. En utilisant l’algorithme ci-dessus, calculez \((-8)*(11)\).

Note

Représentation des entiers en python

Les ordinateurs utilisent un nombre fixe de bits pour stocker les entiers. En notation en complément à deux, le plus grand nombre positif que l’on peut stocker sur 32 bits est \(2^{31}-1\), soit 2147483641. Si une opération arithmétique retourne une résultat qui est supérieur à 2147483641, celui-ci ne pourra plus être stocké sur 32 bits. La plupart des processeurs indiquent alors un problème de dépassement de capacité qui peut être traité par le logiciel qui réalise le calcul. Si ce dépassement n’est pas traité, le calcul sera erroné.

Le langage python ne souffre pas de ce problème car ce langage utilise un nombre variable de bits pour stocker les nombres entiers. Il ajuste le nombre de bits nécessaire en fonction du nombre à stocker. On peut observer ce comportement en utilisant la fonction sys.getsizeof du module sys. Cette fonction retourne la zone mémoire occupée par un type primitif ou un objet en python.

Grâce à cette fonction, on peut observer qu’un programme python utilise 28 octets pour stocker un entier mais que la zone mémoire nécessaire augmente avec la valeur de cet entier. Au-delà de \(2^{30}\), un entier occupe 32 bytes en python et la représentation du nombre \(2^{900}\) nécessite 148 octets en mémoire.

Cette adaptation dynamique de la taille des entiers dans python permet de réaliser des calculs exacts avec les nombres entiers, quel que soit le nombre considéré. Tous les langages de programmation ne sont pas aussi précis. Vous verrez l’an prochain qu’en Java et en C par exemple les entiers sont stockés sur un nombre fixe de bits, ce qui vous posera différents problèmes liés à des dépassements de capacité.

Division euclidienne

La quatrième opération arithmétique de base sur les naturels est la division euclidienne. Cette division prend deux arguments : un dividende et un diviseur. Elle retourne deux entiers : un quotient et un reste. Formellement, la relation entre ces trois entiers est: \(dividende = diviseur \times quotient + reste\). Nous nous concentrerons sur la division euclidienne appliquée aux naturels même si elle peut évidemment s’appliquer aux entiers positifs et négatifs.

Note

Division entière en python

Le langage python permet de réaliser les divisions entières de différentes façons. Si les variable x et y contiennent des nombres entiers, alors x / y et x // y (depuis python 3.5) retournent le quotient de la division euclidienne. Le reste de la division euclidienne s’obtient en utilisant l’expression x % y. Il est aussi possible d’utiliser la fonction divmod(a,b) qui retourne le quotient et le reste de la division entière entre a et b.

Avant d’aborder cette division euclidienne, il est intéressant de discuter le cas particulier de la division par deux ou par une puissance de 2. En représentation binaire, la division par deux d’un naturel revient à décaler sa représentation binaire d’une position vers la droite. A titre d’exemple, considérons le quartet \(0110\) qui représente le nombre 6 en notation décimale. Lorsque l’on décale ce quartet d’une position vers la droite, on obtient la séquence \(0011\) qui est bien la représentation binaire de 3. Ce décalage vers la droite fonctionne également pour les puissances de deux. Ainsi, pour obtenir le quotient de la division du nombre décimal 109 représenté par l’octet \(01101101\) par \(2^3\), il suffit de décaler la séquence de bits de trois positions vers la droite. Ce décalage donne \(00001101\) qui est bien la représentation de 13.

Note

Division rapide d’un entier par une puissance de deux

Le décalage fonctionne pour les naturels, mais pas pour les entiers en notation en complément à deux. Pour s’en rendre compte, considérons la valeur -5 dont la représentation binaire est \(11111011\). Si on décale cette représentation binaire de deux positions vers la droite, on obtient \(00111110\) qui est la représentation binaire du nombre \(+62\)…

On pourrait imaginer de résoudre ce problème en insérant des bits de poids fort avec la valeur 1 plutôt que 0. Dans notre exemple, cela donnerait la séquence binaire \(11111110\) qui correspond à la valeur \(-2\). C’est plus proche de la valeur attendue mais malheureusement incorrect. Soyez prudents lorsque vous utilisez des décalages pour remplacer des multiplications ou des divisions.

Pour illustrer la division euclidienne, considérons l’opération \(1011 / 10\) en notation décimale. Lorsque l’on réalise cette division en calcul écrit, on réalise en fait une suite de soustractions. Analysons ce calcul étape par étape. Chaque étape nous permet d’obtenir un chiffre du quotient. Le calcul démarre en initialisant le reste à la valeur du dividende. Nous allons d’abord déterminer la valeur du chiffre des centaines du quotient, \(Q_2\). Pour cela, nous essayons de soustraire \(1 \times 10^{2} \times diviseur\) du reste (Fig. 28). Comme son résultat est positif et vaut 11, le chiffre des centaines du quotient est connu et il vaut 1. Le reste est mis à jour à la valeur 11.

Fig. 28 Première étape de la division décimale

L’étape suivante est de déterminer le chiffre des dizaines du quotient. Pour cela, nous essayons de soustraire \(1 \times 10^{1} \times diviseur\) du reste (Fig. 29). Le résultat étant négatif, le chiffre des dizaines du quotient doit valoir 0.

Fig. 29 Deuxième étape de la division décimale

Nous pouvons maintenant réaliser la troisième soustraction pour déterminer le chiffre des unités du quotient. Pour cela, nous essayons de soustraire \(1 \times 10^{0} \times diviseur\) du reste (Fig. 30). Ce résultat est positif, le chiffre des unités du quotient vaut donc 1 et le reste de notre division également.

Fig. 30 Première étape de la division décimale

Essayons maintenant de transposer cette méthode au calcul des divisions binaires. Pour cela, considérons la division entière de \(46\) par \(5\). Cette division euclidienne retourne comme quotient la valeur \(9\) avec un reste de \(1\).

A chaque étape, on va déterminer la valeur d’un bit du quotient en commençant par le bit de poids fort. La première étape est d’essayer de soustraire \(2^{4} \times diviseur\) du dividende. En notation binaire, cette valeur s’obtient facilement en décalant le diviseur de 4 positions vers la gauche. La soustraction réalisée dans la Fig. 31 retourne un résultat négatif. Cela indique que le bit \(Q_4\) du quotient doit valoir 0.

Fig. 31 Première étape de la division binaire

La deuxième étape (Fig. 32) nous permet de déterminer la valeur du bit \(Q_3\) de notre quotient. Celui-ci vaudra 1 si en soustrayant \(2^{3} \times diviseur\) on obtient un résultat positif. C’est le cas. Le bit \(Q_3\) est donc mis à la valeur 1 et le reste prend la valeur du résultat.

Fig. 32 Deuxième étape de la division binaire

La troisième étape nous permet de déterminer la valeur du bit \(Q_2\) du quotient. Pour cela, on essaye de soustraire \(2^{2} \times diviseur\) de notre dividende intermédiaire. Le résultat de cette soustraction est négatif (Fig. 33) et \(Q_2\) prend donc la valeur zéro.

Fig. 33 Troisième étape de la division binaire

La troisième étape nous permet de déterminer la valeur du bit \(Q_1\) du quotient. Pour cela, on essaye de soustraire \(2^{1} \times diviseur\) de notre dividende intermédiaire. Le résultat de cette soustraction est négatif (Fig. 34) et \(Q_2\) prend donc la valeur zéro.

Fig. 34 Quatrième étape de la division binaire

La dernière étape (Fig. 35) nous permet de déterminer la valeur du bit \(Q_0\) de notre quotient. Celui-ci vaudra 1 si en soustrayant \(2^{0} \times diviseur\) du dividende intermédiaire on obtient un résultat positif. C’est le cas. Le bit \(Q_0\) est donc mis à la valeur 1 et le dividende intermédiaire prend la valeur du reste de notre calcul.

Fig. 35 Dernière étape de la division binaire

Le résultat final de notre division en binaire est donc :

• \(quotient=01001\)

• \(reste=0001\)

Cette procédure peut également s’écrire en python comme nous l’avons fait pour la multiplication. Une version de cet algorithme permettant de diviser un naturel représenté sur 8 bits par un naturel représenté sur quatre bits est repris dans le code ci-dessous. Cet algorithme peut être étendu pour supporter des nombres encodés sur un plus grand nombre de bits.

def div(dividende,diviseur):
    quotient=0b0000
    reste = dividende
    diviseur = diviseur << 4
    for i in range(4+1):
        r=reste-diviseur
        if( r > 0 ):
            reste=r
            quotient = quotient << 1
            quotient = quotient | 0b0001
        else:
            quotient = quotient << 1
            quotient = quotient & 0b1110

        diviseur = diviseur >> 1
    return quotient, reste

La plupart des ordinateurs utilisent des circuits logiques pour calculer efficacement les divisions euclidiennes. Ces circuits permettent de diviser des entiers, positifs et négatifs. Le fonctionnement de ces circuits sort du cadre de ce cours d’introduction.

Note

Division par zéro en python

La division euclidienne n’est pas définie lorsque le diviseur vaut zéro. Pourtant, il peut arriver que l’utilisateur demande par inadvertance de réaliser une division par zéro. Dans la plupart des langages de programmation, une telle division par zéro provoque une exception. Cette exception correspond à un signal généré par le matériel pour avertir d’une erreur lors de l’exécution d’un programme. Ce signal est intercepté par le système d’exploitation. Un système d’exploitation est un logiciel spécialisé qui contrôle les interactions entre les programmes qui s’exécutent sur l’ordinateur et le matériel. Parmi les systèmes d’exploitation les plus connus, on peut citer Microsoft Windows, Linux, MacOS, … Le système d’exploitation avertit ensuite le programme qui a tenté d’effectuer cette division par zéro. Par défaut, le système d’exploitation termine l’exécution du programme en erreur, mais il est possible dans certains langages de programmation de traiter ces erreurs de division par zéro. C’est le cas en python via le mécanisme d’exceptions. Python définit l’exception ZeroDivisionError qui correspond exactement à ce cas de figure.

Code source 2 Division par zéro en python

a = ...
b = ...
try:
  a / b
except ZeroDivisionError:
  print("Erreur")

Opérations sur les réels

Les entiers sont des nombres importants, mais ce ne sont pas les seuls types de nombres avec lesquels nous devons réaliser des opérations mathématiques. Les réels sont nettement plus importants dans de très nombreux domaines scientifiques. Les réels sont d’ailleurs les nombres que nous manipulons le plus fréquemment, que ce soit dans la vie de tous les jours pour représenter des montants en Euros ou pour réaliser des calculs scientifiques. Les constantes mathématiques importantes comme \(\pi\) (3.141592653589793) ou \(e\) (2.718281828459045) sont des réels.

Quasiment tous les ordinateurs construits depuis les années 1980s ont adopté la norme IEEE 754 pour représenter les nombres réels et réaliser des opérations mathématiques sur ces nombres. Cette norme peut être vue comme la façon d’utiliser sur un ordinateur la notation scientifique à laquelle vous avez étés habituée durant vos études secondaires. Lorsque l’on doit représenter des réels très grands ou très petits, on exprime le réel sous la forme d’une mantisse et d’un exposant. La notation standard est \(\pm m \times 10^{p}\) où \(m\) est appelée la mantisse et doit être dans l’intervalle \([1,10[\) et \(p\) est l’exposant. L’avantage de la notation scientifique est qu’elle permet de manipuler efficacement de grands et de petits nombres comme le nombre d’Avogadro, \(N_{A} = 6.02214076 \times 10^{23}\) ou la masse de l’électron, \(9.109 \times 10^{-31}\). Formellement, il n’y a pas de représentation pour le nombre 0 en utilisant la notation scientifique, mais tout le monde utilise le chiffre 0 dans ce cas.

La norme IEEE 754 permet à l’ordinateur de représenter les réels en utilisant une notation binaire qui est inspirée de la notation scientifique. Cette représentation est souvent appelée la représentation en virgule flottante. Dans cette représentation, tout nombre réel est de la forme \((-1)^{s} 1.mmmm \times 2^{eeee}\) où tant la mantisse (mmm) que l’exposant (eeee) sont en notation binaire.

Il est intéressant d’analyser plus en détails la représentation de la partie fractionnaire d’un nombre en binaire. Formellement, le nombre \(1.B_{(-1)}B_{(-2)}B_{(-3)}...B_{(-n)}\) correspond à la valeur numérique \((1 + B_{(-1)} \times 2^{-1} + B_{(-2)} \times 2^{-2} + B_{(-3)} \times 2^{-3} + ... B_{-n} \times 2^{-n})\). On peut donc aisément convertir en nombre binaire en notation fractionnaire en sa version décimal. Ainsi, \(1.1010\) correspond au nombre décimal \(1 + 1 \times 2^{-1} + 0 \times 2^{-2} + 1 \times 2^{-3} + 0 \times 2^{-4} = 1.625\)

Exercices

1. Quel est le nombre réel qui correspond à \(1.0110\) en notation binaire ?

2. Si on utilise 4 bits pour représenter la partie fractionnaire du nombre \(1.B_{(-1)}B_{(-2)}B_{(-3)}B_{(-4)}\), quels sont le plus petit réel et le plus grand réel que l’on peut représenter ?

3. Sans convertir les nombres \(A = 1.00110\) et \(B = 1.010001\), quelle relation pouvez-vous identifier entre ces deux séquences de bits ?

   • \(A = B\)

   • \(A \ne B\)

   • \(A < B\)

   • \(A > B\)

4. Quelle est la valeur décimale qui correspond au nombre binaire fractionnaire \(1.1111111111111111\) ?

La norme IEEE 754 définit deux représentations pour les réels :

• la représentation en simple précision

• la représentation en double précision

Ces deux représentations diffèrent au niveau de nombre de bits qui sont utilisés pour représenter l’exposant et la partie fractionnaire du nombre en virgule flottante. En simple précision, la partie fractionnaire est encodée sur 23 bits et l’exposant sur 8. En double précision, la partie fractionnaire est encodée sur 52 bits et l’exposant sur 11 bits. Dans les deux cas, un bit est utilisé pour indiquer si le nombre est positif ou négatif. Un nombre en simple précision occupe donc 32 bits tandis qu’un nombre en double précision occupe 64 bits.

Ces deux représentations utilisent quelques astuces dans l’encodage des nombres réels. La première astuce est que si tout nombre réel est exprimé sous la forme \((-1)^{s} \times 1.mmmm \times 2^{eeee}\), alors il n’est pas nécessaire d’inclure le premier 1 dans la représentation binaire du nombre en virgule flottante. C’est une optimisation intéressante car elle libère un bit dans la représentation binaire de ces nombres. Cependant, il y a un nombre important que l’on ne peut pas représenter sous la forme \((-1)^{s} 1.mmmm \times 2^{eeee}\) : zéro. La norme IEEE 754 contourne cette difficulté en réservant la séquence de bits \(00000..00\) pour représenter la valeur zéro.

La deuxième astuce est que le bit de poids fort de la représentation binaire contient le signe du nombre réel, 1 pour les nombres négatif et 0 pour les nombres positifs. Même si la notation en complément à deux ne contient pas de bit explicite de signe, tous les nombres entiers négatifs ont aussi leur bit de poids fort à 1.

La troisième astuce concerne l’exposant. Pour faciliter le tri des nombres en virgule flottante sur base de leur séquence binaire, l’exposant est placé dans les bits de poids fort, juste après le bit de signe. Si l’exposant étant représenté en utilisant la notation en complément à deux, alors une séquence de bits commençant par \(0 11111111 ...\) correspondrait à une valeur numériquement inférieure à \(0 00000001 ...\) ce qui rendrait ces tris compliqués. La solution choisie par la notation IEEE 754 est d’encoder les exposants en utilisant un biais de 127 en simple précision (et de 1023 en double précision). Avec ce biais, l’exposant -1 est encodé comme la séquence de bits 0111 1110 qui correspond à la valeur décimale 126.

La notation complète utilisée par la norme IEEE 754 est donc \((-1)^{Signe} \times (1 + Fraction) \times 2^{Exposant-Biais}\).

Fig. 36 Notation IEEE 754 en simple précision

Fig. 37 Notation IEEE 754 en double précision

Note

Python et la norme IEEE 754

Comme la plupart des langages de programmation, python supporte la norme IEEE 754. Par défaut, python utilise la notation en double précision pour tous les calculs avec des réels. La librairie python contient deux fonctions intéressantes qui permettent d’explorer la notation IEEE 754 :

• float.hex() permet de convertir un réel en notation hexadécimale sous la forme [sign] ['0x'] integer ['.' fraction] ['p' exponent]

• float.fromhex() réalise la conversion inverse

Ces deux fonctions permettent d’explorer différents nombres réels en virgule flottante.

print((0.0).hex())  # affiche 0x0.0p+0
print((4.0).hex())   # affiche 0x1.0000000000000p+2
print((1.25).hex())  # affiche 0x1.4000000000000p+0
print((1000000000.0).hex()) # affiche 0x1.dcd6500000000p+29
print(float.fromhex('1.8p+0')) # affiche 1.5
print(float.fromhex('1.fffffffffp+0')) # affiche 1.999999999985448

Exercices

1. Quel est le plus petit nombre positif que l’on peut représenter en double précision ?

2. Quel est le plus petit nombre négatif que l’on peut représenter en double précision ?

Lorsque l’on réalise des opérations mathématiques sur les nombres en virgule flottante, il se peut que le résultat soit trop grand ou trop petit pour être représenté en utilisant la notation IEEE 754. Dans ce cas, le circuit électronique va générer une exception ou interruption. Ce signal sera intercepté par la système d’exploitation qui avertira le programme du problème détecté.

Toutes les opérations arithmétiques peuvent être réalisées avec la notation en virgule flottante. Cependant, la notation en virgule flottante pose plusieurs problèmes qui sont liés au nombre de bits pour encoder la mantisse et l’exposant dont il est important d’être conscient. Afin de les illustrer, considérons d’abord une addition en utilisant la notation scientifique : \(9.998 \times 10^2 + 2.789 \times 10^{-1}\). Nous supposerons que notre représentation décimale nous permet uniquement de stocker 4 chiffres décimaux.

La première étape pour réaliser cette addition est de ramener les deux nombres à la même puissance de dix. Nous devons donc ramener \(2.789 \times 10^{-1}\) sous la forme \(x \times 10^{2}\). Notre addition est donc \(9.998 \times 10^2 + 0.003 \times 10^{2}\) où \(0.003 \times 10^{2}\) est l’arrondi de \(2.789 \times 10^{-1}\). Cette opération a provoqué une première perte de précision.

Nous pouvons maintenant additionner les mantisses de nos deux nombres: \(9.998 + 0.003 = 10.001\). Le résultat de notre addition est \(10.001 \times 10^{2}\), soit \(1.0001 \times 10^{3}\). Malheureusement, ce résultat contient cinq chiffres décimaux alors que notre représentation ne permet qu’en stocker 4. Nous devons donc à nouveau arrondir la mantisse. Le résultat final de notre addition en virgule flottante \(9.998 \times 10^2 + 1.789 \times 10^{-2} = 1.000 \times 10^{3}\). Le résultat obtenu par ce calcul est à comparer au résultat exact: \(1000.0789\).

En pratique, l’ordinateur utilisera la représentation binaire des nombres pour réaliser les opérations mathématiques, mais des problèmes similaires vont se poser: la mantisse et l’exposant contiennent chacun un nombre finis de bits. A chaque étape d’un calcul, il faut potentiellement réaliser un arrondi pour que le résultat tienne dans la représentation en virgule flottante choisie. En simple précision, sachant que l’on utilise des nombres encodés sur 32 bits, on peut représenter au maximum \(2^{32} = 4294967296\) réels différents. Vu la façon dont séquences de bits sont encodées, on remarque aisément que la moitié de ces nombres sont dans l’intervalle \([-1,1]\) et l’autre moitié sert à représenter des réels dont la valeur absolue est comprise entre \(1\) et \(2^{127}\). Dans cet intervalle, nous ne pouvons représenter que \(2^{30}\) réels différents parmi l’infinité de réels qui existent.

Pour illustrer les imprécisions liées aux nombres en virgule flottante, il est intéressant de calculer les puissances de 3. Si l’on calcule \(3^{33}\) comme une multiplication d’entiers, on obtient \(5559060566555523\) comme résultat. Le résultat est identique lorsque l’on calcule cette valeur avec une multiplication de réels: \(5559060566555523.0\). Par contre, si l’on multiplie ce dernier nombre par \(3.0\), on obtient \(1.6677181699666568e+16\) comme résultat alors que la valeur exacte est \(16677181699666569\). Les erreurs relatives augmentent pour de plus grands nombres. Ainsi, \(3^{50}\) vaut \(717897987691852588770249\) lorsque le calcul est réalisé avec des entiers. En virgule flottante, le résultat obtenu est \(7.178979876918526e+23\).

Note

Les opérations en virgule flottante ne sont pas toujours associatives

En mathématique, vous avez l’habitude d’utiliser la propriété d’associativité qui implique que \((a + b) + c = a + (b +c)\). Cette propriété est très pratique car elle vous permet de réaliser une opération arithmétique dans l’ordre dans lequel vous le souhaitez. En virgule flottante, cette propriété n’est pas toujours vérifiée, notamment lorsque l’on utilise des nombres réels de valeur très différentes. L’exemple ci-dessous en python devrait vous convaincre:

import math

a=1.234 * math.pow(10,56)
b=-a
c=5.678 * math.pow(10,-23)

print(a+b+c) # affiche 5.678e-23
print(a+(b+c)) # affiche 0.0

Il existe des techniques qui permettent de réaliser des calculs les plus précis possibles en virgule flottante. Certaines d’entre elles seront présentées dans le cours d’algorithmique numérique.

Les dépassements de capacité et les divisions par zéro peuvent provoquer des exceptions en python lorsque l’on travaille avec des réels.

import math

a = math.exp(1000)  # provoque OverflowError: math range error
b = 24.0 / 0.0 # provoque ZeroDivisionError: float division by zero

En python, le nombre float('inf') est utilisé pour représenter une valeur infinie. Elle pourrait être utilisée en cas de dépassement de capacité comme dans la fonction ci-dessous:

import math

def myexp(x):
    try:
        return math.exp(x)
    except OverflowError:
        return float('inf')