Si on teste le script suivant :
p = 0 while p<1: p += 0.1 print(p)
sur une machine à 32 bits
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
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.
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).
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.
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.
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.
La périodicité peut se montrer par induction structurelle sur ce graphe représentant le double modulo 10 :
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.
En refaisant un graphe similaire mais modulo 100 on constate que 1/100 n'est pas dyadique non plus :
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 !