Arithmétique et Ordinateur
CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641, École polytechnique, Institut Polytechnique de Paris, CNRS, France
[Site Map, Help and Search [Plan du Site, Aide et Recherche]]
[The Y2K Bug [Le bug de l'an 2000]]
[Real Numbers don't exist in Computers and Floating Point Computations aren't safe. [Les Nombres Réels n'existent dans les Ordinateurs et les Calculs Flottants ne sont pas sûrs.]]
[N'oubliez pas de visiter Une Machine Virtuelle à Explorer l'Espace-Temps et au-delà où vous trouverez plusieurs milliers d'images et d'animations à la frontière de l'Art et de la Science]
(Site WWW CMAP28 : cette page a été créée le 11/30/2017 et mise à jour le 12/12/2023 18:40:05 -CET-)
L'arithmétique est enseignée dès l'école primaire et
savoir compter, additionner deux nombres, les multiplier,...
font partie des fondamentaux que doivent assimiler nos enfants.
Or on oublie (ou ignore) trop souvent qu'il s'agit là aussi des compétences de base de
nos ordinateurs auxquelles il convient d'ajouter la capacité de déplacer dans sa
mémoire des informations et de comparer deux nombres (par exemple afin de savoir
si A est strictement supérieur à B puis d'entreprendre des actions en conséquences).
Nos machines nous permettent de faire, en apparence, des choses beaucoup plus complexes :
"surfer" sur Internet, regarder des films, intégrer des équations différentielles,...
Mais tout cela se ramène in fine à l'arithmétique.
Et ainsi, savoir passer d'une description des tâches à accomplir aux opérations de base
est le rôle des programmeurs.
Programmer un ordinateur est en général une activité très délicate qui est
source d'erreurs et d'anomalies : les fameux "bugs" et "plantages" que tout utilisateur a
rencontré plus d'une fois dans sa vie. Il est possible fort heureusement de réduire
le nombre de ces défauts ; il existe pour cela des méthodes plus ou moins coûteuses
utilisées en particulier dans les logiciels que l'on trouve dans les avions.
Mais n'existerait-il pas dans nos machines des défauts irréductibles, dont on ne pourrait
se débarasser ? Au niveau le plus fondamental, nos ordinateurs sont-ils des maîtres ès arithmétique
et respectent-ils systématiquement toutes les régles,... ?
Rappelons au préalable les progrès presque incroyables accomplis, en particulier au niveau matériel,
en quelques décennies. Au début des années 1970, disposer d'une
mémoire "centrale" de 128 Kilo-octets était un luxe que peu d'entreprises ou de centres de recherche pouvaient s'offrir !
Aujourd'hui, pour n'importe quel ordinateur même "grand public", la capacité se mesure en Giga-octets !
Et ainsi, l'utilisateur a quasiment le sentiment de disposer d'une mémoire infinie...
Mais malgré tout elle reste finie et cela est trop souvent négligé. Or très nombreuses sont finalement
les circonstances où l'infini est nécessaire. Par exemple, les nombres réels possèdent,
sauf de très très rares exceptions, une infinité de décimales. Pour calculer l'aire d'un cercle dans la vie courante,
utiliser pi=3.14159265358979312 est largement suffisant. Mais, à cause de la finitude des mémoires, le "vrai" nombre pi
et d'une façon générale l'ensemble des nombres réels ne peuvent pas être manipulés exactement dans nos
ordinateurs. Il est essentiel de noter que cela est évidemment vrai pour toutes les bases de numération : aussi bien la base 10 [01]
que nous utilisons quotidiennement "à la main" que la base 2 [02] qui est au cœur de toutes nos machines numériques.
Les opérations arithmétiques élémentaires d'addition et de multiplication possèdent un certain nombre
de propriétés et en particulier celle d'associativité. Elle signifie que quels que soient les nombres P, Q et R, on a respectivement :
P+(Q+R) = (P+Q)+R
et :
Px(QxR) = (PxQ)xR
L'associativité est-elle vérifiée dans un ordinateur ? Oui en général et par exemple :
2+(5+8) = (2+5)+8 = 15
et :
2x(5x8) = (2x5)x8 = 80
Mais pas toujours. Ainsi, par exemple (les valeurs situées au bout de chaque ligne donne le résultat en base 16 ce qui
permet de voir tous les bits calculés sans exception) :
1.10 + (3.30 + 5.50) = 9.900001 = 0x411E6667
# #
(1.10 + 3.30) + 5.50 = 9.900000 = 0x411E6666
# #
et :
3.10 * (2.30 * 1.50) = 10.694999 = 0x412B1EB7
#### #
(3.10 * 2.30) * 1.50 = 10.695000 = 0x412B1EB8
#### #
Une remarque s'impose ici : il est très difficile de savoir dans quel ordre un ordinateur
effectuera les deux opérations (addition ou multiplication) dans la mesure où les parenthèses
sont redondantes. Par exemple, dans le cas de la multiplication, les trois écritures Px(QxR), (PxQ)xR et PxQxR sont a priori
équivalentes mathématiquement parlant. Est-ce alors la première multiplication qui sera effectuée en premier ou bien la seconde (on notera au passage que l'on
ignore ici la propriété de commutativité satisfaite dans nos ordinateurs aussi bien par l'addition que par la multiplication et qui signifie que P+Q=Q+P et PxQ=QxP) ?
Or pour vérifier cette anomalie, il faut de toute évidence être sûr de l'ordre dans lequel seront exécutées les opérations. Un moyen sûr
consiste à passer par des fonctions pour effectuer les opérations arithmétiques ainsi que le montre l'exemple suivant programmé en C pour l'addition :
float ADD(x,y)
float x,y;
{
return(x+y);
}
main()
{
float A=1.1,B=3.3,C=5.5;
float X,Y;
X=ADD(ADD(A,B),C);
Y=ADD(A,ADD(B,C));
printf("\n (%f x %f) x %f = %f\n",A,B,C,X);
printf("\n %f x (%f x %f) = %f\n",A,B,C,Y);
}
Il a été dit précédemment que rédiger un programme n'était pas toujours facile et il est
possible d'ajouter qu'au-delà d'une certaine complexité un certain nombre d'anomalies subsistent malgré
les tests de validation effectués. On pourrait donc croire que pour avoir un programme parfait, il
suffirait qu'il soit très simple. Montrons par l'exemple qu'il n'en est rien [03] :
main()
{
double A,B,x0,x1,x2,x3,x4,x5,x6,x7;
B=4095.1;
A=B+1;
x0 = 1;
x1 = (A*x0) - B;
x2 = (A*x1) - B;
x3 = (A*x2) - B;
x4 = (A*x3) - B;
x5 = (A*x4) - B;
x6 = (A*x5) - B;
x7 = (A*x6) - B;
printf("x0 = %+.16f\n",x0);
printf("x1 = %+.16f\n",x1);
printf("x2 = %+.16f\n",x2);
printf("x3 = %+.16f\n",x3);
printf("x4 = %+.16f\n",x4);
printf("x5 = %+.16f\n",x5);
printf("x6 = %+.16f\n",x6);
printf("x7 = %+.16f\n",x7);
}
Faisons quelques remarques concernant ce "vrai" programme :
- Il est rédigé en langage C [04] et peut donc s'exécuter sur la plupart des ordinateurs, mais à condition
d'en respecter scrupuleusement le contenu.
- Ce phénomène est évidemment indépendant du langage de programmation comme on peut le voir
avec les versions de ce programme
en Fortran 95 ou encore
en Python.
- Il aurait pu être conçu de manière beaucoup plus compacte et plus "professionnelle" (en faisant
appel, par exemple, à une itération),
mais cela se serait fait au détriment de sa compréhension par les non informaticiens.
- Il est extrèmement simple et même un novice peut en comprendre le fonctionnement et la finalité.
- Cette simplicité a pour conséquence qu'il est difficilement imaginable qu'il
puisse y avoir une erreur de logique à l'intérieur.
- On peut vérifier facilement que le compilateur a correctement effectué l'indispensable traduction en assembleur (ce qui correspond aux
instructions élémentaires qui seront effectivement exécutées par le processeur).
- En le suivant pas à pas et en interprétant ses instructions, on peut voir très
facilement que x1=(A*x0)-B=(A*1)-B=A-B=1 (puisque A=B+1) et que de même x2=x3=...=x7=1.
- On connait donc à l'avance exactement les résultats attendus ce qui est assez rare,
puisqu'en général les programmes sont écrits pour calculer des valeurs que l'on ignore...
Or, malgré les remarques précédentes, il ne donne pas les résultats attendus, loin s'en faut :
x0 = +1.0000000000000000
x1 = +1.0000000000004547
x2 = +1.0000000018630999
x3 = +1.0000076314440776
x4 = +1.0312591580864137
x5 = +129.0406374377594148
x6 = +524468.2550088063580915
x7 = +2148270324.2415719032287598
De façon paradoxale, on notera que remplacer double par float
(c'est-à-dire diminuer la précision en passant de 64 à 32 bits), donne la réponse attendue (1).
Il n'y a là rien de mystérieux : en 32 bits (la simple précision), A-B est égal exactement à 1 et ce un peu "par hasard"...
Cela peut se voir grace au petit progranne suivant :
void main()
{
float fA,fB;
double dA,dB;
fB=4095.1;
fA=fB+1;
dB=4095.1;
dA=dB+1;
if ((fA-fB) == 1)
{
printf("(fA-fB) = 1\n");
}
else
{
printf("(fA-fB) # 1\n");
}
if ((dA-fB) == 1)
{
printf("(dA-fB) = 1\n");
}
else
{
printf("(dA-dB) # 1\n");
}
}
qui donne les résultats suivants :
(fA-fB) = 1
(dA-dB) # 1
Et ainsi, dans ces deux exemples, augmenter le précision des calculs n'améliore pas la qualité des résultats, bien au contraire !
Mais quelle est donc la cause d'une telle anomalie ? En fait tout cela est d'une simplicité tout à la fois déconcertante
et paradoxale, puisqu'en effet, il n'y a pas, en toute généralité, de correctif !
Les ordinateurs ont aujourd'hui -2019- des capacités de stockage et des performances de calcul qui dépassent l'entendement.
Il est ainsi possible, par exemple, de stocker sur une petite carte de quelques millimètres carrés
plus de mille milliards d'octets ! Mais malgré cela l'infini reste inacessible (pour toujours ?) à nos machines.
Or le besoin d'infini apparait dans la plupart des problèmes et en particulier dans l'exemple dramatique précédent,
mais où ? Comme cela a été rappelé ci-dessus, nous utilisons pour nos calculs la base 10 et ce pour des raisons historiques et
morphologiques. Cette base 10 est inenvisageable dans nos ordinateurs car, en effet, elle demanderait des dispositifs
physiques à dix états d'équilibre. En revanche des systèmes en possédant deux sont très nombreux : c'est par
exemple le cas d'un interrupteur électrique ouvert ou fermé. Ainsi, lors de l'entrée de valeurs numériques
dans un ordinateur il est nécessaire de procéder à un changement de base (de 10 vers 2) et inversement (de 2 vers 10)
lors de la sortie des résultats. Dans l'exemple précédent la seule valeur numérique apparaissant explicitement
est la constante 4095.1. Sa partie entière ne pose aucun problème :
4095 --> 111111111111
Par contre sa partie décimale est la source de tous nos ennuis. En effet, 0.1 signifie 1/10 c'est-à-dire l'inverse
d'une seule puissance de 10, mais en base 2, il en va tout autrement :
0.1 --> 0.0 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 ad infinitum...
En toute rigueur il conviendrait donc d'utiliser une infinité d'inverses de puissances de 2 pour représenter exactement 1/10.
Or cela est évidemment impossible et ce à cause de la capacité finie (bien qu'énorme) de nos machines.
Ainsi, la valeur de 0.1 (et donc de 4095.1) dans ce programme n'est pas exacte, mais approchée et cette différence,
bien que petite, se voit dès la valeur de x1, puis l'erreur s'amplifie ensuite à cause des multiplications par A.
On pourrait alors imaginer naïvement qu'utiliser la base 10 plutôt que la base 2 dans nos ordinateurs serait LA solution.
Il n'en est rien car, en effet, le problème ne vient pas de la base mais bien évidemment de la finitude
de nos machines. Or il est des êtres mathématiques essentiels (dans les applications scientifiques en particulier) : ce sont les
nombres réels.
Déjà leur partie entière peut être énorme (c'est évidemment le cas des nombres entiers),
mais surtout leur partie décimale contient en général une infinité de décimales. Les nombres réels ne peuvent donc pas être
utilisés tels quels dans nos ordinateurs. On utilise à leur place, les nombres dits flottants
dont le principe, pour simplifier, consiste à ramener la valeur absolue de tout nombre dans [1,10[ grace à une multiplication
par une puissance de 10 appropriée (négative, nulle ou positive).
Un nombre flottant sera donc défini par un petit nombre décimal (appelé mantisse) et un exposant
(par exemple, pour -5039.28, la mantisse et l'exposant vaudront -5.03928 et +3 respectivement).
Mais malheureusement, les nombres flottants ne sont pas les nombres réels. Cela peut se voir facilement en vérifiant
qu'ils ne respectent pas les propriétés fondamentales de l'addition et de la multiplication comme cela fut indiqué ci-dessus
avec l'associativité. Oublier cela peut conduire à de très graves anomalies.
[01]
- La base 10 est la base de numération que nous utilisons dans la vie quotidienne. Nombreux sont ceux qui croient que
son usage est aujourd'hui quasiment universel parce que c'est plus facile avec elle qu'avec tout autre base. Cela est vrai, mais
ne vient pas de quelque propriété "magique" du nombre 10, mais tout simplement de son apprentissage dès la plus petite enfance.
Elle trouve très certainement son origine dans le nombre de doigts de nos deux mains.
Rappelons que, par exemple, l'écriture '5039.28' signifie :
+3 +2 +1 0 -1 -2
5039.28 = 5x10 + 0x10 + 3x10 + 9x10 + 2x10 + 8x10
= = = = = =
[02]
- Toute autre base que 10 peut-être utilisée. En particulier la base 2 est omniprésente dans nos ordinateurs tout simplement
parce qu'il est plus facile de mettre en œuvre des systèmes physiques à deux états d'équilibre (ainsi, par exemple, un interrupteur
qui sera ouvert -0- ou fermé -1-) : cela permet donc de simplifier considérablement la réalisation matérielle des processeurs.
Rappelons que, par exemple, l'écriture binaire '11001' signifie :
4 3 2 1 0
11001 = 1x2 + 1x2 + 0x2 + 0x2 1x2 = 16 + 8 + 1 = 25 (en base 10)
= = = = =
[03]
- Avant d'imaginer ce programme (en 2005 ?), je ne croyais pas possible de trouver un jour
quelque chose d'aussi simple qui mettrait si facilement et si dramatiquement ces anomalies en évidence.
En effet, avant cette découverte, j'utilisais en particulier des programmes beaucoup plus compliqués qui
utilisaient des méthodes numériques (en particulier pour résoudre approximativement des équations autrement insolubles)
qui elles-mêmes introduisaient leurs propres défauts qui venaient donc se superposer à ce que je voulais mettre en évidence.
Avec ce programme il ne subsiste que la pure essence du problème !
[04]
- Les ordinateurs possèdent tous un ensemble de plusieurs centaines d'instructions élémentaires : addition, soustraction,
multiplication, division, déplacement d'informations, accès aux organes périphériques,... Il est possible à un
utilisateur de spécifier ses ordres en les utilisant directement, mais malheureusement il s'agit là d'une tâche difficile et cela
réduirait donc considérablement la productivité
des programmeurs et la fiabilité de leurs programmes. Un autre inconvénient majeur est de limiter la portabilité c'est-à-dire la possibilité de porter un
programme d'un ordinateur à un autre sans efforts et sans anomalies. C'est pourquoi ont été développé des langages dits de "haut niveau" qui sont
indépendants des ordinateurs tout en étant plus proches des problèmes des utilisateurs. Historiquement le Fortran (1954) et le Cobol (1959) furent les
premiers langages populaires. Aujourd'hui C (1972) et C++ (1983) sont très répandus.
Copyright © Jean-François COLONNA, 2017-2023.
Copyright © CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641 / École polytechnique, Institut Polytechnique de Paris, 2017-2023.
