CHAPITRE 8 : QUAND LE BINAIRE NE TOMBE PAS JUSTE

Ouvrez une console Python et tapez 0.1 + 0.2. La réponse n'est pas 0,3, mais 0,30000000000000004. Ce n'est pas un bogue de Python : la même chose se produit en C, en Java, en JavaScript, dans un tableur. C'est une conséquence directe de tout ce que nous avons vu, et ce dernier chapitre explique exactement d'où elle vient.

Le développement qui ne s'arrête jamais

Reprenons la méthode du chapitre 5 pour convertir 0,1 en binaire.

0,1 x 2 = 0,2  ->  0   reste 0,2
0,2 x 2 = 0,4  ->  0   reste 0,4
0,4 x 2 = 0,8  ->  0   reste 0,8
0,8 x 2 = 1,6  ->  1   reste 0,6
0,6 x 2 = 1,2  ->  1   reste 0,2   ← le reste 0,2 est deja passe

0,1 = 0,0 0011 0011 0011 ...  en base 2

Au cinquième tour, le reste 0,2 réapparaît. Or le reste détermine entièrement la suite du calcul : la machine va donc refaire exactement les mêmes quatre opérations, indéfiniment. Les bits 0011 se répètent sans fin.

Ce n'est pas une faiblesse de l'ordinateur, c'est une propriété arithmétique. 0,1 vaut 1/10, et 10 = 2×5. Le facteur 5 ne peut jamais être épuisé par des divisions par 2.

Que range vraiment la machine ?

La mantisse ne fait que 23 bits. Il faut donc couper, et arrondir au plus proche. Voici le codage de 0,1 en simple précision :

0,1 = 0,0 0011 0011 0011 0011 0011 0011 ...
    = 1,1001 1001 1001 1001 1001 1001 ... x 2^-4

Eb = -4 + 127 = 123 = 01111011

mantisse brute  : 10011001100110011001100|1100...
                                          ^ le 24e bit vaut 1
                                            on arrondit au superieur

mantisse stockee: 10011001100110011001101

resultat : 0 01111011 10011001100110011001101
           soit 3D CC CC CD en hexadecimal

Le nombre réellement stocké n'est donc pas 0,1 mais :

13 421 773 / 134 217 728 = 0,100000001490116…

L'écart vaut environ 1,5×10⁻⁹. C'est minuscule, et c'est très exactement ce qui fera échouer un test d'égalité.

D'où vient le 0,30000000000000004

Dans un double, 0,1 et 0,2 sont chacun arrondis. Leur somme est arrondie à son tour. Et le résultat de ces trois arrondis successifs ne tombe pas sur le même motif que l'arrondi de 0,3.

0,1 stocke -> 0,1000000000000000055511151...
0,2 stocke -> 0,2000000000000000111022302...
leur somme -> 0,3000000000000000444089209...
0,3 stocke -> 0,2999999999999999888977697...

0,1 + 0,2 == 0,3  ->  FAUX

Chaque étape est correcte : le processeur donne à chaque fois le flottant le plus proche du résultat exact. C'est l'accumulation qui décale, et aucune opération n'a « mal » travaillé.

Ne testez jamais l'égalité de deux flottants. Comparez leur écart à une tolérance : |a − b| < ε.

Le choix de ε dépend de l'ordre de grandeur des nombres comparés ; pour des valeurs autour de 1 en double précision, 10⁻⁹ est un ordre de grandeur raisonnable.

La densité : tous les écarts ne se valent pas

Deuxième surprise, moins connue que la première mais plus dangereuse. Les nombres représentables ne sont pas répartis régulièrement sur la droite réelle.

Chaque intervalle [2^k ; 2^k+1] contient exactement le même nombre de valeurs : 2²³ = 8 388 608 en simple précision. Mais l'intervalle est deux fois plus large que le précédent. Donc le pas double à chaque puissance de deux.

Conséquence spectaculaire : en simple précision, au-delà de 2²⁴ = 16 777 216, le pas devient supérieur à 1. Deux entiers consécutifs ne sont plus distinguables.

en simple precision :
   16 777 216  ->  4B 80 00 00
   16 777 217  ->  4B 80 00 00    le meme motif !

L'absorption

Le même phénomène sous une autre forme. Prenons, toujours en simple précision :

x = 100 000 000,0      (1e8)
y = x + 1              ->  100 000 000,0
z = y - x              ->  0,0

on a ajoute 1, puis repris 1, et on obtient 0
au lieu de 1

Autour de 10⁸, le pas en simple précision vaut environ 8. Ajouter 1 ne change aucun bit : le résultat exact est arrondi sur le même flottant. Le petit nombre est absorbé par le grand.

C'est le piège classique des boucles d'accumulation : si l'on somme un million de petites valeurs dans un total qui grandit, les dernières ne comptent plus. La parade consiste à sommer du plus petit au plus grand, ou à employer un algorithme de sommation compensée.

Sept règles pour programmer sans mauvaise surprise

1. Jamais d'égalité sur des flottants. Comparez l'écart à une tolérance.
2. Jamais de flottant pour de l'argent. Comptez en unités entières indivisibles, en francs CFA, en centimes, en millièmes, avec un entier 64 bits ou un type décimal.
3. Jamais de flottant comme compteur de boucle. for (x = 0; x != 1; x += 0.1) ne s'arrête pas : en double, la somme de dix fois 0,1 vaut 0,9999999999999999.
4. Préférez double à float sauf contrainte de mémoire ou de bande passante. Sept chiffres sûrs s'épuisent vite.
5. Méfiez-vous des différences de nombres proches. Soustraire deux valeurs voisines détruit les chiffres significatifs : c'est l'élimination catastrophique.
6. Sommez du plus petit au plus grand quand vous accumulez beaucoup de termes.
7. Ne concluez pas qu'un calcul est faux parce qu'il affiche 0,30000000000000004. Le calcul est juste ; c'est la question qui était mal posée.

Pour finir

Rien de tout cela n'est un défaut de l'ordinateur. La norme IEEE 754 est un compromis d'ingénierie remarquable : elle fait tenir dans 32 bits une étendue de plus de soixante-dix ordres de grandeur, avec sept chiffres significatifs garantis, et des opérations qui s'exécutent en une poignée de cycles.

Le prix à payer est que l'ensemble des nombres représentables est fini, alors que les nombres réels sont infinis, et infiniment denses. Toute la difficulté du calcul numérique tient dans cet écart. Le programmeur qui sait d'où il vient écrit du code qui résiste ; celui qui l'ignore écrit du code qui marche sur ses jeux d'essai et se trompe en production.

0,7 x 2 = 1,4  ->  1   reste 0,4
0,4 x 2 = 0,8  ->  0   reste 0,8
0,8 x 2 = 1,6  ->  1   reste 0,6
0,6 x 2 = 1,2  ->  1   reste 0,2
0,2 x 2 = 0,4  ->  0   reste 0,4  ← deja vu