Le Hollandais Volant

Je vous rassure, on va pas voir comment montrer que 1+1=3, mais plutôt pourquoi « b + a – b ≠ a ».
En fait, on va demander à l'ordinateur si b + a – b est égal à a, au moyen d'un petit programme. Ça permettra de mettre en évidence quelques faits à propos de la représentation des nombres dans un ordinateur.

On verra aussi que pour un ordinateur 0,9+0,8 est différent de 1,7.

b + a – b est différent de a

Voici le petit code source en C :

#include <stdio.h>
#include <math.h>

int main(void) {
    float a = pow(2,-10);
    float b = pow(2,59);

    if (a == b+a-b) printf("a et (b+a–b) sont égaux.");
    else printf("a et (b+a–b) ne sont pas égaux.");

    return 0;
}

Ce que fait ce programme :
- à une variable A je donne la valeur 2^(-10)
- à une variable B je donne la valeur 2^(59)
- je demande de comparer A et B+A–B, et d'afficher s'ils sont égaux si c'est le cas.

Mathématique, b+a-b = a, donc on s'attend à ce que le programme renvoie « a et (b+a-b) sont égaux ». Voyons si c'est le cas à l'exécution :

a et (b+a–b) ne sont pas égaux.

Alors que se passe t-il ?
Il faut savoir que l'ordinateur stocke les nombres dans un format précis. Ce format est un peu comme l'écriture scientifique en mathématiques : au lieu de mettre 42, on écrira +4,2 × 10^1. Pour l'ordinateur, cette écriture est appelée « virgule flottante ». Chaque élément du format d'écriture utilise un certain nombre de chiffres significatif : pour un nombre écrit sur 32 bit, il y a 1 bit pour le signe, 24 chiffres significatifs (24 bit) pour le nombre et 7 chiffres significatifs (7 bit) pour l'exposant (je ne le dit pas ici car il n'y en a pas besoin mais l'exposant et le nombre – aussi nommé « mantisse » – sont stockés en binaire dans la mémoire).

Autre chose : pour faire B+A–B, l'ordinateur utilise des priorités opératoires suivant l'ordre d'écriture, donc il fera ((B+A)–B). Voilà.

Ce qui se passe ici et qui est à l'origine de ce qui est a priori une erreur, c'est que l'addition de nombres d'ordre de grandeurs différents contribue à l'augmentation du nombre de chiffres significatifs.
Exemple : 4,0×10^5 + 1,0×10^0 = 4,000010×10^5. (on passe de deux nombres à deux chiffres significatifs à un nombre avec 7 chiffres significatifs).

Là où ça pose problème pour l'ordinateur, c'est quand le nombre de chiffres significatifs du calcul dépasse la valeur maximale autorisée : 24 en l'occurrence. L'ordinateur effectue une troncature et une erreur est faite lors du calcul (B+A) : Pour lui, A est tellement faible dans B+A, que ça ne tient plus dans la mémoire et il ne reste que B avec des zéros après. Donc B+A = B. Quand il continue son calcul, il retranche B, et ça fait 0.
Enfin, lors de la comparaison, il voit A et 0, qui sont différents d'où le message « A est différent de B+A–B ».

Pour contrer ce problème, il faut utiliser des formats de stockages adaptés. Au lieu d'utiliser les nombres à virgule flottant (float) sur 32 bits, on peut utiliser des nombres sur 64 ou 80 bits.

1.7 est différent de 0,9 + 0,8

Ce phénomène est repris d'un exemple de Sebsauvage, qui l'explique en Anglais.

Considérons le programme ici :

#include <stdio.h>

int main(void) {
    double a = 1.7;
    double b = 0.9+0.8;

    printf("a = %.1f", a);
    printf("b = %.1f", b);

    if (a == b) printf("a et b sont égaux.");
    else printf("a et b ne sont pas égaux.");

    return 0;
}

Ce qu'il fait :
- une variable A reçoit 1,7
- une variable B reçoit 0,9+0,8
- il affiche A puis B
- il nous affiche si A et B sont égaux ou non.

Là encore, mathématiquement, on devrait voir « a et b sont égaux ». Vérifions :

a = 1.7 
b = 1.7 
a et b ne sont pas égaux

Alors, où est l'arnaque ?

Vous ne le savez peut-être pas, mais 0,9 est une valeur exacte en base dix, mais pas en base deux ! Tout comme 12,5 est une valeur exacte dans l'ensemble ⅅ des nombres décimaux, mais pas dans l'ensemble ℕ des entiers naturels. Dans ℕ, 12,5 s'approche par 12.
Dans ℕ, il n'existe pas de valeur exacte de 12,5 (on peut toujours écrire 12 + 1/2, avec des chiffres appartenant à ℕ, mais on reste tout de même dans ⅅ).

De la même façon, en binaire, certains nombres (dont 0,9) n'ont pas de valeur exacte mais seulement une valeurs approchée. Du coup, lorsque l'on compare 1,7 et 0,9+0,8, à force d'erreurs d'arrondis, l'ordinateur ne voit pas la même valeur. Cette erreur est extrêmement faible (elle apparait peut-être à la 15ème ou 20ème digit binaire) mais elle suffit à tromper l'ordinateur, qui ne compare toujours que des nombres binaires.

Conclusion

J'ai trouvé assez amusant de constater ces « anomalies » de l'informatique. Je veux dire… On utilise tous les jours des nombres à virgule sur une calculatrice, pourtant la calculatrice est incapable de faire des calculs exacts avec ces nombres.

C'est tout comme le hasard… Facile à imaginer, mais impossible à générer pour un ordinateur seul.

image de lrargerich