Représentation des flottants

I/ Présentation du phénomène

1) Une expérience en Python 3

Si on teste le script suivant :

p = 0
while p<1:
    p += 0.1
    print(p)

sur une machine à 32 bits

2) Résultat

On obtient alors l'affichage suivant dans la console :

0.1
0.2
0.30000000000000004
0.4
0.5
0.6
0.7
0.7999999999999999
0.8999999999999999
0.9999999999999999
1.0999999999999999

3) Interprétation

On constate l'accumulation d'erreurs d'approximation, ce qui révèle qu'en Python 3, 3/10 n'est pas représenté exactement en machine. En fait, il en est de même pour 1/10 et cela n'est pas propre à Python 3, mais c'est la conséquence de la représentation approchée des nombres décimaux en binaire.

II/ Flottants et dyadiques

1) La norme IEEE 754

Sur une machine 32 bits, en C, les flottants sont représentés sur 32 bits, dont 1 pour le signe (+ ou -), 8 pour l'exposant (la puissance de 2, un entier relatif) et 23 pour la mantisse. Cela permet donc de représenter en binaire 232 réels différents. Soit un peu plus de 4 milliards de réels différents. Mais comme il y a une infinité de réels (ℵ1 selon l'hypothèse du continu), il est clair que l'on ne peut pas représenter sous forme de flottants tous les réels.

Même avec le type long en C sur une machine 32 bits, et ses 11 bits d'exposant et 52 bits de mantisse, les 264 (soit plus de 6×1016) flottants possibles ne suffisent pas à représenter tous les réels en machine.

L'exposant est la puissance de 2 qui intervient dans la valeur du réel représenté. Par exemple, les nombres 3, 6 et 12 ont la même mantisse (1000... en binaire) mais des exposants différents (respectivement 1, 2 et 3 car par exemple 1,5×23=12).

2) Nombres décimaux et dyadiques

Certains flottants ne sont pas des nombres réels. Les infinis -∞ et +∞ mais même des flottants qui ne sont pas des nombres du tout (NaN).

Ce qui surprend c'est que même des nombres comme 1/10 ne soient pas représentés exactement comme des flottants.

En fait les nombres représentés par des flottants sont des fractions dyadiques, et 1/10 ne l'est pas.

Définition : On appelle dyadique le quotient d'un entier relatif, par une puissance de 2.

3) Inclusion

Tout nombre dyadique est décimal. En effet, par définition, un nombre dyadique s'écrit a/2p où a∈Z et p∈N. Mais on obtient le même nombre en multipliant en haut et en bas par 5p, or (a×5p)/(2p×5p) =(a×5p)/(2×5)p=(a×5p)/10p est un nombre décimal.

III/ Preuves par l'absurde

1) 3/10 n'est pas dyadique

En effet, s'il existait deux nombres entiers a et p tels que 3/10=a/2p, on aurait, par produit en croix, 3×2p=10×a. Il y aurait donc un nombre de la forme 3×2k divisible par 10, c'est-à-dire dont l'écriture décimale se termine par un 0.

Le programme C suivant permet de chercher une valeur de k possible :

int k, n = 3;
for (k = 0; k<=10; k += 1) {
    n *= 2;
    printf("Le terme de rang %d est %d\n",k,n);
}

En regardant le dernier chiffre on ne voit pas de 0 :

Le terme de rang 0 est 6
Le terme de rang 1 est 12
Le terme de rang 2 est 24
Le terme de rang 3 est 48
Le terme de rang 4 est 96
Le terme de rang 5 est 192
Le terme de rang 6 est 384
Le terme de rang 7 est 768
Le terme de rang 8 est 1536
Le terme de rang 9 est 3072
Le terme de rang 10 est 6144

On peut ne calculer que le dernier chiffre avec cette variante :

int k, n = 3;
for (k = 0; k<=40; k += 1) {
    n *= 2;
    n %= 10;
    printf("%d\t",n);
}

qui donne

6	2	4	8	6	2	4	8	6	2	4
8	6	2	4	8	6	2	4	8	6	2
4	8	6	2	4	8	6	2	4	8	6
2	4	8	6	2	4	8	6

On aperçoit une périodicité 6,2,4,8 qui ne comprend pas le chiffre 0. Il suffit de prouver cette périodicité pour en déduire l'impossibilité que 3/10 soit un flottant.

2) 1/10 n'est pas dyadique

La périodicité peut se montrer par induction structurelle sur ce graphe représentant le double modulo 10 :

%3 0 0 0->0 1 1 2 2 1->2 4 4 2->4 8 8 4->8 3 3 6 6 3->6 6->2 8->6 5 5 5->0 7 7 7->4 9 9 9->8

On voit qu'en partant de 3, on passe effectivement par 6, 2, 4 et 8 en cycle et que ce cycle ne passe pas par 0.

Mais en partant de 1 sur le même graphe, on voit qu'on entre là aussi dans ce cycle (mais en commençant par 2, pas par 6) et là encore, cela prouve que 1/10 n'est pas un flottant.

En fait le seul moyen d'arriver à un multiple de 10 sans y être déjà, c'est de partir d'un multiple de 5. Ainsi les nombres 0,5 et 1,5 par exemple sont des flottants.

2) 1/100 n'est pas dyadique

En refaisant un graphe similaire mais modulo 100 on constate que 1/100 n'est pas dyadique non plus :

%3 0 0 0->0 1 1 2 2 1->2 4 4 2->4 8 8 4->8 3 3 6 6 3->6 12 12 6->12 16 16 8->16 5 5 10 10 5->10 20 20 10->20 24 24 12->24 7 7 14 14 7->14 28 28 14->28 32 32 16->32 9 9 18 18 9->18 36 36 18->36 40 40 20->40 11 11 22 22 11->22 44 44 22->44 48 48 24->48 13 13 26 26 13->26 52 52 26->52 56 56 28->56 15 15 30 30 15->30 60 60 30->60 64 64 32->64 17 17 34 34 17->34 68 68 34->68 72 72 36->72 19 19 38 38 19->38 76 76 38->76 80 80 40->80 21 21 42 42 21->42 84 84 42->84 88 88 44->88 23 23 46 46 23->46 92 92 46->92 96 96 48->96 25 25 50 50 25->50 50->0 52->4 27 27 54 54 27->54 54->8 56->12 29 29 58 58 29->58 58->16 60->20 31 31 62 62 31->62 62->24 64->28 33 33 66 66 33->66 66->32 68->36 35 35 70 70 35->70 70->40 72->44 37 37 74 74 37->74 74->48 76->52 39 39 78 78 39->78 78->56 80->60 41 41 82 82 41->82 82->64 84->68 43 43 86 86 43->86 86->72 88->76 45 45 90 90 45->90 90->80 92->84 47 47 94 94 47->94 94->88 96->92 49 49 98 98 49->98 98->96 51 51 51->2 53 53 53->6 55 55 55->10 57 57 57->14 59 59 59->18 61 61 61->22 63 63 63->26 65 65 65->30 67 67 67->34 69 69 69->38 71 71 71->42 73 73 73->46 75 75 75->50 77 77 77->54 79 79 79->58 81 81 81->62 83 83 83->66 85 85 85->70 87 87 87->74 89 89 89->78 91 91 91->82 93 93 93->86 95 95 95->90 97 97 97->94 99 99 99->98

IV/ Exemple

On peut montrer par récurrence que la suite

est géométrique de raison (1-√5)/2, et par conséquent, tend vers 0. Pour le vérifier expérimentalement, on peut la programmer en C :

double a,b,temp;
int i;
a = 1;
b = (1-sqrt(5))/2;
for (i=0;i<20;i+=1) {
    temp = b;
    b += a;
    a = temp;
    printf("%f\tet\t %f\n",a,b);
}

Au début, on dirait effectivement que la suite tend vers 0 :

-0.618034	et	 0.381966
0.381966	et	 -0.236068
-0.236068	et	 0.145898
0.145898	et	 -0.090170
-0.090170	et	 0.055728
0.055728	et	 -0.034442
-0.034442	et	 0.021286
0.021286	et	 -0.013156
-0.013156	et	 0.008131
0.008131	et	 -0.005025
-0.005025	et	 0.003106
0.003106	et	 -0.001919
-0.001919	et	 0.001186
0.001186	et	 -0.000733
-0.000733	et	 0.000453
0.000453	et	 -0.000280
-0.000280	et	 0.000173
0.000173	et	 -0.000107
-0.000107	et	 0.000066
0.000066	et	 -0.000041

Mais au bout de 400 itérations (en C sur une machine 32 bits) on trouve -15471332147508811778649072123238637817871931576684395831357484302336 qui n'est pas vraiment une suite tendant vers 0 !