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