Les pi�ges de la traduction et de la repr�sentation en machine

    Ecrire un algorithme simple et correct n'assure pas  que
    la traduction est simple.  Il faut souvent tenir  compte
    du  codage  de  l'information,  de la repr�sentation des
    nombres en machine, surtout pour les langages  fortement
    typ�s.  Les entiers et  les r�els sont stock�s avec  une
    certaine pr�cision, d'o� des erreurs d'arrondis  souvent
    g�nantes.  Nous pr�senterons  sur des exemples ce  qu'on
    peut d�duire comme r�gles simples de traduction.

Codage des nombres entiers

    Tout le monde  sait que math�matiquement,  l'addition de
    deux nombres positifs donne un autre nombre positif, que
    multiplier un nombre positif par un autre nombre positif
    donne  un  autre  nombre  positif.   Et pourtant... nous
    montrerons avec l'algorithme  suivant qu'il ne  faut pas
    confondre les r�gles de calcul math�matique avec  celles
    du calcul en machine.

*********** impossible math�matiquement
k <-- 1
p <-- 1
tant que p > 0
  car <-- k*k
  p   <-- car*car
  ecrire k , p
  k   <-- k+1
  **** pour un langage "propre", il faut rajouter :
  **** sortirquand k > 20
fintant que p > 0

    Cet algorithme  devrait th�oriquement  boucler, afficher
    les  nombres  not�s  k  et  leur  puissance quatri�me, �
    partir de 1 et sans jamais  s'arr�ter.  En fait, il y  a
    deux affichages possibles :  sortie probable :

       1         1
       2        16
       3        81
       4       256
       5       625
       6      1296
       7      2401
       8      4096
       9      6561
      10     10000
      11     14641
      12     20736
      13     28561
      14    -27120

    sortie correcte :
            1          1
            2         16
            3         81
            4        256
            5        625
            6       1296
            7       2401
            8       4096
            9       6561
           10      10000
           11      14641
           12      20736
           13      28561
           14      38416
           15      50625
           16      65536
           17      83521
           18     104976
           19     130321
           20     160000


    La  raison  d'une  telle  "erreur"  est  que les nombres
    entiers sont souvent  stock�s sur x  bits dont 1  bit de
    signe (0 pour plus et 1 pour moins).  Par exemple, sur 8
    bits dont 1  bit de signe,  le plus grand  nombre entier
    est  0  1111111  soit  32767  ;  si  on lui ajoute 1, on
    obtient 1 000000, ce qui, en binaire compl�ment� � deux,
    �quivaut a -32768.  Un calcul simple comme 3*15000/15000
    ne donne donc pas 3  mais plut�t -xxx.xxx ; de  m�me, le
    programme Pascal suivant, traduction simple et fid�le de
    l'algorithme "impossible"  donne un  affichage incorrect
    (le m�me que celui de la colonne "sortie probable").

program trouvez_l_erreur ;
  var k, car, p : integer ;
begin
   k := 1 ; p := 1 ;
   while  p > 0 do begin
    car := k*k ; p := car*car ;
    writeln( k :2 , p : 10 ) ;
    k   := k+1
   end (* while  p > 0 *)
end.

    Remarque  :    certains  Pascal,  comme  le Turbo Pascal
    proposent   d'autres   types   d'entiers   (byte,  word,
    longint).   Avec un  longint plutot  que integer,  on ne
    fait que repousser le probl�me et l'affichage finit  par
    :

    214      2097273616  --- 10 chiffres seulement ?
    215      2136750625
    216      2118184960

Le m�me algorithme traduit b�tement en langage C fait la m�me erreur :

/* entiers c ou pascal, m�me motif,  m�me punition*/
int  k, car, p;
void main()
{  k = 1 ; p = 1 ;
   while (p > 0 ) {
    car = k*k ; p = car*car ;
    printf("%2d%10d\n", k, p) ;
    k   = k+1;
   } /* while  p > 0 */
}

    Par contre, les  langages interpr�t�s s'offrent  souvent
    le luxe de travailler en plus grande pr�cision :   ainsi
    le programme Rexx qui suit fournit une sortie correcte ;
    on  remarquera   que  la   traduction  suit   exactement
    l'algorithme (on n'a pas utilise l'expression k**4  pour
    calculer  la  puissance  quatri�me  de  k, par exemple).
    Rexx pourrait m�me travailler en tr�s grande  pr�cision,
    gr�ce a  l'instruction numeric  digits 1000.   On aurait
    alors 1000  chiffres exacts  pour les  entiers, au  prix
    d'une grande lenteur de  ca lcul.  Cette  pr�cision peut
    sembler inutile, mais  elle ne l'est  pas :   la plupart
    des protections par cryptage utilisent des techniques de
    codage  qui  font  appel  �  de grands nombre premiers ;
    quand on sait  le co�t de  la s�curit� en  informatique,
    utiliser    1000    chiffres    exacts   mais   garantir
    l'inviolabilit� des donn�es est un choix raisonnable.

/* pas d'erreur, c'est du Rexx */
k = 1
p = 1
do while  p > 0
 car = k*k
 p   = car*car
 say format( k , 2) format( p , 10 )
 k = k+1
 if k > 20 then exit
end /*  while  p > 0 */

    De m�me,  en Apl,  on obtient  la bonne  sortie avec  le
    programme  ("fonction")  qui  suit  ;  la  encore,  on a
    traduit au plus fid�le, sans utiliser une expression  en
    one    liner.        Car    une   simple   ligne   comme
    k,[1.5](k{CARSPECIAUX   67   \f   "Lucida   Bright  Math
    Symbol"}�n)*4 aurait correctement affich� les n premiers
    entiers et leur puissance quatri�me (sans le cadrage).

[0] algos ; K ; CAR ; P
[1] comme en maths... mais sans k*4
[2] K {CARSPECIAUX 67 \f "Lucida Bright Math Symbol"} 1
[3] bou:
[4]   CAR {CARSPECIAUX 67 \f "Lucida Bright Math Symbol"} K    x K
[5]   P   {CARSPECIAUX 67 \f "Lucida Bright Math Symbol"} CAR  x CAR
[6]   (2 0 rk) , 10 0 r P
[7]   D (K>20) / 0
[8]   k {CARSPECIAUX 67 \f "Lucida Bright Math Symbol"} k+1
[9] D(P>0)/bou

    Dbase aussi  fournit un  affichage correct  ; le cadrage
    des nombres k et p est fait par d�faut sur 14 positions,
    ce qui suffit puisque nous for�ons l'arr�t a 204 :

store 1 to k
store 1 to p
do while  p > 0
 store k*k to car
 store car*car to p
 ? k , p
 store k+1 to k
 if k > 20
    return
 endif
enddo

La raison pour laquelle Dbase sait bien g�rer les grands entiers et les r�els (il n'ya pas de typage explicite en entierou r�el sous Dbase) tient � l'objectif de  Dbase : Dbase est un langage orient� gestion. Dans de nombreux calculs de gestion et de comptabilit�, on doit g�rer les sommes exactement du premier au dernier centime, m�me si les sommes manipul�es se comptent en milliards ; or un milliard, c'est d�j� 109.
De m�me, sous Awk,  on obtient avec le programme (qui est pratiquement le m�me que le programme en C) :

BEGIN {  ARGV[1]="" ; k = 1 ; p = 1
   while (p > 0 ) {
    car = k*k ; p = car*car
    printf("%2d%10d\n", k, p)
    k   = k+1
   } # while  p > 0
}

Toutefois, � partir de k=216 (sur PC, ou pour une autre valeur sous Unix) on obtient le message : warning at program line 7 (NR=0):Overflow in conversion of floating point number to integer.
Lisp g�re correctement les "grands entiers"  gr�ce aux instructions :
(setq k 1)
(setq p 1)
(while (> p 0)
  (setq car (* k k))
  (setq p   (* car car))
  (prin  k)
  (prin  " ")
  (print p)
  (setq k (+ 1 k))
  (if (> k 20) (setq p -1)))

mais l'affichage r�sultant pourra �tre capricieux (suivant la version de Lisp utilis�e). Un lecteur attentif remarquera comment, pour Lisp, on a contourne la sortie de boucle : puisque le test se fait sur la positivit� de p, on met -1 dans p pour forcer la sortie. Dans les langages pr�c�dents, il y avait une sortie "officielle" de boucle sous la forme d'une instruction (exit, return) ou d'un branchement (D0). Une fa�on plus "lispienne" de faire serait de cr�er la fonction carr�, la fonction puiss4  et la fo
nction kp4 par les d�finitions
(defun carre(x) (* x x))
(defun puis4(x) (* (carre x) (carre x)))
(defun kp4(k p)
 (prin k)
 (prin " ")
 (print p)
 (if (> p 0) (kp4 (1+ k) (puis4 (1+ k))))
); fin de la fonction kp4

puis de lancer un calcul r�cursif par (kp4 1 1). On obtient alors un affichage correct en LeLisp jusqu'� la valeur k=56, comme le montre l'extrait de sortie d'ex�cution
56 9834496.
57 1.0556001e+007
58 1.1316496e+007
Vouloir r�aliser un programme �quivalent en Prolog tient un peu de la gageure. On peut quand m�me tenter de r�aliser le but algos � partir des d�clarations suivantes :
clauses
 algos :- K=1, P=1, puiss4(K,P).
 puiss4(VarK,Varp) :-
   Varp>0,
   write(Vark),  write(" "),
   write(Varp),  nl,
   Vark1=Vark+1, Varcar=Vark1*Vark1,
   Varp4=Varcar*Varcar,
   puiss4(Vark1,Varp4).
Il faut toutefois pour Turbo Prolog mettre avant ces clause les instructions de typage
predicates
 algos
 puiss4(integer,integer)
On obtient alors un affichage correct, mais qui s'arr�te "raisonnablement" apr�s avoir affich� la valeur 13 et sa puissance quatri�me, comme quoi nombre de langages travaillent en interne selon les m�mes fonctionnements, et en particulier les m�mes stockages m�moire, m�me si les langages sont tr�s diff�rents. Un langage comme Mathematica sait bien s�r faire mieux, par avec une traduction fid�le de l'algorithme de d�part en
k=1; (* ne s'arr�te vraiment jamais *)
While[k^4>0,
    Print[k," ",k^4] ;
    k++ ;
] (* fin de While *)
Toutefois, nous nous sommes dispens�s d'utiliser la variable car puisque Mathematica sait calculer les puissances, y compris en calcul formel. Ainsi, Expand[ (a+b)^5 ] renvoie
  5      4         3  2       2  3        4    5
 a  + 5 a  b + 10 a  b  + 10 a  b  + 5 a b  + b

5.3.3.2. codage des nombres r�els
Si l'exemple des puissances parait anti-naturel car peu fr�quent* , le suivant sera peut-�tre plus probable : il s'agit d'aller de 0 � 1 de dixi�me en dixi�me. L'algorithme, simple et court, est correct math�matiquement :
 k C 1/10
 r�p�ter
   �crire k , 1-k
   k Ck+1/10
   ******* quand on conna�t le "truc", on rajoute
   ******* sortirquand k > 1.5
 jusqu'� k=1
Nous avons inclus dans cet algorithme l'affichage de la diff�rence entre 1 et k pour mieux appr�cier le probl�me. La traduction "classique" de l'algorithme r�serve des surprises. En Pascal, avec les instructions
program ma19b ;
 var k : real ;
begin k := 1/10 ;
 repeat
   writeln(k , '':6 , 1-k) ;
   k :=  k + 1/10 ;
   if k > 1.5 then exit
 until k=1
end.
Oon obtient, comme sortie du programme :
 1.0000000000e-01       9.0000000000e-01
 2.0000000000e-01       8.0000000000e-01
 3.0000000000e-01       7.0000000000e-01
 4.0000000000e-01       6.0000000000e-01
 5.0000000000e-01       5.0000000000e-01
 6.0000000000e-01       4.0000000000e-01
 7.0000000000e-01       3.0000000000e-01
 8.0000000000e-01       2.0000000000e-01
 9.0000000000e-01       9.9999999999e-02
 1.0000000000e+00      -1.8189894035e-12
 1.1000000000e+00      -1.0000000000e-01
 1.2000000000e+00      -2.0000000000e-01
 1.3000000000e+00      -3.0000000000e-01
 1.4000000000e+00      -4.0000000000e-01
Mettre comme type extended plut�t que real ne fait que repousser le probl�me et donne comme affichage :
 ...
 8.00000000000000e-0001       2.00000000000000e-0001
 9.00000000000000e-0001       1.00000000000000e-0001
 1.00000000000000e+0000      -1.08420217248550e-0019
 1.10000000000000e+0000      -1.00000000000000e-0001
 ...
Le m�me ph�nom�ne se produit en C, avec le programme :
#include <stdio.h>
  float k;
void main()
{  k = 0.1 ;
   do { printf("%f  %f\n", k, 1-k) ;
        k =  k + 0.1 ;
   } while ( (!(k==1)) && (k<1.5)) ;
}
mais son affichage est plus surprenant :
 0.100000   0.900000
 0.200000   0.800000
 0.300000   0.700000
 0.400000   0.600000
 0.500000   0.500000
 0.600000   0.400000
 0.700000   0.300000
 0.800000   0.200000
 0.900000   0.100000
 1.000000  -0.000000
 1.100000  -0.100000
 1.200000  -0.200000
 1.300000  -0.300000
 1.400000  -0.400000
La raison en est classique : chaque nombre est stock� en machine sous forme binaire, c'est � dire avec des puissances de deux 1/10 devrait donc s'�crire comme une combinaison lin�aire sous la forme
  {INCORPORER Equation |}
o� chaque coefficient vaut 0 ou 1 ; mais cette �criture ne peut se faire qu'avec un nombre fini de termes, par exemple par la somme
 {INCORPORER Equation |}
N'utiliser que p termes introduit donc une erreur d'approximation faible mais constante qui se propage et se r�p�te ; on la voit au bout de 10 fois si on effectue un test strict d'�galit�.
Pour les lecteurs int�ress�s, il est simple de calculer le d�veloppement en base 2 de 0.1 ; comme pour un nombre d�cimal classique mais inf�rieur � 1, il suffit de multiplier par 2 le nombre, de noter puis d'enlever la partie enti�re et de recommencer. Dans le cas pr�sent, on obtient donc
 0.1 multipli� par 2 vaut 0.2 ; on retient donc 0
 0.2 multipli� par 2 vaut 0.4 ; on retient donc 0
 0.4 multipli� par 2 vaut 0.8 ; on retient donc 0
 0.8 multipli� par 2 vaut 1.6 ; on retient donc 1 et on garde 0.6
 0.6 multipli� par 2 vaut 1.2 ; on retient donc 1 et on garde 0.2
 0.2 multipli� par 2 vaut 0.4 ; on retient donc 0
 0.4 multipli� par 2 vaut 0.8 ; on retient donc 0
 0.8 multipli� par 2 vaut 1.6 ; on retient donc 1 et on garde 0.6
 etc.
Le d�but du d�veloppement de 0.1 est donc 0.000110011... L'algorithme de codage en binaire et de d�codage est simple � �crire. On �crira le d�veloppement binaire sous forme d'une chaine de caract�res car il est simple de concat�ner un caract�re au d�veloppement courant ; on aurait aussi pu utiliser un tableau de coefficients, mais il aurait fallu se poser la question du dimensionnement. Pour le d�codage, c'est � dire l'�valuation du d�veloppement binaire, une boucle pour calcule cette valeur en divisant le
i-�me terme (qui est � la position i+2 dans la chaine car le d�veloppement contient "0" et "." comme premiers caract�res) par la bonne puissance de deux.
module BinaireD�cimal
 param�tres nombre { dont on veut le d�veloppement }
            precis { nombre de bits utilis�s }
 locales    valbin { d�veloppement binaire de nombre }
            multip { multiples successifs }
            retenu { partie enti�re de multip }
            decode { valeur d�cimale de valbin }
            pdd    { puissance de deux }


d�but du module BinaireD�cimal
  valbin {CARSPECIAUX 67 \f "Lucida Bright Math Symbol"} "0."
  pour i de1� precis
     multip {CARSPECIAUX 67 \f "Lucida Bright Math Symbol"} 2*nombre
     retenu {CARSPECIAUX 67 \f "Lucida Bright Math Symbol"} PartieEnti�re( multip )
     valbin {CARSPECIAUX 67 \f "Lucida Bright Math Symbol"} valbin + Format(retenu)
     nombre {CARSPECIAUX 67 \f "Lucida Bright Math Symbol"} multip - retenu
  finpour
  �crire " valeur binaire de ",nombre," = ",valbin
decode {CARSPECIAUX 67 \f "Lucida Bright Math Symbol"} 0
pdd    {CARSPECIAUX 67 \f "Lucida Bright Math Symbol"} 1
pour i de1� to precis
   pdd    {CARSPECIAUX 67 \f "Lucida Bright Math Symbol"} pdd * 2
   decode {CARSPECIAUX 67 \f "Lucida Bright Math Symbol"} decode + ( SousChaine(valbin,2+i,1) / pdd )
end
�crire " valeur d�cod�e de ",valbin," = ",decode
La traduction en Rexx b�n�ficie des simplifications dues aux nombreuses fonctions de Rexx comme trunc, | | (pour la concat�nation), substr :
/* Ebdnd.Rex : Ecriture Binaire D'un Nombre D�cimal */
nombre = 0.1 ; precis = 16 /* par exemple */
valbin = "0."
do i=1 to precis
   multip = 2*nombre
   retenu = trunc( multip )
   valbin = valbin || retenu
   nombre = multip - retenu
end
say " valeur binaire de " nombre " = " valbin
/* renvoie 0.000110011001 */
decode = 0 ; pdd    = 1
do i=1 to precis
   pdd    = pdd * 2
   decode = decode + ( substr(valbin,2+i,1) / pdd )
end
say " valeur d�cod�e de " valbin " = " decode
/* renvoie 0.0999908447
   si precis = 20 on obtient 0.0999994278 */
Si de tels "pi�ges" sont classiques, il n'en sont pas pour autant simples � expliquer ni toujours faciles � pr�voir. Avec de l'exp�rience, un programmeur C ou Pascal saura que "ses" entiers doivent rester petits ou qu'il faudra les traiter comme des r�els ; � force, les tests d'�galit�s entre nombres r�els comme x=y seront remplac�s par des tests d'approximation suffisante comme abs(x-y)<eps o� eps est une valeur consid�r�e comme petite ({CARSPECIAUX 68 \f "Lucida Bright Math Italic"}-machine, pr�cision gar
antie par le compilateur, etc.). Seuls des langages comme Rexx ou Mathematica peuvent garantir suffisamment de d�cimales, mais au prix d'une grande lenteur. Ainsi, calculer yx o� y vaut xx et x est 1993* prend plusieurs heures.
* Par exemple en Pascal, on peut r�server { et } pour les commentaires associ�s aux etapes, (* et *) pour les autres commentaires.
* le m�me probl�me arrive avec les puissances plus faibles, comme le carr�, ou m�me une simple addition ; par exemple 32767+1 renvoie pour de nombreux langages compil�s -32768.
*  nous n'avons pas os� �crire {INCORPORER Equation |} � cause l'ambiguit� entre {INCORPORER Equation |} et {INCORPORER Equation |}.