Cette page explique - en partant des bases sur l'écriture
binaire - comment on représente des nombres (entiers ou
réels) sur un ordinateur.
Elle couvre (en débordant un peu) la partie correspondante
du programme d'«informatique pour tous» (IPT) de première
année de CPGE, mais pourra j'espère être utile à toute
personne étudiant des bases d'informatique.
Les puissances de 2
Nous allons beaucoup parler de puissances de 2 dans la
suite. Voici un tableau donnant les premières.
$n$
$2^n$
I - Les entiers
1 - Écriture décimale des nombres entiers, écriture en base $B$
Pour comprendre l'écriture binaire, il peut être utile de
se replonger dans la signification de l'écriture décimale,
que nous sommes habitués à utiliser depuis notre enfance -
à tel point que nous ne faisons plus en général la
distinction entre un nombre et la façon de le représenter.
Que signifie par exemple 8473 ? Nous le voyons comme un
nombre entier, mais il s'agit en fait d'une suite finie de
caractères - appelés chiffres - représentant un nombre
entier. Le 3 correspond au chiffre des unités, le 7 à
celui des dizaines, etc. Cela peut se traduire par la
relation mathématique suivante.
$$8473 = 8.1000 + 4.100+7.10+3.1 = 8.10^3+4.10^2+7.10^1+3.10^0$$
Le choix d'utiliser 10 chiffres (de 0 à 9) et des
puissances de 10 vient probablement du fait que nous avons généralement
10 doigtsSans compter les orteils. Mais certaines cultures utilisent les orteils, ainsi que d'autres parties du corps pour compter, et utilisent donc des systèmes de numération différents., mais est mathématiquement arbitraire : il est
possible de remplacer 10 par n'importe quel entier $B\geq
2$. En base $B$, un entier sera réprésenté sous la forme
$$a_p\dots a_1a_0 = a_p.B^p+\dots + a_1.B^1+a_0.B^0$$
où les $a_i$ sont des symboles «codant» les
entiers compris entre $0$ et $B-1$.
On peut montrer la propriété suivante, qui justifie en
partieEn partie seulement ! Un autre intérêt de la notation en base $B$ est sa simplicité et la relative facilité avec laquelle elle permet d'effectuer les opérations élémentaires sur les entiers - comme l'addition ou la multiplication. Essayer de faire une multiplication en utilisant des chiffres romains permet de s'en convaincre rapidement… l'intérêt l'usage de ces notations :
Représentation des nombres entiers en base $B$
Soit $B$ un entier supérieur ou égal à 2.
Pour tout entier $n\in\mathbb{N}$, il existe $p\in\mathbb{N}$ et $(a_0,\dots a_p)$ des entiers compris entre 0 et $B-1$ tels que $$n = \sum_{i=0}^pa_iB^i$$
On notera alors $n=\overline{a_p\dots a_1a_0}^B$ - ou simplement $n=\overline{a_p\dots a_1a_0}$ s'il n'y a pas d'ambigüité sur la base.
Les $a_i$ sous la barre sont donc des entiers compris entre 0 et $B-1$ mais sont généralement représentés par $B$ symboles choisis à l'avance. Par exemple, pour la base 10, ces symboles sont 0,1,2,3,4,5,6,7,8 et 9, que l'on confond avec les nombres qu'ils représentent.
À noter qu'il n'y a pas unicité de l'écriture en base $B$ : il est toujours possible de rajouter des «0» devant
l'écriture d'un nombre sans le modifier. Par exemple, en
écriture décimale, on peut théoriquement écrire 00292 au
lieu de 292. Si l'on omet ces 0 surnuméraires en début de
nombre, on peut alors prouver un résultat d'unicité - en
toute base.
Finalement, le choix de mettre le chiffre des unités tout
à droite plutôt que tout à gauche est également largement
arbitraire : l'écriture décimale pourrait très bien
fonctionner - par convention - dans l'autre sens.
En informatique, on utilise fréquemment la base 2, dont
nous allons beaucoup parler ci-dessous. Mais notons qu'il existe d'autres bases :
La base 16 est également utilisée en informatique - par exemple pour représenter des niveaux de canaux de couleur. Les chiffres en base 16 s'écrivent usuellement 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
La base 24 est utilisée pour les heures et la 60 est utilisée pour les secondes et les minutesPourquoi 24, pourquoi 60 ? ! Mais plutôt que d'utiliser 24 et 60 symboles de chiffres (qui seraient fastidieux à retenir), on note ces chiffres en base 10. Cela oblige d'ailleurs à utiliser des séparateurs («h», «:», «,») et/ou à rajouter des «0» inutiles. Par exemple si l'on notait simplement un horaire (heure + minute) 203, on ne saurait pas si cela correspondrait à 20h03, 20h30 ou 2h03…
2 - Écriture binaire des nombres entiers
(a) L'écriture
Il s'agit du cas particulier où $B=2$. On utilisera les
symboles de chiffres $0$ et $1$. Ainsi, $\overline{110}^2$
représente l'entier $1.2^2+1.2^1+0.2^0=6$.
Comment voir sur l'écriture binaire d'un nombre s'il est pair ?
Un nombre est pair si et seulement si le chiffre
le plus à droite de son écriture binaire est 0.
Faites le parallèle avec un critère ressemblant en base 10.
Un nombre est divisible par 10
si et seulement si le chiffre le plus à droite de
son écriture décimale est 0.
Prouvez le résultat dans les deux cas.
Prouvons le résultat
directement en base $B$ quelconque. Soit $n$ un
entier dont la représentation en base $B$ est
$\overline{a_p\dots a_1a_0}$. On a donc
$n=\sum_{k=0}^pa_kB^k =
a_0+B\sum_{k=1}^pa_kB^{k-1}$. Comme $0\leq a_0\leq B-1$, cela signifie que $a_0$ est le reste de la division euclidienne de $n$ par $B$. Comme ce reste est nul si et seulement si $B$ divise $n$, on a bien le résultat voulu.
Écriture décimale
Écriture binaire
L'objectif de cette partie est de vous familiariser avec
l'écriture binaire des entiers. Il n'est pas pour
l'instant question de la représentation des entiers en
machine !
Le tableau ci-contre donne l'écriture binaire des
premiers entiers.
Voici des méthodes (naïves) pour établir la
correspondance entre les 2 colonnes.
Conversion binaire vers décimal :
Partons par exemple de $\overline{1011}^2$. On utilise
alors simplement la définition de l'écriture binaire :
$\overline{1011}^2 = 1.2^3+0.2^2+1.2^1+1.2^0=8+2+1=11$.
Conversion décimal vers binaire :
Prenons par exemple 19. On cherche à le décomposer
comme somme de puissances de 2. On commence par
chercher la plus grande puissance de 2 inférieure ou
égale à 19 - c'est $16$. On écrit donc $19 = 16 +
3$. On recommence alors avec 3. La plus grande
puissance de 2 inférieure ou égale à 3 est 2. On écrit
donc $3=2+1$. Finalement,
$19=16+2+1=2^4+2^1+2^0 =1.2^4+0.2^3+0.2^2+1.2^1+1.2^0=\overline{10011}^2$.
Une autre méthode plus efficace pour la conversion décimal vers binaire : étant donné un entier $n$, on distingue 2 cas :
Si $n$ est pair, il existe $k\in\mathbb{N}$ tel que $n=2k$ et l'écriture binaire de $n$ est celle de $k$ à laquelle on a rajouté un «0» à droite. On commence donc à écrire un «0» à droite, puis on rajoute à sa gauche l'écriture binaire de $k$ - obtenue en appliquant «récursivement» la même méthode.
Si $n$ est impair, il existe $k\in\mathbb{N}$ tel que $n=2k+1$ et l'écriture binaire de $n$ est celle de $k$ à laquelle on a rajouté un «1» à droite. On procède comme dans le point précédent, en mettant un «1» au lieu d'un «0».
Par exemple, pour $n=9$ :
9 est impair, donc $9=\overline{\dots 1}^2$,
où les pointillés correspondent à l'écriture
binaire de $\frac{9-1}{2}=4$.
4 est pair, donc $4=\overline{\dots 0}^2$,
où les pointillés correspondent à l'écriture
binaire de $\frac{4}{2}=2$. On a donc
$9=\overline{\dots 01}^2$.
2 est pair, donc $2=\overline{\dots 0}^2$,
où les pointillés correspondent à l'écriture
binaire de $\frac{2}{2}=1$. On a donc
$9=\overline{\dots 001}^2$.
L'écriture binaire de $1$ est
$\overline{1}^2$. Finalement, on obtient
$9=\overline{1001}^2$.
Trouvez l'écriture binaire de 128
10000000
Trouvez l'écriture binaire de 100
1100100
Trouvez l'écriture binaire de 63
111111
Trouver l'écriture décimale de 100101
37
Trouver l'écriture décimale de 10111
23
Entrainez-vous avec d'autres valeurs ! Vous pouvez vérifier vos résultats à l'aide du convertisseur ci-dessous.
Voici un convertisseur binaire/décimal/hexadécimal, qui permet
d'obtenir la correspondance pour des nombres entiers de longueur
arbitraire. Tapez simplement un nombre dans l'un des
champs.
Nombre en binaire : Nombre en décimal : Nombre en hexadécimal :
(b) Les opérations
Reprendre le tableau de
correspondance ci-dessus et regarder la colonne des
écritures binaires. Comment passer d'une ligne à la
suivante ?
Il s'agit simplement d'ajouter 1. On peut le faire en
posant l'addition, comme vous avez appris à le faire à
l'école primaire, mais en utilisant le fait qu'en binaire
«1+1 égale 0, je retiens 1».
Il est possible d'ajouter et de multiplier des nombres en
écriture binaire, en posant les opérations comme vous avez
appris à le faire à l'école primaire, et en utilisant les
tables d'addition et de multiplication suivantes.
+
0
1
0
0
1
1
1
10
$\times$
0
1
0
0
0
1
0
1
Tables qui sont, vous en conviendrez, plus simple à
apprendre que leurs homologues en base 10.
Faites les opérations suivantes en écriture binaire,
en les posant :
$10101+11$
11000
$1010\times 101$
110010
$11\times 10000$
110000
$100000-1$
11111
3 - Représentation machine des entiers
(a) Qu'est-ce-qu'une mémoire ?
Sans rentrer dans les détails, une mémoire est un ensemble
de composés électroniquesIl existe d'autres types de supports d'information, le but ici n'est pas de les détailler,
chacun d'entre eux pouvant être dans deuxIl existe d'autres façons de faire qui conduisent à ne pas avoir seulement 2 états. C'est par exemple le cas en informatique quantique. états différents
- par exemple : chargé/déchargé. On va noter l'un de ces
états 0, et l'autre 1.
D'un point de vue abstrait, une mémoire peut donc être vue
comme une (très longue) suite finie de 0 et de 1.
L'unité de mesure de mémoire est le bit -
correspondant à l'un des emplacements qui peut prendre la
valeur 0 ou 1.
On parle d'octet pour une suite de 8 bits. Par
exemple, «01110010» est un état possible pour un octet.
Combien y a-t-il d'états différents possibles pour un octet ?
$2^8$, c'est-à-dire $256$.
On utilise les notations suivantes :
$1o=8$ bits (1 octet)
$1Ko = 10^3o$ (1 kilooctet)
$1Mo = 10^6o$ (1 mégaoctet)
$1Go = 10^9o$ (1 gigaoctet)
$1To = 10^{12}o$ (1 téraoctet)
$1Po = 10^{15}o$ (1 pétaoctet)
L'ordre de grandeur de la taille d'un disque dur actuel
(nous sommes en 2018) est celui du téraoctet.
Quel est le nombre d'états possibles d'un disque dur de $1To$ ?
$2^{8.10^{12}} \approx 10^{24.10^{11}}$
c'est-à-dire à la louche un «1» suivi de 2400 milliards
de «0». C'est beaucoup - et en particulier nettement plus que le nombre de particules dans l'univers visible…
On souhaite coder les 26 lettres de l'alphabet
sur un nombre $n$ fixe de bits - c'est-à-dire établir une
bijection entre les 26 lettres de l'alphabet et une partie
de l'ensemble des séquences de $n$ bits possibles. De combien de bits a-t-on besoin ?
Sur $n$ bits, on pourra coder $2^n$ lettres
différentes. On cherche donc $n$ tel que $2^n\geq 26$,
et $n=5$ est le premier nombre convenable.
On considère une image constituée de $3600\times 2400$ pixels.
Pour chaque pixel, il y a trois canaux de
couleur, R, G et B (pour rouge, vert, et bleu). Chacun
de ses canaux à un niveau compris entre 0 et 255,
déterminant l'intensité de la couleur correspondante
pour le pixel considéré.
Évaluer la taille d'une telle image en
mémoire. Comparer avec l'ordre de grandeur que vous
aviez éventuellement en tête avant de faire
l'exercice.
Chaque canal est codé sur 1 octet (i.e. 8 bits,
car $2^8=256$). Chaque pixel est donc codé sur 3
octets. La taille de l'image est donc $3\times2400\times3600\approx 26Mo$. C'est un ordre de grandeur raisonnable pour une image brute sortant d'un appareil photo. En revanche, les images que l'on manipule sont souvent beaucoup plus légères, car compressées, ou composées d'un nombre de pixel moindre. On peut donner un ordre de grandeur de 500Ko pour une image destinée à être mise sur un site web.
(b) Représenter les entiers positifs
L'idée naturelle est de représenter un entier positif
par son écriture binaire vue comme une suite de
bits. Mais on se heurte à un problème dès que l'on
veut représenter deux entiers ou plus : si par exemple
on sait que la suite de bits $1001101$ correspond à
deux entiers, il y a ambigüité : on peut lire
$\underbrace{1001}\underbrace{101}$, qui correspond
aux entiers 9 et 5, ou encore
$\underbrace{100}\underbrace{1101}$, qui correspond
aux entiers 4 et 13. Idéalement, on voudrait pouvoir placer un séparateur et écrire quelquechose du genre $100|1101$ - mais il nous faudrait pour cela un 3ème symbole, «|», alors que les mémoires permettent intrinsèquement de n'en n'avoir que 2…
Une façon de résoudre ce problème est de décider que les
entiers seront toujours représentés sur un nombre fixé de
bits, quitte à rajouter des «0» en trop à gauche.
Entier
Sur 4 bits
Sur 8 bits
Sur 16 bits
Sur 32 bits
1101
00001101
0000000000001101
00000000000000000000000000001101
Cela pose évidemment un problème : sur $n$ bits, on ne pourra coder que $2^n$ entiers, en l'occurrence ceux de $0$ à $2^{n}-1$. Tenter de dépasser cette limite va créer un problème, et souvent renvoyer un message d'erreur de type «dépassement» (ou «overflow»). Par exemple, sur 16 bits, on ne peut pas dépasser 65 535, et sur 32 bits, 4 294 967 295. C'est un prix à payer pour la simplicité de la représentation. On peut utiliser plus de bits pour coder des entiers plus grands, mais il est de toute façon impossible de représenter tous les entiers (en nombre infini) sur un nombre fixé $n$ de bits (et donc sur une mémoire quelconque !), où l'on ne peut en coder que $2^n$.
Ce codage est par exemple utilisé pour les types uint8, uint16, uint32 et uint64Le «u» est pour «unsigned» - sans signe. du module SciPy de
Python.
(c) Représenter les entiers relatifs
Complément à 2 sur 4 bits
Entier
Code
Pour les entiers relatifs, la convention la plus
fréquemment adoptée est celle du complément à deux.
Sur $n$ bits, on va coder les entiers de $-2^{n-1}$ à
$2^{n-1}-1$ (il y en a bien $2^{n-1}-1-(-2^{n-1})+1=2.2^{n-1}=2^n$).
Les entiers positifs sont codés par leur écriture binaire sur $n$ bits - en rajoutant des 0 à gauche.
Les entiers $i$ strictement négatifs sont codés par l'écriture binaire de $i+2^n$ - ce qui signifie que leur code «suit» celui des entiers positifs.
Ci-contre, le codage des entiers de -8 à 7 en complément à
deux sur 4 bits.
À noter que pour trouver le codage d'un entier strictement
négatif $-i$, on peut prendre le codage de $i-1$ et transformer tous les «0» en «1» et réciproquement.
Prouver que la méthode expliquée ci-dessus pour le codage de $-i$ fonctionne.
On considère $n\in\mathbb{N}^*$, et
$i\in \{ 1\dots 2^{n-1}\}$.
Le codage de $i-1$ est son écriture binaire. Celui
de $-i$ est l'écriture binaire de $-i+2^n$.
Comme $(i-1)+(-i+2^n)=2^n-1$, dont l'écriture
binaire sur $n$ bits est $11\dots11$, on en déduit
que les codes de $i-1$ et de $-i$ sont
«complémentaires», au sens expliqué ci-dessus.
On se place en complément à deux sur 8 bits.
Quel est le code de 27 ?
00011011
Quel est le code de -1 ?
11111111
Quel est le code de -27 ?
11100101
La convention du complément à deux présente de nombreux avantages :
Les entiers positifs sont codés de façon très naturelle.
Pour tous les codes (sauf le dernier), on peut
passer au code de l'entier suivant en ajoutant 1 à
l'écriture binaire correspondante (et en tronquant à
$n$ bits pour passer de $-1$ à $0$)
Plus généralement - aux problèmes de dépassement près - ajouter 2 entiers revient à ajouter leur code en complément à 2.
Il est très facile de déterminer le signe d'un
entier codé en complément à deux : il suffit de
regarder le premier bit du code.
Nombre en décimal : Nombre en complément à deux (sur 16 bits) :
Ce codage est par exemple utilisé pour les types int8, int16, int32 et int64 du module SciPy de
Python.
À noter que pour le type entier de base (int) Python utilise un mécanisme beaucoup plus sophistiquéOn dit «de plus haut niveau». Il s'agit en l'occurrence de tableaux dynamiques. qui lui permet de gérer des entiers de taille arbitraireLimitée tout de même par la taille de la mémoire que Python a le droit d'utiliser !, ce qui est bien pratique, mais implique un coût en temps important pour les opérations arithmétique. Si le temps de calcul sur des entiers est critique pour le développement d'une application, il vaudra peut-être mieux utiliser un codage de plus bas niveau tel que celui qui vient d'être décrit.
II - Les réels
1 - Écriture binaire des réels
Revenons rapidement sur l'écriture décimale des nombres
réels. Que signifie par exemple «$7,54$» ? Il s'agit d'une
notation pour $7.10^0+5.10^{-1}+4.10^{-2}$ - qui rappelle ce qui a été vu au tout début de cette page concernant l'écriture binaire des entiers,
et où la virgule joue un rôle de séparateur - indiquant
que l'on passe à des puissances d'exposant strictement
négatif de 10.
La situation est un peu plus complexe que pour les
entiers, car tout réel ne peut pas nécessairement se
représenter avec un nombre fini de chiffres en utilisant
cette notation à virgule : penser par exemple à
$1/3=0,33333\dots$ . On peut montrer la propriété suivante.
Représentation des nombres réels en base $10$
Pour tout réel $x\in\mathbb{R}^+$, il existe $p\in\mathbb{N}$ et $(a_p, a_{p-1},\dots a_0, a_{-1}, a_{-2}\dots)$ une suite d'entiers compris entre $0$ et $9$ tels que $$x = \sum_{i=0}^pa_i10^i+\sum_{i=1}^{+\infty}a_{-i}10^{-i}$$
On note $x={a_p\dots a_1a_0,a_{-1}a_{-2}a_{-3}\dots}$ (avec la convention que l'on ne note plus les 0 après la virgule à partir du moment où la suite stationne à 0. Si elle ne stationne pas à 0, cette notation est problématique !).
La somme jusqu'à $+\infty$ est une série convergente
- cf le cours de mathématiques !
Quelques exemples:
$7.54 = 7.10^0+5.10^{-1}+4.10^{-2}$ correspond au
cas où $a_0=7$, $a_{-1}=5$, $a_{-2}=4$, et pour tout $i\geq 3$, $a_{-i}=0$.
Après le cours sur les séries - ou en voyant cette
somme comme la limite quand $n\longrightarrow +\infty$
de la somme des $n$ premiers termes d'une suite
géométrique, on montre que
$\sum_{i=1}^{+\infty}3.10^{-i}=3\sum_{i=1}^{+\infty}10^{-i}=3\frac{1}{10}\frac{1}{1-1/10}=\frac{3}{10-1}=\frac{1}{3}$. On retrouve donc le résultat annoncé ci-dessus : $1/3$ s'écrit $0,3333\dots$ où les points de suspension indiquent que la suite $(a_{-i})$ stationne à $3$.
De la même façon,
$\sum_{i=1}^{+\infty}9.10^{-i}=9\sum_{i=1}^{+\infty}10^{-i}=9\frac{1}{10}\frac{1}{1-1/10}=\frac{9}{10-1}=1$.
On obtient donc $0,9999\dots=1,0000\dots$ : même
en omettant les $0$ surnuméraires à gauche, il n'y a
pas unicité de la représentation d'un réel en écriture
décimale. On récupère cependant un résultat d'unicité s'il on exclut les «développements impropres», c'est-à-dire les suites $(a_{-i})$ qui stationnent à 9.
Le passage de l'écriture décimale à l'écriture binaire est
direct : on remplace les 10 par des 2, et on n'utilise
plus que les chiffres «0» et «1».
Représentation des nombres réels en base $2$
Pour tout réel $x\in\mathbb{R}^+$, il existe $p\in\mathbb{N}$ et $(a_p, a_{p-1},\dots a_0, a_{-1}, a_{-2}\dots)$ une suite de $0$ ou $1$ tels que $$x = \sum_{i=0}^pa_i2^i+\sum_{i=1}^{+\infty}a_{-i}2^{-i}$$
On note $x=\overline{a_p\dots
a_1a_0,a_{-1}a_{-2}a_{-3}\dots}^2$ (avec la même
convention que ci-dessus).
$\overline{10,1}^2=1.2^1+0.2^0+1.2^{-1}=2,5$.
Cherchons l'écriture binaire de $5,75$. On écrit $5,75=4+1+0,5+0,25=1.2^2+0.2^1+1.2^0+1.2^{-1}+1.2^{-2}=\overline{101,11}^2$.
Quelle est l'écriture décimale de $\overline{101,101}$ ?
$5,625$
Quelle est l'écriture binaire de $6,375$ ?
$\overline{110,011}$
Comment procéder en général pour obtenir l'écriture
binaire d'un réel $x\in\mathbb{R}^+$ ? On commence par
écrire $x=\lfloor x\rfloor + y$ - $\lfloor
x\rfloor\in\mathbb{N}$ désignant sa partie entière, et
$y\in[0,1[$ sa partie fractionnaire. On obtient l'écriture
de la partie entière en utilisant la
méthode expliquée au début de la page.
Pour la partie fractionnaire, qui va s'écrire sous la
forme $\overline{0,\dots}^2$, on remarque que pour
obtenir le premier chiffre après la virgule, il suffit
de multiplier par $2$ (i.e. de décaler la virgule vers
la droite), et de regarder le chiffre avant la virgule
(i.e. de prendre la partie entière). On procède de
même pour les chiffres suivants.
Prenons par exemple $5,75$ :
Sa partie entière est 5, dont l'écriture binaire est $\overline{101}^2$
Sa partie fractionnaire est $0,75$.
$2\times 0,75=1,5=1+0,5$, dont la partie entière est
$1$. Le premier chiffre après la virgule de $0,75$
est donc 1.
$2\times 0,5=1(=1+0)$, dont la partie entière est
$1$. Le deuxième chiffre après la virgule de
$0,75$ est donc $1$.
On a obtenu une partie fractionnaire de 0, dont l'écriture binaire est $\overline{0,0000\dots}^2\ $. On peut donc s'arrêter, et finalement, $0,75=\overline{0,11}^2$, d'où $5,75=\overline{101,11}^2$.
Cherchons maintenant l'écriture binaire de 0,6.
$2\times 0,6=1,2=1+0,2$, dont la partie entière est
$1$. Donc $0,6=\overline{0,1???\dots}^2\ $.
$2\times 0,2=0,4$, dont la partie entière est
$0$. Donc $0,6=\overline{0,10???\dots}^2\ $.
$2\times 0,4=0,8$, dont la partie entière est
$0$. Donc $0,6=\overline{0,100???\dots}^2\ $.
$2\times 0,8=1.6=1+0,6$, dont la partie entière est
$1$. Donc $0,6=\overline{0,1001???\dots}^2\ $.
On retombe sur $0,6$, donc le processus ne va
pas s'arrêter. On va toujours retomber sur la même séquence de chiffres, et ainsi $0,6=\overline{0,10011001100110\dots}^2\ $.
Comme pour l'écriture décimale, certains réelsTous ceux qui ne s'écrivent pas sous la forme $\pm\frac{m}{2^n}$, où $m,n\in\mathbb{Z}$ s'écrivent en binaire avec une infinité de chiffres après la virgule.
Déterminer l'écriture binaire de $0,1$.
$0,1 = \overline{0,0001100110011\dots}^2$
Quel est le réel dont l'écriture binaire est $\overline{0,1010101010101\dots}^2$ ?
Ce nombre est $\sum_{k=0}^{\infty}2^{-2k-1}=\frac{1}{2}\sum_{k=0}^{\infty}(1/4)^k=\frac{1}{2}\frac{1}{1-1/4}=\frac{2}{3}$.
Voici un convertisseur binaire/décimal, qui
permet d'obtenir la correspondance pour des nombres
réels positifs de longueur arbitraire. Tapez
simplement un nombre dans l'un des champs.
Nombre en décimal : Nombre en binaire :
2 - Le problème, et une première tentative pour coder les réels
Cette infinité possible de chiffres après la virgule pose un problème supplémentaire par rapport aux entiers : intuitivement, si $\mathbb{Z}$ a une infinité d'éléments «vers la droite» et «vers la gauche»Ce n'est pas - du tout - un énoncé mathématique., $\mathbb{R}$ a une infinité d'éléments «partout» : en plus du problème de représentabilité de réels «grands» se pose celui de la représentation d'une infinité de décimales, c'est-à-dire celui de la précision. Même
si l'on se restreint à $[0,1]$ par exemple, on ne pourra
jamais représenter en machine tous les réels de cet
intervalle - étant donné qu'il y en a une infinité.
Proposons une méthode naïve pour coder les réels
positifs - disons sur 64 bits. Fixons $h=10^{-5}$.
On se propose de coder le réel $i\times h$, où $i\in
\{-2^{63},\dots 2^{63}-1\}$, par la représentation en
complément à 2 de $i$. Les réels ainsi codables sont
donc régulièrement répartis entre $-2^{63}h$ et
$(2^{63}-1)h$.
Le plus grand réel représentable est
$(2^{63}-1)h\approx 10^{14}$.
Le plus petit réel strictement positif représentable est $h=10^{-5}$
Ces deux valeurs extrèmes ne sont pas très
bonnes : il y a des constantes physiques qui dépassent
allègrement $10^{14}$ dans le système international
(par exemple le nombre d'Avogadro), et d'autres
inférieures à $10^{-5}$. Le $10^{-5}$ est également une
précision trop faible si l'on manipule des nombres de l'ordre de $10^{-4}$ par exemple (on aurait alors une précision relative de
1/10). On pourrait penser à prendre un $h$ plus petit,
$h=10^{-6}$, $10^{-7}\dots$ mais ce que l'on va gagner
sur la précision et les «petits» nombres va être perdu
sur les «grands».
Le problème est que, sur 64 bits, on ne pourra pas
représenter plus que $2^{64}$ réels - ce qui est le cas
de la méthode ci-dessus. Il faut donc renoncer à
représenter les réels de façon régulière entre deux
valeurs extrémales.
On souhaiterait pouvoir représenter des réels plus
grands, plus proches de 0, avec une meilleure
précision relative pour de petits réels. A contrario,
avoir une précision de $10^{-5}$ pour des réels de
l'ordre de $10^{14}$ (i.e. avoir une précision
relative de $10^{-19}$) n'est pas nécessaire.
On va donc coder les réels avec une meilleure
précision au voisinage de 0, et une moins bonne
précision au voisinage des valeurs maximales, tout en
essayant de conserver une précision relative
sensiblement égale en tout point.
C'est ce que va permettre la représentation en virgule flottante.
3 - Représentation en virgule flottante
Tout nombre réel $x$ non-nul peut être écrit sous la forme
$$x\ =\ s\ m\ 2^e$$
où
$s$ est le signe, et vaut 1 ou -1.
$e$ est l'exposant - il s'agit d'un entier relatif.
$m$ est un réel de l'intervalle $[1,2[$, appelé mantisse.
Déterminer cette représentation pour les réels suivants :
1,4
$1,4 = +1,4\ .\ 2^0$
-2,9
$-2,9= -1,45\ .\ 2^1$
0,2
$0,2 = +1,6\ .\ 2^{-3}$
Il est beaucoup plus facile de trouver cette
décomposition en utilisant l'écriture
binaire. Considérons par exemple
$x=\overline{0,001001}^2$. On fait bouger la
virgule vers la droite pour écrire
$x=\overline{1,001}^2/\overline{1000}^2
=+\overline{1,001}^2.2^{-3}$ - on obtient donc la décomposition souhaitée, où $s=+1,\ m=\overline{1,001}^2$ et $e=-3$.
Faire varier l'exposant permet de déplacer la
virgule - d'où le nom de cette représentation.
Les $64-1-p$ bits restants pour coder la
mantisse. Celle-ci étant dans l'intervalle
$[1,2[$, son écriture binaire est de la
forme $\overline{1,\dots}^2$. Il est
inutile de coder le 1, qui est toujours
présent, et on peut donc coder la mantisse
par les $64-1-p$ premiers bits après la
virgule de son écriture binaire.
Le plus grand réel représentable est de l'ordre de
$2\ .\ 2^{2^{p-1}}$ - car la mantisse maximale est
de l'ordre de $2$, et l'exposant maximal de
l'ordre de $2^{p-1}$. Pour $p=11$, on obtient
environ $2\ .\ 10^{308}$.
Le plus petit réel strictement positif
représentable est de l'ordre de $1\ .\
2^{-2^{p-1}}$ (car la plus petit mantisse possible
est 1, et le plus petit exposant $-2^{p-1}$). Pour
$p=11$, on obtient comme ordre de grandeur
$10^{-308}$.
Si l'on considère un réel codable $x=sm2^n$, le
réel codable suivant est obtenu en ajoutant
$2^{p-63}$ à la mantisse (sauf dans le cas où
celle-ci serait codée par $p-63$ «1»). Autrement
dit, cela revient à ajouter 1 à l'écriture binaire
de la mantisse. La précision relative est donc
$\frac{(x+2^{p-63}2^n)-x}{x}\approx
2^{p-63}$. Pour $p=11$, on obtient $2^{-52}\approx
5\ .\ 10^{-15}$. Pour avoir des ordres de
grandeur en tête, en 2018, l'unité kg est
définie avec une précision de l'ordre $10^{-8}$ par
les physiciens, et l'unité s avec
une précision de l'ordre de $10^{-16}$.
On a donc bien gagné sur les différents plans par
rapport à la méthode naïve décrite ci-dessus.
4 - La norme IEEE 754
Cette section - plus technique - peut être omise
si vous ne voulez pas trop mettre les mains dans
le cambouis…
La norme IEEE 754 pour le codage des réels est
basée sur le mécanisme de la virgule flottante. C'est la
plus utilisée à l'heure actuelle par les
processeurs. Nous décrivons ici le format «double
précision» - sur 64 bits.
Il s'agit en résumé d'utiliser le codage en
virgule flottante décrit ci-dessus, avec la valeur
$p=11$ - c'est-à-dire $11$ bits pour l'exposant,
et $52$ bits pour la mantisse, avec quelques
variantes sordides (mais permettant notamment de coder 0, ce qui n'était pas possible avec la méthode expliquée dans la section précédente !).
L'exposant n'est pas représenté en
complément à 2, mais dans une
variante décalée de ce codage. La
suite de bits «$00\dots 01$» représente
$-2^{10}+2$, $«00\dots 010»$ représente
$-2^{10}+3$, etc, jusqu'à $«11\dots 110»$
qui représente $2^{10}-1$.
Suite de 11 bits : Entier codé en complément à 2 : Entier codé en complément à 2 décalé :
Les codages $«00\dots 00»$ et $«11\dots 11»$ de l'exposant ne codent pas des entiers relatifs mais correspondent à des cas particuliers :
Si l'exposant est codé par $00\dots 0$ et que la mantisse est nulle, le nombre représenté est 0 ($+0$ ou $-0$ en fait, ce qui n'a pas de sens mathématique, mais correspond à des nombres flottants différents en machine).
Si l'exposant est codé par $00\dots 0$, et la
mantisse non-nulle, au lieu de décoder la mantisse en écrivant $\overline{1,\dots}^2$, où les pointillés correspondent à la mantisse, on la décode en $\overline{0,\dots}^2$. On parle de nombre dénormalisé dans
ce cas - et l'exposant vaut alors -1022.
Si l'exposant est codé par $11\dots 1$ et que la
mantisse est nulle, le «nombre» représenté est $+\infty$ ou $-\infty$ selon le signe.
Si l'exposant est codé par
$11\dots 1$ et que la mantisse est
non-nulle, le «nombre» représenté est NaN (not a number : pas un nombre), correspondant par exemple à un résultat d'opération mathématique «indéterminée» du type $0/0$.
Dans les cas où le code de l'exposant est autre que $«00\dots 00»$ ou $«11\dots 11»$, on parle de nombre normalisé.
L'appli ci-dessous permet de se
familiariser avec cette norme.
Code sur 64 bits : Signe : Exposant : Mantisse : Nombre codé $=$
Comment déterminer le codage de 0,4 ?
On écrit sa représentation en virgule flottante : $0,4=+1,6.2^{-2}$
On code le signe (par 0)
On code l'exposant (par 01111111101)
Pour la mantisse, on commence par trouver l'écriture binaire de 0,6 : $0,6=\overline{0,1001100110011\dots}^2$. Problème : celle-ci a un nombre infini de chiffres après la virgules. Il va donc falloir tronquer ou arrondir pour obtenir une mantisse sur 52 bits. On obtient 1001100110011001100110011001100110011001100110011001 ou 1001100110011001100110011001100110011001100110011010
Vous pouvez tester avec l'application ci-dessus. Le point important est que 0,4 n'est pas représentable exactement en machine,
à l'instar de la plupart des autres nombres réels. On
ne dispose que d'approximations de ce nombre.
«Nombres flottants» est le nom donné aux nombres réels
représentables en machine par la méthode ci-dessus. En Python, le type correspondant est float.
Une fois que l'on a déterminé quels sont ces nombres, il faut déterminer une arithmétique flottante,
c'est-à-dire savoir comment les ajouter, multiplier,
quelles conventions utiliser pour NaN, $\pm\infty$,
comment arrondir etc. Cela dépasse le cadre de cette
page.
Il est important de retenir que les flottants ne
permettent pas de coder tous les réels - et que
lorsque l'on tape par exemple x = 0.4 en
Python, $0,4$ est converti en le flottant le plus proche - cf
la fin de la section précédente.
Par conséquent, dès que l'on utilise des flottants, on fait des calculs approchés.
C'est très important en pratique. S'il n'y a qu'une chose à retenir de cette page, c'est la phrase suivante, que vous pouvez écrire sur le mur le plus visible de votre chambre :
«Ne jamais faire de test d'égalité entre flottants.»
où $10**-6$ peut être modifié selon les besoins du code que l'on est en train d'écrire (s'il s'agit de comparer des réels de l'ordre de $10**-8$, ce $10**-6$ n'est pas une bonne idée…)
Une solution plus robuste est d'utiliser la fonction isclose du module math. isclose(a,b) teste si $|a-b|\leq 10^{-9}|max(a,\ b)|$, ce qui prend en compte l'ordre de grandeur des nombres testés et est une solution convenable dans la plupart des situations.
On peut également obtenir des problèmes d'overflow, ou dépassement.
>>> 10.**309
Traceback (most recent call last):
File "", line 1, in
OverflowError: (34, 'Numerical result out of range')
Dernière conséquence des problèmes d'arrondis :
les propriétés des opérations usuelles ne sont plus
nécessairement valables en arithmétique flottante. Par
exemple, l'addition n'est pas associative !