Dans une machine, tout s’écrit avec des $\color{#2563EB}{0}$ et des $\color{#2563EB}{1}$, et chaque nombre dispose d’un nombre fixé de chiffres, le plus souvent $64$. Cette seule contrainte explique des comportements déroutants : en Python, 0.1 + 0.2 ne vaut pas 0.3, et ailleurs, ajouter $1$ à un grand nombre positif peut donner un nombre négatif. Elle est aussi à l’origine de quelques-uns des bugs les plus célèbres, et les plus coûteux, de l’histoire de l’informatique.
Dans l’écriture décimale $301$, le chiffre $3$ vaut trois centaines, le $1$ une seule unité : chaque rang vaut dix fois le précédent. En base 2, il n’y a que deux chiffres, $0$ et $1$, et chaque rang vaut le double du précédent. Le même nombre $301$ s’écrit alors $(100101101)_2$ : il suffit d’additionner les poids des rangs qui portent un $1$.
Sous chaque chiffre, son poids : une puissance de 10 en décimal, une puissance de 2 en binaire.
En base $b$, l’écriture $(a_n \cdots a_1 a_0)_b$, où chaque chiffre vérifie $0 \leqslant a_i < b$, désigne le nombre
$$ a_n b^n + \cdots + a_1 b + a_0 = \sum_{i=0}^{n} a_i\, b^i. $$
La base 2 est celle des machines, faites de composants qui n’ont que deux états, passant ou bloqué, chargé ou déchargé. Chaque chiffre binaire est un bit (binary digit), et huit bits forment un octet. On peut basculer ci-dessous chaque bit d’un clic :
Pour écrire un nombre en base 2, on le divise par $2$ : le reste est le dernier chiffre, et l’on recommence avec le quotient. Les restes, lus de bas en haut, donnent l’écriture binaire.
| 301 = 2 × 150 + | 1 |
| 150 = 2 × 75 + | 0 |
| 75 = 2 × 37 + | 1 |
| 37 = 2 × 18 + | 1 |
| 18 = 2 × 9 + | 0 |
| 9 = 2 × 4 + | 1 |
| 4 = 2 × 2 + | 0 |
| 2 = 2 × 1 + | 0 |
| 1 = 2 × 0 + | 1 |
Pour revenir en décimal, la méthode de Horner évite de calculer les puissances : on lit les chiffres de gauche à droite, et à chaque nouveau chiffre on double ce qu’on a avant de l’ajouter, puisque $a_2 \cdot 4 + a_1 \cdot 2 + a_0 = (a_2 \cdot 2 + a_1) \cdot 2 + a_0$.
Les écritures binaires sont longues. Comme $16 = 2^4$, un paquet de quatre bits correspond exactement à un chiffre en base 16, ou hexadécimal, dont les chiffres sont $0$ à $9$, puis $\text{A}$ pour $10$, jusqu’à $\text{F}$ pour $15$. Pour passer du binaire à l’hexadécimal, il suffit de grouper les bits par quatre, en partant de la droite :
$(1100\,0111\,1110\,1011)_2 = (\text{C7EB})_{16} = 51\,179$ : seize bits, quatre chiffres hexadécimaux.
Un octet s’écrit donc avec exactement deux chiffres hexadécimaux, de 00 à FF, ce qui rend cette base omniprésente : adresses mémoire, adresses des cartes réseau, codes des couleurs. Une couleur d’écran est faite de trois octets, pour le rouge, le vert et le bleu :
L’écriture binaire n’est pas la seule façon de coder des entiers avec des bits. Un codeur rotatif, qui mesure l’angle d’un axe, porte un disque découpé en anneaux, un par bit, lus par des capteurs alignés. En binaire naturel, passer de $3 = (011)_2$ à $4 = (100)_2$ fait changer trois bits à la fois. Les capteurs ne basculent jamais exactement au même instant : pendant une fraction de seconde, la lecture peut donner $(111)_2 = 7$ ou $(000)_2 = 0$, très loin de la vraie position.
Le code de Gray range les entiers de sorte que deux entiers consécutifs ne diffèrent que d’un seul bit. Une lecture prise pendant une transition donne alors l’une des deux positions voisines, jamais une position aberrante.
Le code de Gray se construit par réflexion : on écrit la liste à $n$ bits, puis la même liste à l’envers, comme dans un miroir ; on ajoute un $\color{#2563EB}{0}$ devant la première moitié et un $\color{#DB2777}{1}$ devant la seconde. Deux codes voisins diffèrent toujours d’un bit, y compris à la jonction des deux moitiés, et entre le dernier et le premier.
| 1 bit | 2 bits | 3 bits |
|---|---|---|
| 0 | 00 | 000 |
| 1 | 01 | 001 |
| 11 | 011 | |
| 10 | 010 | |
| 110 | ||
| 111 | ||
| 101 | ||
| 100 |
La seconde moitié de chaque colonne est la colonne précédente lue à l'envers, précédée d'un 1.
Il existe aussi une formule directe : le code de Gray de $n$ est $n \oplus \lfloor n/2 \rfloor$, le ou exclusif de $n$ et de $n$ décalé d’un rang vers la droite, n ^ (n >> 1) en Python.
Le code porte le nom de Frank Gray, ingénieur aux laboratoires Bell, qui le brevette en 1953, mais Émile Baudot l’utilisait déjà pour le télégraphe dans les années 1870. On le retrouve dans un jeu familier : les tours de Hanoï. Numérotons les disques à partir du plus petit et comptons en code de Gray, avec autant de bits que de disques. À chaque étape, le bit qui change indique le disque à déplacer : le bit de droite pour le plus petit disque, le suivant pour le deuxième, et ainsi de suite. Les $2^n - 1$ codes successifs donnent exactement les $2^n - 1$ déplacements de la solution optimale.
Avec $n$ bits, on écrit tous les entiers de $0$ à $2^n - 1$. Ajouter $1$ au plus grand d’entre eux demanderait un bit de plus, qui n’existe pas : comme un compteur kilométrique, le résultat revient à $0$.
| taille | entiers naturels | entiers relatifs (complément à deux) |
|---|---|---|
| 8 bits | 0 à 255 | −128 à 127 |
| 16 bits | 0 à 65 535 | −32 768 à 32 767 |
| 32 bits | 0 à 4 294 967 295 | −2 147 483 648 à 2 147 483 647 |
| 64 bits | 0 à environ 1,8 × 1019 | environ ± 9,2 × 1018 |
Pour les négatifs, l’idée la plus simple est de réserver le premier bit au signe. Elle a deux défauts : $0$ a deux écritures, $+0$ et $-0$, et l’addition ordinaire ne marche plus. Sur $4$ bits, $3$ s’écrirait 0011 et $-3$ s’écrirait 1011, dont la somme posée en binaire donne 1110, soit $-6$.
Les machines utilisent le complément à deux. La règle tient en une phrase : sur $n$ bits, le bit de gauche a un poids négatif, $-2^{n-1}$, et tous les autres gardent leur poids habituel.
Un mot qui commence par 1 est négatif, puisque −8 l'emporte sur tous les autres poids réunis (4 + 2 + 1 = 7).
Il en découle tout le reste. Un mot qui commence par $\color{#DC2626}{1}$ est négatif, un mot qui commence par $\color{#2563EB}{0}$ est positif ou nul, et $0$ n’a qu’une écriture. Sur $n$ bits, on écrit les entiers de $-2^{n-1}$ à $2^{n-1} - 1$. Surtout, l’addition posée habituellement donne le bon résultat, sans aucun circuit spécial pour les négatifs : c’est la même addition que pour les naturels, en oubliant la retenue qui sortirait du mot. Pour obtenir l’opposé d’un nombre, on inverse tous les bits et on ajoute 1 :
| 3 | 0011 | le nombre |
| on inverse | 1100 | vaut −4, car x + (x inversé) = 1111 = −1 |
| + 1 | 1101 | vaut −3 |
Les $2^n$ mots se rangent naturellement sur un cercle : ajouter $1$, c’est avancer d’un cran, et après 1111 vient 0000. Les positifs occupent une moitié du cercle, les négatifs l’autre.
Le cercle montre aussi le revers du procédé. Sur $4$ bits, $5 + 7$ donne 1100, c’est-à-dire $-4$ : le vrai résultat, $12$, ne tient pas sur $4$ bits. C’est un dépassement de capacité (overflow), et le processeur ne s’arrête pas pour autant : il continue avec une valeur fausse.
Un dépassement de capacité ne prévient pas : le programme continue, avec un nombre faux. Il frappe souvent longtemps après la mise en service, le jour où un compteur finit par faire le tour du cercle.
Le numéro du niveau tient sur un octet. Au niveau 256, le compteur repasse à 0, la routine qui dessine les fruits s'emballe et couvre la moitié droite de l'écran de symboles illisibles : le niveau est impossible à finir.
Une vitesse convertie en entier signé de 16 bits dépasse 32 767 : la fusée se désintègre 37 secondes après le décollage. Le récit complet est dans la page Prouver un algorithme.
Les contrôleurs aériens du sud de la Californie perdent pendant trois heures le contact avec quelque 400 avions. Un compteur de millisecondes sur 32 bits fait le tour au bout de 232 ms ≈ 49,7 jours, et le redémarrage préventif, prévu tous les 30 jours, avait été oublié.
La NASA perd le contact avec la sonde, dont l'impacteur avait percuté la comète Tempel 1 en 2005. Son horloge comptait les dixièmes de seconde depuis l'an 2000 sur 32 bits : 232 dixièmes de seconde, c'est un peu plus de 13 ans et 7 mois.
La vidéo dépasse 2 147 483 647 vues, le plus grand entier signé de 32 bits. YouTube doit passer ses compteurs à 64 bits.
L'aviation civile américaine impose de redémarrer régulièrement les générateurs électriques : après 231 centièmes de seconde, soit 248 jours, un compteur déborde et les générateurs se mettent en sécurité, même en vol.
Une machine à sous d'un casino new-yorkais annonce un gain de plus de 42,9 millions de dollars, presque exactement 232 centimes. Le casino refuse de payer et invoque une panne.
Beaucoup de systèmes comptent les secondes écoulées depuis le 1er janvier 1970. Sur 32 bits signés, ce compteur atteindra 231 − 1 le 19 janvier 2038 à 3 h 14 min 7 s, temps universel, puis deviendra négatif : le 13 décembre 1901.
Python cache le problème : ses entiers s’allongent autant que nécessaire, au prix de calculs plus lents sur les très grands nombres. Mais les bibliothèques de calcul comme numpy, et la plupart des autres langages, utilisent des entiers de taille fixe.
Une image en donne une illustration très visible. Une photo en couleurs est un tableau de pixels, chacun fait de trois octets, pour le rouge, le vert et le bleu : c’est une image en 24 bits, qui peut afficher $256^3 = 16\,777\,216$ couleurs. Les bibliothèques de traitement d’images la rangent dans un tableau numpy d’entiers uint8, sans signe et sur un octet. Réduisons-la à 6 bits, deux par couleur : chaque valeur de $0$ à $255$ doit être remplacée par l’un de quatre niveaux, un par intervalle de $64$. Encore faut-il choisir lesquels, et faire le calcul sans sortir d’un octet.
Le port de La Rochelle. Faire glisser le curseur pour comparer l'image d'origine et l'image convertie, cliquer sur un pixel pour suivre le calcul en binaire.
Le dépassement ne se voit pas dans le code, qui paraît juste, mais il saute aux yeux sur l’image. Pour l’éviter, il suffit ici de choisir un calcul qui reste dans les bornes, ou de convertir d’abord le tableau en entiers de 16 bits, avec image.astype(np.uint16), avant de le ramener à 8 bits une fois le calcul fini.
Après la virgule, les rangs binaires valent $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{8}$, etc. Ainsi $0{,}625 = \color{#2563EB}{\frac{1}{2}} + \color{#2563EB}{\frac{1}{8}}$ s’écrit $(0{,}\color{#2563EB}{1}0\color{#2563EB}{1})_2$. Pour obtenir ces chiffres, on double : la partie entière du résultat, $0$ ou $1$, donne le chiffre suivant, et l’on recommence avec la partie après la virgule.
Avec $0{,}1$, le calcul ne s’arrête jamais : après quelques doublements, on retombe sur $0{,}2$, et tout recommence.
$0{,}1 = (0{,}0\,\color{#B45309}{0011}\,\color{#B45309}{0011}\,\color{#B45309}{0011}\ldots)_2$ : le motif $\color{#B45309}{0011}$ se répète indéfiniment.
C’est la même chose qu’en décimal, où $\frac{1}{3} = 0{,}333\ldots$ n’a pas d’écriture finie : seules les fractions dont le dénominateur ne contient que des facteurs $2$ et $5$ en ont une. En binaire, seules celles dont le dénominateur est une puissance de 2 en ont une. Or $0{,}1 = \frac{1}{10}$ et $10 = 2 \times \color{#DC2626}{5}$ : une machine ne peut garder qu’un nombre fini de chiffres du motif, et le nombre $0{,}1$ n’existe pas en machine. Seule une approximation existe.
Les physiciens écrivent la distance de la Terre au Soleil $\color{#0D9488}{+}\,\color{#2563EB}{1{,}496} \times 10^{\color{#DB2777}{11}}$ m et la masse d’un électron $\color{#0D9488}{+}\,\color{#2563EB}{9{,}109} \times 10^{\color{#DB2777}{-31}}$ kg : un signe, un nombre fixé de chiffres significatifs, la mantisse, et une puissance de dix, l’exposant, qui fait « flotter » la virgule. La machine fait de même en base 2 :
$$ x = \color{#0D9488}{\pm}\, \color{#2563EB}{1{,}f_1 f_2 \ldots f_p} \times 2^{\color{#DB2777}{e}}, $$
où la mantisse commence toujours par $1$, suivi d’un nombre fixé $p$ de chiffres binaires, et où l’exposant $e$ est un entier. Par exemple, $\color{#2563EB}{1{,}01}_2 \times 2^{\color{#DB2777}{1}} = 1{,}25 \times 2 = 2{,}5$.
Avec un nombre fixé de chiffres, les nombres représentables ne sont pas régulièrement répartis. Prenons un format minuscule, avec seulement deux ou trois chiffres après la virgule. Entre $1$ et $2$, il y a autant de nombres qu’entre $2$ et $4$, ou qu’entre $4$ et $8$ : chaque intervalle est une règle graduée de la même façon, mais de plus en plus longue. Sur la vraie droite, en bas, les nombres se serrent près de $0$ et s’espacent vers les grandes valeurs.
L’écart absolu entre deux nombres voisins grandit avec eux, mais l’écart relatif reste du même ordre : un nombre est toujours connu avec le même nombre de chiffres significatifs, qu’il s’agisse d’une masse d’électron ou d’une distance astronomique. C’est tout l’intérêt de la virgule flottante.
La norme IEEE 754, adoptée en 1985 sous l’impulsion de William Kahan, fixe les formats utilisés par presque toutes les machines. Le plus courant, la double précision, utilisée par les float de Python, occupe $64$ bits :
Les 64 bits d'un nombre en double précision, de gauche à droite.
Prenons $13\,256{,}625$. En binaire, il s’écrit 11001111001000,101, c’est-à-dire 1,1001111001000101 × 213. L’exposant stocké est $13 + 1023 = 1036$, qui s’écrit 10000001100 en binaire. La mantisse est faite des $16$ chiffres après la virgule, suivis de $36$ zéros :
Le mot de 64 bits de 13 256,625 : un nombre dyadique, stocké exactement.
Les exposants extrêmes sont réservés : tous les bits à $0$ pour zéro et pour des nombres minuscules dits dénormalisés, tous les bits à $1$ pour l’infini et pour NaN (not a number), le résultat d’une opération impossible. Le décortiqueur ci-dessous montre le mot de n’importe quel nombre ; on peut aussi cliquer sur les bits pour les changer.
Le nombre stocké pour 0.1 vaut exactement 0,1000000000000000055511151231257827021181583404541015625 : les dix-sept premiers chiffres après la virgule sont justes, la suite est l’erreur d’arrondi, de l’ordre de $5{,}6 \times 10^{-18}$. Python l’affiche 0.1, parce que c’est la plus courte écriture décimale qui redonne ce flottant, mais c’est bien ce nombre-là qui entre dans les calculs.
Chaque opération sur des flottants produit un résultat exact, aussitôt arrondi au flottant le plus proche. L’erreur relative de chaque arrondi est minuscule, au plus $2^{-53} \approx 1{,}1 \times 10^{-16}$, mais elle a des conséquences bien visibles.
0.1 + 0.2 == 0.30.1 + 0.2 = 0.30000000000000004 → FalseNe jamais tester l'égalité de deux flottants : on vérifie qu'ils sont proches, avec math.isclose.
(0.1 + 0.2) + 0.30.6000000000000001, mais 0.1 + (0.2 + 0.3) = 0.6L'addition des flottants n'est plus associative.
(1e16 + 1) - 1e160.0 au lieu de 1Au-delà de 253, deux flottants voisins sont espacés de plus de 1 : ajouter 1 ne change rien.
(1 - cos(1e-8)) / 1e-160.0 au lieu de 0.5Soustraire deux nombres très proches efface leurs chiffres significatifs communs : il ne reste que l'erreur.
Ajouter dix fois $0{,}1$ ne donne pas exactement $1$ ; la fonction math.fsum compense les erreurs d’arrondi, et depuis Python 3.12, sum le fait aussi pour les flottants. L’absorption a une conséquence surprenante : la boucle suivante, qui serait infinie avec des nombres réels, s’arrête.
Contre la compensation, il faut souvent réécrire la formule. Pour $x$ petit, $1 - \cos x$ soustrait deux nombres presque égaux ; l’identité $1 - \cos x = 2 \sin^2 \frac{x}{2}$ donne la même quantité sans soustraction :
Une erreur d’arrondi de $10^{-16}$ semble sans conséquence. Mais répétée des millions de fois, toujours dans le même sens, ou amplifiée par un calcul mal conditionné, elle finit par se voir.
Créé à 1 000 points, l'indice est recalculé des milliers de fois par jour et chaque résultat est tronqué à trois décimales au lieu d'être arrondi. Vingt-deux mois plus tard, il affiche environ 525, alors que sa vraie valeur dépasse 1 098.
Une batterie antimissile ne parvient pas à intercepter un Scud, qui tue 28 soldats américains. Son horloge accumulait, à chaque dixième de seconde, l'erreur commise sur 0,1. Le calcul est détaillé ci-dessous.
Quelques cases manquent dans une table de l'algorithme de division des premiers Pentium : 4 195 835 / 3 145 727 donne 1,33373… au lieu de 1,33382…. Intel remplace les processeurs, pour un coût de 475 millions de dollars.
À sa sortie, Excel 2007 affiche 100 000 pour 850 × 77,1, dont le résultat est 65 535. Le calcul était juste ; c'est la conversion du flottant en texte décimal qui se trompait, pour quelques nombres très proches de 65 535.
L’horloge de la batterie comptait le temps en dixièmes de seconde, et le logiciel multipliait ce compteur par $\color{#2563EB}{0{,}1}$, stocké en virgule fixe sur $24$ bits, avec $23$ chiffres après la virgule. Le développement binaire infini de $0{,}1$ était donc coupé après le $23^\text{e}$ chiffre :
$$ 0{,}1 \approx (0{,}0\color{#B45309}{0011}\color{#B45309}{0011}\color{#B45309}{0011}\color{#B45309}{0011}\color{#B45309}{0011}00)_2, \qquad \text{erreur} \approx \color{#DC2626}{9{,}5 \times 10^{-8}}. $$
Moins d’un dix-millionième, mais à chaque dixième de seconde. Après cent heures de fonctionnement sans interruption, l’horloge retardait d’un tiers de seconde, et le radar cherchait le missile à plus d’un demi-kilomètre de sa position réelle. Le correctif, qui était connu, est arrivé le lendemain.
Les flottants restent le bon outil pour la physique et l’ingénierie, où les données sont elles-mêmes des mesures approchées, à condition de garder ces pièges en tête. Quand l’exactitude est indispensable, Python offre d’autres représentations, plus lentes : les entiers, d’abord, qui sont exacts ; les fractions du module fractions, qui calculent exactement avec des rationnels ; et le module decimal, qui calcule en base 10 avec la précision choisie, comme l’exigent les calculs monétaires.