Page d'accueil de ce livre
Annexe A Numération binaire
A.1 Définitions
Le premier procédé utilisé par l'humanité pour
représenter graphiquement les nombres a sûrement
été le système des « bâtons », que l'on peut appeler
numération unaire. Il est encore en usage pour
marquer les points au ping-pong : pour noter
dix-sept points on trace dix-sept bâtons, regroupés
par paquets de cinq pour faciliter la lecture. Il n'en
reste pas moins que l'encombrement de la notation est
proportionnel à la grandeur du nombre envisagé, ce qui
est vite malcommode.
Le système que nous utilisons communément est
appelé numération de position. Dans la représentation
d'un nombre le chiffre le plus à droite est celui des unités,
le second à partir de la droite celui des dizaines, le
troisième celui des centaines, etc. Ainsi :
147 = 7 . 100 + 4 . 101 + 1 . 102 = 7 + 40 + 100
La numération de position a été inventée à Sumer il y a
4 000 ans, mais sa diffusion a été laborieuse. Notre système
utilise la base 10, c'est-à-dire que les chiffres successifs
à partir de la droite sont les coefficients des puissances
successives de 10, mais tout nombre supérieur ou
égal à 2 serait une base convenable. Les premiers comptables
sumériens utilisaient la base 60 : il était logique, alors
que la numération de position était une science de pointe,
une acquisition intellectuelle difficile, d'utiliser une
base de valeur élevée, ce qui permettait pour les
usages élémentaires (nombres inférieurs à 60) de se
ramener à l'ancien système, plus accessible.
Les anciens Gaulois utilisaient la base 20 dont
nous voyons la trace dans les termes quatre-vingt et
Quinze-Vingt, vieux noms de nombres celtiques.
La Chine antique utilisait les bases 2, 10
et 12. L'ouvrage classique de Marcel Granet
La pensée chinoise consacre un volumineux
chapitre à l'usage des nombres par les Chinois.
Ils maîtrisaient une arithmétique
tout à fait respectable, mais cette discipline était
tenue en piètre estime par rapport à l'usage noble
des nombres : la divination par la numérologie.
Soit B un entier supérieur ou égal à 2 et N un
entier strictement positif : tout entier p peut être
écrit de façon unique sous la forme :
où les di sont des entiers compris entre 0 et
B-1. C'est un théorème dont la démonstration
est laissée en exercice au lecteur.
B est appelé la base de notre système
de numération, (d0, d1, ..., dN-1) est appelé
décomposition en base B du nombre p, on la notera
(dN-1...d1 d0)B, ou lorsqu'il n'y a pas de
confusion possible sur la base utilisée simplement
dN-1...d1 d0. Les di sont les chiffres
de notre système et il est de bon ton de leur faire
correspondre à chacun un symbole spécial. Si B
est inférieur à 10 les chiffres arabes habituels
feront l'affaire. N est le nombre de chiffres de notre
nombre p en base B, une donnée importante en
informatique. Ainsi le nombre 42 s'écrit en
base 10 :
42 = 2 × 100 + 4 × 101 = (42)10 = 42
et en base 2 :
(42)10 = 0 × 20 + 1 × 21 + 0 × 22 + 1 × 23
+ 0 × 24 + 1 × 25 = (101010)2
Cela marche aussi bien sûr avec les chiffres
après la virgule, qui sont les coefficients des puissances
négatives de la base
B dans la décomposition du nombre.
A.2 Petits exemples binaires
Voyons ce que donne la base 2, qui nous
intéresse tout particulièrement. Énumérons les premiers
nombres :
| Notation décimale |
Notation binaire |
| 0 |
0 |
| 1 |
1 |
| 2 |
10 |
| 3 |
11 |
| 4 |
100 |
| 5 |
101 |
| 6 |
110 |
| 7 |
111 |
| 8 |
1000 |
| ... |
... |
| 15 |
1111 |
| 16 |
10000 |
| ... |
... |
Il sera commode de se rappeler que 210=1024 ~ 103,
220 ~ 106, etc.
Voyons l'addition : 2+3 s'écrit donc 10+11 et se calcule
ainsi, selon la méthode habituelle :
-
un plus zéro donne un et je ne retiens rien ;
- un plus un donne deux, je pose zéro et je retiens un ;
- un plus zéro donne un, le résultat s'écrit 101
et vaut bien cinq.
A.3 Conversion entre bases quelconques
Il est parfois nécessaire de convertir un nombre p
écrit dans la base B vers la base B'.
La méthode, laborieuse, est la suivante :
-
Dans la base de départ B diviser (au sens de la division
entière qui donne un quotient et un reste) p par la
nouvelle base B'. Remarquer que le reste obtenu est
forcément inférieur à B'. Diviser le quotient obtenu à
nouveau par B', puis recommencer ainsi de suite
jusqu'à l'obtention d'un quotient nul.
- Si B' > B, convertir tous les restes de B en B'. Si
B' < B c'est inutile. En toute rigueur l'algorithme
décrit est récursif, mais en pratique le nombre de
cas à examiner est réduit et les calculs peuvent se
faire de tête.
- Écrire les restes successifs de droite à gauche : c'est le
résultat cherché, l'écriture de p dans la base B'.
C'est un algorithme, il est donc programmable. Pour
les chiffres après la virgule c'est un peu plus compliqué parce
qu'il faut prévoir le cas des nombre dont l'écriture dans la
nouvelle base nécessite une
infinité de nombres après la virgule,
et alors s'arrêter.
A.4 Représentation informatique des nombres entiers
Nous allons maintenant dire quelques mots de la façon
dont sont représentés dans la mémoire d'un ordinateur les
nombres entiers.
De façon usuelle un entier est stocké dans un mot mémoire.
La taille du mot d'un ordinateur donné détermine donc la valeur
absolue maximum utilisable sur cet ordinateur, ce qui nous rappelle
qu'en informatique nous sommes contraints de demeurer dans un
univers fini. Une machine à mots de 32 bits autorisera des entiers
compris entre -2 147 483 648 et +2 147 483 647.
Principe de représentation
La représentation des nombres
est en général caractéristique de
l'architecture d'un ordinateur
donné, et non pas du langage de
programmation utilisé. Les lignes qui suivent décrivent la
représentation des nombres entiers en « virgule fixe »
et valent pour la plupart des ordinateurs contemporains
et la plupart des langages de programmation.
Si la représentation des entiers positifs se fait selon la notation de
position usuelle et n'appelle pas de remarques particulières, celle
des nombres négatifs se fait par la méthode du « complément à la base »,
qui appelle une description. Cette dernière
méthode, plus complexe au premier abord, simplifie la conception des
algorithmes de calcul comme nous allons le voir.
| Représentation physique |
Nombre représenté |
| (chaîne de chiffres binaires) |
|
| 0000 |
0 |
| 0001 |
1 |
| 0010 |
2 |
| 0011 |
3 |
| 0100 |
4 |
| 0101 |
5 |
| 0110 |
6 |
| 0111 |
7 |
| 1000 |
-8 |
| 1001 |
-7 |
| 1010 |
-6 |
| 1011 |
-5 |
| 1100 |
-4 |
| 1101 |
-3 |
| 1110 |
-2 |
| 1111 |
-1 |
Table A.1 : Représentation des entiers
Soit un ordinateur dont l'architecture matérielle met à notre
diposition, pour représenter les entiers, des emplacements de n
positions en base B, B paire.
Nous pouvons représenter Bn nombres différents :
nous prenons ceux compris entre - Bn/2 et Bn/2-1,
ce qui revient à partager l'espace des représentations disponibles en deux
parties égales, une pour les nombres négatifs et une pour les nombres
positifs. Le plus grand nombre positif représentable a une valeur absolue
plus faible de 1 que celle du plus petit nombre négatif représentable, parce
que 0 est « avec » les nombres positifs. La représentation se fera comme suit :
-
Les nombres compris entre 0 et Bn/2-1,
soit Bn/2 nombres,
seront représentés selon la notation usuelle de position ; remarquons
que le chiffre de poids fort (rang n) est toujours 0 pour ces
nombres.
- Pour représenter au moyen des combinaisons restantes les Bn/2
nombres compris entre -Bn/2 et -1 nous leur ferons correspondre,
dans cet ordre, les nombres à n chiffres binaires compris entre
Bn/2 et Bn-1. Cela revient à dire que le chiffre de poids fort
(rang n) est toujours égal à 1 et qu'un nombre négatif -p sera
représenté par le nombre obtenu en remplaçant chacun des chiffres de
p par son complément à 1 (c'est-à dire en remplaçant chaque 1 par
un 0 et chaque 0 par un 1) et en additionnant 1 au résultat, ce que
l'on appelle le complément à 2.
- Prenons un exemple avec comme base B=2 et n=4 chiffres possibles.
Les entiers représentés seront tels que décrits dans la table A.1.
Le nombre +5 est représenté par les chiffres suivants : 0101.
Le complément à 1 de cette combinaison de chiffres nous donne : 1010.
Additionnons 1 pour avoir le complément à 2 : 1011,
qui représente -5. Si nous additionnons les deux nombres en abandonnant
la dernière retenue (puisque nous n'avons que 4 chiffres par nombre) :
0101
+ 1011
= 0000
ce qui est conforme à notre attente.
L'intérêt de cette notation réside dans le fait que l'addition peut se
faire selon le même algorithme, quel que soit le
signe des opérandes, il suffira « d'oublier » la retenue éventuelle qui
donnerait un n+1ième chiffre. Évidemment, si le calcul excède
la capacité physique de la représentation, il y aura une erreur.
A.4.1 Notation hexadécimale
La représentation des nombres en base 2 est très commode pour
les ordinateurs mais moins pour les humains, parce qu'elle est encombrante
et peu lisible. La conversion entre base 2 et base 10 est laborieuse. Mais la
conversion entre la base 2 et une base puissance de 2 est beaucoup plus
maniable. La règle des faisceaux (que nous ne démontrerons pas ici) nous
apprend que chaque groupe de n chiffres d'un nombre binaire correspond
à un chiffre de ce nombre converti en base 2n. Les valeurs de n souvent
utilisées sont 3 et 4, soient les notations octale et hexadécimale. Les chiffres
de la notation octale sont les chiffres arabes de 0 à 7, ceux de la
notation hexadécimale les chiffres arabes de 0 à 9 et les lettres
majuscules de A à F qui notent respectivement les nombres 10 à 15.
Ainsi le nombre binaire :
0111 1111 0011 1000
soit en décimal 32 568, s'écrit-il en hexadécimal :
7F 38
On notera qu'un octet correspond à un nombre compris entre 0
et 255, représenté en hexadécimal par deux chiffres. Ce mode de représentation
est très utilisé par les informaticiens.
A.5 Types fractionnaires
A.5.1 Les « réels »
Ces types usurpent volontiers le qualificatif « réel », et
correspondent aux nombres en virgule flottante de l'ordinateur
utilisé, dont la notice du constructeur et celle de l'auteur du
compilateur comportent une description. Ils servent à représenter les
nombres « avec des chiffres après la virgule ».
La norme IEEE 754
définit deux formats de nombres fractionnaires que
l'on retrouve sur la plupart des ordinateurs. Elle est le plus
généralement implantée physiquement sur l'ordinateur, c'est-à-dire que
les lignes qui suivent ne s'appliquent pas à un langage particulier,
mais à l'utilisation de la plupart des ordinateurs et de la plupart
des langages de programmation.
Un type fractionnaire est défini sur un sous-ensemble borné, incomplet
et fini des rationnels. En effet, le « nombre de chiffres après la
virgule » est limité par la taille physique d'une représentation
concrète. Un tel type peut être utilisé pour représenter
approximativement les nombres réels.
A.5.2 Principe de représentation
Les nombres fractionnaires sont représentés dans les registres des
ordinateurs selon le principe de la virgule flottante. Ce principe est
inspiré de la notation familière aux scientifiques, qui préfèrent
écrire 197.106 plutôt que 197 000 000.
Soit un système de numération de base B (entier positif), un nombre x
pourra être représenté par le doublet :
[m,p] tel que : x = m . Bp
m, la mantisse du nombre x, est un nombre positif compris entre :
1 (compris) et B (exclus),
ou nul si x=0. Ceci correspondrait, en notation décimale
usuelle, à des nombres tels que :
1,000000000 à 1,9999999999
Cette mantisse m sera représentée par un nombre fixe de S chiffres
binaires : elle pourra donc prendre 2S valeurs différentes.
L'exposant p sera un entier compris entre deux valeurs MIN et MAX.
Les quatre entiers B (la base), N (le nombre de chiffres significatifs
de la mantisse), MIN et MAX (les bornes de l'exposant) suffisent à
définir un système de virgule flottante. Tout nombre réel de
l'intervalle :
]-BMAX, +BMAX[
sera approché par un nombre représentable exactement, c'est-à-dire de
la forme :
x = m . Bp
La norme IEEE 754
définit deux types de nombres en virgule flottante,
en simple ou double précision. Le tableau ci-dessous donne
aussi les caractéristiques de
la double précision sur Cray YMP, qui ne respecte pas la norme.
| |
Simple précision |
Double précision |
Cray |
| |
|
|
(double) |
| B |
2 |
2 |
2 |
| MIN |
-126 |
-1022 |
-16382 |
| MAX |
127 |
1023 |
16383 |
| S |
24 |
53 |
48 |
| |
|
|
|
| plus petite |
|
|
|
| valeur absolue |
1,1754944.10-38 |
2,225073858507201.10-308 |
|
| |
|
|
|
| plus grande |
|
|
|
| valeur absolue |
3,4028235.10+38 |
1,797693134862317.10+308 |
|
On remarquera qu'avec des emplacements de même taille physique pour
placer les nombres, Cray privilégie la largeur de l'intervalle
utilisable (ce que l'on appelle la « dynamique » de la représentation)
aux dépens de la précision. D'autre part la représentation IEEE est
dite « normalisée », c'est-à-dire que le premier chiffre de la mantisse
(devant la virgule) est toujours égal à 1 et que l'on peut donc se
dispenser de le stocker, ce qui assure 53 chiffres significatifs sur
52 bits. La virgule flottante Cray n'est pas normalisée, ce qui
accroît encore la dynamique et diminue la précision.
Voici à titre d'illustration le format physique d'un nombre à la norme
IEEE simple précision :
Figure A.1 : Format d'un nombre en virgule flottante
| S |
le bit de signe, 0 pour un nombre |
| |
positif, 1 pour un nombre négatif ; |
| |
|
| Exposant |
exposant binaire « biaisé », c'est-à-dire |
| |
que s'il est représenté sur E chiffres |
| |
binaires (E=8 ici), on ajoute à sa valeur |
| |
effective 2E-1, afin de n'avoir à |
| |
représenter que des valeurs positives ; |
| |
|
| Mantisse |
une valeur fractionnaire. Un bit à 1 implicite |
| |
figure « à gauche » du bit 22. La virgule est à |
| |
droite du bit implicite. |
En fait, la norme IEE754
est plus complexe que le résumé que nous en
donnons, et elle admet des variantes. Les valeurs conventionnelles
suivantes sont définies, ici en simple précision (les valeurs des
mantisses et des exposants sont les configurations binaires
physiques) :
| Nom |
Valeur |
Signe |
Exposant |
Mantisse |
| zéro positif |
+0 |
0 |
0 |
0 |
| zéro négatif |
-0 |
1 |
0 |
0 |
| infini positif |
+¥ |
0 |
255 |
0 |
| infini négatif |
-¥ |
1 |
255 |
0 |
| NaN (not a number) |
aucune |
1 ou 0 |
255 |
différente de 0 |
Un exemple simple emprunté au toujours précieux livre de Bertrand Meyer
et Claude Baudoin Méthodes de programmation
[45] illustrera quelques aspects intéressants de ce type
de représentation. Soit un système où B=2, N=3, MIN=-1 et MAX=2, les
nombres susceptibles d'être représentés exactement sont les suivants :
| |
p = - 1 |
p = 0 |
p = + 1 |
p = + 2 |
| m = (1,00)2 = 1 |
1/2 |
1 |
2 |
4 |
| m = (1,01)2 = 5/4 |
5/8 |
5/4 |
5/2 |
5 |
| m = (1,10)2 = 3/2 |
3/4 |
3/2 |
3 |
6 |
| m = (1,11)2 = 7/4 |
7/8 |
7/4 |
7/2 |
7 |
Figure A.2 : Axe des nombres représentés
Seules les valeurs positives ont été représentées dans le tableau et
sur le graphique, les valeurs négatives s'en déduiraient par
symétrie. On remarquera que la « densité » des nombres représentés
exactement (ou la précision absolue de la représentation) est
variable. Le lecteur pourra se convaincre facilement de ce qui suit :
-
si l'on représente les nombres réels par un tel ensemble de
nombres, l'opérateur d'égalité n'est pas utilisable (non plus que
l'inégalité d'ailleurs) ; au mieux peut-on vérifier que la
différence entre deux nombres est inférieure à un seuil que l'on se
donne, et encore à condition de s'assurer que les chiffres fractionnaires
qui produisent la différence sont significatifs ; pour un exposé
complet et original de la question on se reportera utilement au
livre de Michèle Pichat et Jean Vignes [52] ;
- la soustraction risque de provoquer une grande perte de précision
dans les calculs (cas de deux nombres « grands » mais peu différents) ;
- il est dangereux d'additionner ou de soustraire des nombres
d'ordres de grandeur différents, parce qu'une « mise au même exposant »
sera nécessaire, au prix de la précision ;
- des changements de variable judicieux peuvent augmenter la
qualité des résultats ;
- le premier chiffre de la mantisse vaut toujours 1 (on dit que la
virgule flottante est normalisée), il sera donc sous-entendu dans le
matériel.
Pour donner un tour plus concret à cet exposé, nous empruntons au
Numerical Computations Guide de Sun Microsystems
la table suivante, qui donne pour la représentation
IEEE 754
simple précision la taille des intervalles entre deux nombres
représentés exactement consécutifs,
et ce pour différents ordres de grandeur :
| x |
nextafter |
Gap |
| 0.0 |
1.1754944e-38 |
1.1754945e-38 |
| 1.0000000e+00 |
1.0000001 |
1.1920929e-07 |
| 2.0000000e+00 |
2.0000002e.00 |
2.3841858e-07 |
| 1.6000000e+01 |
1.6000002e+01 |
1.9073486e-06 |
| 1.2800000e+02 |
1.2800002e+02 |
1.5258789e-05 |
| 1.0000000e+20 |
1.0000001e+20 |
8.7960930e+12 |
| 9.9999997e+37 |
1.0000001e+38 |
1.0141205e+31 |
© copyright Éditions Vuibert et Laurent Bloch 2003
Page d'accueil de ce livre