Arithmétique et Ordinateur






Jean-François COLONNA

www.lactamme.polytechnique.fr

jean-francois.colonna@polytechnique.edu
CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641, Ecole Polytechnique, CNRS, 91128 Palaiseau Cedex, France

[Site Map, Help and Search [Plan du Site, Aide et Recherche]]
[The Y2K bug [Le bug de l'an 2000]]
[Croyez-vous que les Nombres Réels existent dans un ordinateur et que les calculs flottants sont sûrs ?]
[N'oubliez pas de visiter Une Machine Virtuelle à Explorer l'Espace-Temps 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 30/11/2017 et mise à jour le 08/05/2019 13:27:51 -CEST-)




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 : 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


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 proprement astronomiques. 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.0001100110011001100110011001100110011001100110...
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 (par exemple un interrupteur est 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 '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 (c) Jean-François Colonna, 2017-2019.
    Copyright (c) CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641 / Ecole Polytechnique, 2017-2019.