Calcul formel : Mode d'emploi - Exemples en Maple

Claude Gomez, Bruno Salvy, Paul Zimmermann

Masson, 1995

Chapitre IV, section 1.5, exercice 9, page 109.

Philippe.Dumas@inria.fr
http://algo.inria.fr/dumas/Maple/

Page du Projet Algorithmes | Page de Philippe Dumas | Page Maple de Philippe Dumas

Retour en page principale
Table des matières
Index
Maple V.4 worksheet, bis
Maple V.5 worksheet, bis, ter


Extension de l'exercice précédent | Gestion dynamique
Emploi de tables

Extension de l'exercice précédent. Reprenons d'abord la procédure de l'exercice précédent à titre de comparaison.

> L2:=[1,2,3,7,12,21,29,38,43,47,48,49,
51,52,53,57,62,71,79,88,93,97,98,99];

[Maple Math]
[Maple Math]

> is149_2:=proc(n)
local r,s;
r:=n;
while r<>0 do
s:=irem(r,100,'r');
if not (member(s,{11,14,19,41,44,49,91,94,99})
or
(member(s,{1,4,9}) and r=0)) then
RETURN(false)
fi
od;
true
end:

> tricol_2:=proc(N)
local k,res,q,r,n,i;
global L2;
k:=0;
for q from 0 by 100 while k<N do
for r in L2 do
if is149_2((q+r)^2) then
k:=k+1;
res[k]:=q+r; fi
od
od;
[seq(res[i],i=1..N)]
end:

> start:=time():
tricol_2(12);
time()-start;

[Maple Math]

[Maple Math]

Si l'on augmente la valeur de l'argument en passant à N=14, le calcul devient désespérement long. Pour améliorer la méthode, nous allons faire varier la largeur slicesize de la tranche qui permet d'effectuer le test de dégrossissage. Au lieu de prendre la valeur 2, cette largeur va être prise en paramètre. Nous commençons avec la valeur 4.

> slicesize:=4;

[Maple Math]

Nous devons construire les mots de longueur inferieure ou égale a slicesize sur l'alphabet {1,4,9}. Pour cela nous faisons appel au package combstruct. Pour s'initier à ce package on peut lire la page d'indroduction à combstruct. Nous employons ici la version qui figure dans Maple V.5. Nous définissons une grammaire pour le monoïde libre sur l'alphabet {a,b,c}. Cette grammaire se comprend comme suit : un mot est ou bien le mot vide, ou bien une lettre a, b ou c suivi d'un mot. De plus une lettre a pour taille une unité.

> with(combstruct):

> word:={W=Union(Epsilon,Prod(A,W)),
A=Union(a,b,c),
a=Atom, b=Atom, c=Atom}:

Ensuite combstruct/allstructs nous fournit toutes les éléments d'une taille donnée. Nous substituons à a, b et c les nombres 1, 4 et 9. L'ensemble QQ contient les mots de longueur strictement plus petite que slicesize ; l'ensemble Q contient les mots de longueur exactement slicesize.

> for s to slicesize do
W.s:=allstructs([W,word],size=s);
WW.s:={seq([eval(subs(Prod=proc() args end,
Epsilon=NULL,a=1,b=4,c=9,i))],i=W.s)};
LL.s:=map(proc(l) local i;add(l[i]*10^(i-1),i=1..nops(l)) end,
WW.s)
od:
QQ.slicesize:={seq(op(LL.s),s=1..slicesize-1)};
Q.slicesize:=LL.slicesize;

[Maple Math]
[Maple Math]
[Maple Math]

[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]

En Maple V.4, le package combstruct est moins puissant et ce qui précède ne fonctionne pas. Il suffit alors de reprendre à zéro, ce qui n'est pas trop difficile car la structure à engendrer est simple. On peut procéder comme suit.

> WW0:={[]}:

> for s to slicesize do    
WW.s:=map(proc(L)
local s,i;
s:=op(L);
[s,1],[s,4],[s,9]
end,WW.(s-1));
LL.s:=map(proc(l)
local i;
add(l[i]*10^(i-1),i=1..nops(l))
end,WW.s)
od:
QQ.slicesize:={seq(op(LL.s),s=1..slicesize-1)};
Q.slicesize:=LL.slicesize;

[Maple Math]
[Maple Math]
[Maple Math]

[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]

Ensuite on cherche les résidus modulo 10^slicesize des motifs précédents; on les ordonne et on les range dans la liste L.

> L.slicesize:=sort(map2(op,2,map(op,
[seq(msolve(r^2=d,10^slicesize),
d=QQ.slicesize union Q.slicesize)])));

[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]

On écrit une procedure de sélection dépendant du paramètre slicesize de la même manière que dans l'exercice précédent.

> is149_.slicesize:=eval(subs(_Q=Q.slicesize,
_QQ=QQ.slicesize,
_slicesize=slicesize,
proc(n::posint)
local r,s;
r:=n;
while r<>0 do
s:=irem(r,10^_slicesize,'r');
if not (member(s,_Q)
or
(member(s,_QQ) and r=0)
) then
RETURN(false)
fi
od;
true
end));

[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]

Ensuite on écrit la procédure de génération des mots tricolores où l'itération emploie les motifs de taille slicesize pour les poids faibles.

> tricol_.slicesize:=subs(_L=L.slicesize,
_slicesize=slicesize,
_is149=is149_.slicesize,
proc(N::posint)
local k,res,q,r,n,i;
k:=0;
for q from 0 by 10^_slicesize while k<N do
userinfo(3,procname,"testing q=",q);
for r in _L do
if _is149((q+r)^2) then
k:=k+1;
res[k]:=q+r;
userinfo(2,procname,res[k])
fi
od
od;
[seq(res[i],i=1..N)]
end);

[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]

On teste la procédure sur de faibles valeurs.

> infolevel[tricol_.slicesize]:=3:

> start:=time():
tricol_.slicesize(10);
time()-start;

tricol_4:   "testing q="   0

tricol_4:   1

tricol_4:   2

tricol_4:   3

tricol_4:   7

tricol_4:   12

tricol_4:   21

tricol_4:   38

tricol_4:   107

tricol_4:   212

tricol_4:   "testing q="   10000

tricol_4:   "testing q="   20000

tricol_4:   "testing q="   30000

tricol_4:   31488

[Maple Math]

[Maple Math]

> infolevel[tricol_.slicesize]:=1:

Encouragés par ce succès, nous poursuivons en employant la valeur 6 pour la taille de la tranche.

> slicesize:=6;

[Maple Math]

> for s to slicesize do
W.s:=allstructs([W,word],size=s);
WW.s:={seq([eval(subs(Prod=proc() args end,
Epsilon=NULL,a=1,b=4,c=9,i))],i=W.s)};
LL.s:=map(proc(l) local i;add(l[i]*10^(i-1),i=1..nops(l)) end,
WW.s)
od:
QQ.slicesize:={seq(op(LL.s),s=1..slicesize-1)}:
Q.slicesize:=LL.slicesize:

> L.slicesize:=sort(map2(op,2,map(op,
[seq(msolve(r^2=d,10^slicesize),
d=QQ.slicesize union Q.slicesize)]))):

> is149_.slicesize:=eval(subs(_Q=Q.slicesize,
_QQ=QQ.slicesize,
_slicesize=slicesize,
proc(n::posint)
local r,s;
r:=n;
while r<>0 do
s:=irem(r,10^_slicesize,'r');
if not (member(s,_Q)
or
(member(s,_QQ) and r=0)
) then
RETURN(false)
fi
od;
true
end)):

> tricol_.slicesize:=subs(_L=L.slicesize,
_slicesize=slicesize,
_is149=is149_.slicesize,
proc(N::posint)
local k,res,q,r,n,i;
k:=0;
for q from 0 by 10^_slicesize while k<N do
userinfo(3,procname,"testing q=",q);
for r in _L do
if _is149((q+r)^2) then
k:=k+1;
res[k]:=q+r;
userinfo(2,procname,res[k])
fi
od
od;
[seq(res[i],i=1..N)]
end):

Procédons à quelques essais.

> start:=time():
tricol_.slicesize(10);
time()-start;

[Maple Math]

[Maple Math]

> start:=time():
tricol_.slicesize(12);
time()-start;

[Maple Math]

[Maple Math]

Revenons un peu en arrière pour comparer les résultats.

> start:=time():
tricol_4(12);
time()-start;

[Maple Math]

[Maple Math]

Finalement, pour les tailles 2, 4, 6 les temps de calcul sont respectivement 90, 7 et 3 secondes pour N=12. Le gain est clair, mais le pretraitement est de plus en plus long. Pour la taille 6, on n'atteint pas N=14. Si on passe à la taille 8, le prétraitement devient excessivement long. Bref, il faut trouver autre chose.

Gestion dynamique. Le calcul modulaire a permis une amélioration de l'efficacité parce qu'il permet de filtrer de grands nombres en calculant sur de petits nombres. Cependant si le module devient grand, il ne présente plus d'intérêt pour des nombres qui ne sont pas très grands. C'est pourquoi la démarche précédente amène dans une impasse. Il faut que le module soit plus petit que les nombres que l'on traite tout en étant assez grand pour que le filtrage élimine beaucoup de cas. Pour trouver l'équilibre entre ces deux contraintes, une version dynamique du programme s'impose. Il faut faire évoluer le module au cours du calcul, au lieu de le fixer comme nous l'avons fait jusqu'ici.

Les premiers nombres tricolores sont maintenant connus. Pour trouver ceux qui sont entre 10^2 et 10^4, nous allons employer les résidus modulo 10^2. Pour trouver ceux qui sont entre 10^4 et 10^6, nous allons employer les résidus modulo 10^4. Et ainsi de suite. Encore faut il disposer des résidus acceptables pour effectuer le filtrage. Nous les calculerons en passant. Le programme va donc consister essentiellement en une boucle et chaque tour de boucle préparera le suivant.

Décrivons les différentes phases de cette nouvelle procédure tricol. Les premiers nombres tricolores sont connus. On range ceux qui sont plus petits que 100 dans la table res (#1). Le compteur k donne le nombre de nombres tricolores obtenus ; il démarre à la valeur 7 (#2). On range dans A et AA les chiffres et les bigrammes sur l'alphabet {1,4,9} (#3). Les variables oldQ et newQ vont contenir les ensembles de mots sur l'alphabet {1,4,9} dont la longueur est respectivement strictement plus petite que et exactement égale à la taille de tranche courante dans la boucle qui va suivre (#4). Les résidus modulo 10^2 des nombres tricolores sont connus et mis dans la liste newL (#5). Ensuite on rentre dans la boucle principale, indexée par la variable slicesize qui donne la longueur de la tranche côté poids faible prise en considération pour le criblage (#6). Cette longueur augmente de 2 en 2, ce qui est un choix arbitraire. On sort de la boucle quand on a trouvé les N premiers nombres tricolores. La variable newL fournit la liste des résidus possibles pour la longueur courante (#7). On définit la procédure is149 qui reconnaît les nombres dont le carré a une écriture décimale n'employant que les chiffres permis et cette procédure fonctionne en découpant le nombres en tranches de longueur slicesize (#8). Cette procédure a été pourvu de l'option remember ; en effet dans la boucle nous allons calculer les résidus possibles pour la longueur slicesize+2 et les mêmes nombres vont donc être testés plusieurs fois. On démarre ensuite une boucle indexée par la variable qq qui va de 1 à 99 (#8). Dans cette boucle on va tester chacun des nombres n=qq*10^slicesize+rr prend successivement pour valeurs les résidus possibles (#10). Le test est à deux niveaux. On regarde d'abord si le carré réduit modulo 10^(slicesize+2) ne comporte que les chiffres permis (#11). Si c'est le cas on a un résidu possible pour l'étape suivante et on le met de côté dans une table newT. De plus le nombre n est alors candidat pour être un nombre tricolore. On le teste donc (#12) et s'il est le N-ième on sort de cette boucle par un break, pour provoquer la sortie de la procédure (#13). Ayant terminé la boucle indexée par qq, on range dans la liste newL les résidus utiles pour la prochaine étape (#14). On met à jour les variables oldQ et newQ. On démarre le tour de boucle suivant.

Les instructions (#00) utilisant la procédure userinfo vont nous permette d'être informés du déroulement du calcul.

> tricol:=proc(N::posint)
local res,k,A,AA,oldQ,newQ,newL,
slicesize,oldL,is149,qq,q,l,r,n,n2,
tail,newT,i,j,st;
st:=time();
res[1]:=1; #1
res[2]:=2;
res[3]:=3;
res[4]:=7;
res[5]:=12;
res[6]:=21;
res[7]:=38;
k:=7; #2
A:={1,4,9}; #3
AA:={11,14,19,41,44,49,91,94,99};
oldQ:=A; #4
newQ:=AA;
newL:=[1,2,3,7,12,21,29,38,43,47,48,49,51,52,53, #5
57,62,71,79,88,93,97,98,99];
for slicesize from 2 by 2 while k<N do #6
userinfo(2,procname,"slicesize=",slicesize); #00
oldL:=newL; #7
userinfo(3,procname,"oldL=",oldL); #00

is149:=subs(_slicesize=slicesize, #8
_oldQ=oldQ,_newQ=newQ,
proc(n)
local r,s;
option remember;
r:=n;
while r<>0 do
s:=irem(r,10^_slicesize,'r');
if not (member(s,_newQ)
or
(member(s,_oldQ) and r=0)
) then
RETURN(false)
fi
od;
true
end);
for qq to 99 while k<N do #9
q:=qq*10^slicesize;
l:=0;
for r in oldL do
n:=q+r; #10
n2:=n^2;
tail:=irem(n2,10^(slicesize+2));
if is149(tail) then #11
l:=l+1;
newT[qq,l]:=n;
if is149(n2) then #12
k:=k+1;
res[k]:=n;
userinfo(2,procname,k,res[k]); #00
userinfo(2,procname,"time=",time()-st); #00
if k=N then break fi; #13
fi
fi
od
od;
newL:=sort(convert(newT,list)); #14
oldQ:=oldQ #15
union {seq(seq(10*i+j,i=newQ),j=A)}
union newQ;
newQ:={seq(seq(100*i+j,i=newQ),j=AA)};
od;
[seq(res[i],i=1..N)]
end:

Reprenons les tests.

> infolevel[tricol]:=2:

> start:=time():
tricol(12);
time()-start;

tricol:   "slicesize="   2

tricol:   8   107

tricol:   "time="   .14e-1

tricol:   9   212

tricol:   "time="   .49e-1

tricol:   "slicesize="   4

tricol:   10   31488

tricol:   "time="   1.895

tricol:   11   70107

tricol:   "time="   2.596

tricol:   12   387288

tricol:   "time="   6.234

[Maple Math]

[Maple Math]

Le temps de calcul reste du même ordre de grandeur que dans la version statique avec slicesize=4. Surtout cette version dynamique nous permet d'atteindre le cas N=14 dans un temps raisonnable.

> start:=time():
tricol(14);
time()-start;

tricol:   "slicesize="   2

tricol:   8   107

tricol:   "time="   .13e-1

tricol:   9   212

tricol:   "time="   .44e-1

tricol:   "slicesize="   4

tricol:   10   31488

tricol:   "time="   1.645

tricol:   11   70107

tricol:   "time="   2.258

tricol:   12   387288

tricol:   "time="   5.447

tricol:   "slicesize="   6

tricol:   13   95610729

tricol:   "time="   107.229

tricol:   "slicesize="   8

tricol:   14   446653271

tricol:   "time="   681.336

[Maple Math]

[Maple Math]

> infolevel[tricol]:=1:

Nous atteignons aussi le cas N=16, mais dans un temps déraisonnable.

> start:=time():
tricol(16);
time()-start;

[Maple Math]
[Maple Math]

[Maple Math]

Emploi de tables. La procédure tricol que nous venons d'écrire manque d'efficacité. En particulier l'emploi de member pour tester si un entier ne s'écrit qu'avec les chiffres permis n'est pas satisfaisant, puisqu'il fait sans cesse parcourir un ensemble. Une écriture basée sur des tables serait meilleure. Autrement dit il faudrait remplacer la procédure is149 par une table is149 et employer la procédure assigned. Plus généralement la structure même de Maple repose sur la notion de table de hachage. Pour obtenir un programme efficace, il faut donc employer au mieux cette structure. Nous allons donc repartir de zéro et écrire une nouvelle procédure tricol fondée sur une structure de données qui emploie des tables. Cette procédure prendra en argument un entier N, ainsi qu'un deuxième argument que nous préciserons plus loin et renvoie la liste des N premiers nombres tricolores.

Avant de décrire cette procédure, précisons que son code est dans le fichier ex9_bis_.mpl pour la version V.5 et dans le fichier ex9_bis_V4_.mpl pour la version V.4.

Pour chaque entier s, nous considérons la liste ordonnée des résidus modulo 10^s dont le carré a un résidu modulo 10^s qui ne comporte que les chiffres permis. Par exemple 100107 figure dans les listes associées à s=6 et s=7 mais pas dans celle associée à s=8. En effet son carré vaut 10021411449 et les sept derniers chiffres sont dans l'alphabet {1,4,9}, mais pas le huitième à partir de la fin. Autrement dit, 100107 est un suffixe acceptable pour les longueurs s=6 et s=7.

La liste associée à s, nous la voyons comme une liste chaînée et celle-ci est réalisée par une table nommée Right. Pour chaque élément i de la liste Right[i] est l'élément suivant. Pour amorcer la structure nous employons l'indice -s. Le premier élément de la liste est donc Right[-s].

Nous allons démarrer les calculs avec s=2. Le code qui définit la table Right pour cette longueur de suffixe est donc le suivant.

  Right[-2]:= 1;
  Right[ 1]:= 2;
  Right[ 2]:= 3;
  Right[ 3]:= 7;
  Right[ 7]:=12;
  Right[12]:=21;
  Right[21]:=29;
  Right[29]:=38;
  Right[38]:=43;
  Right[43]:=47;
  Right[47]:=48;
  Right[48]:=49;
  Right[49]:=51;
  Right[51]:=52;
  Right[52]:=53;
  Right[53]:=57;
  Right[57]:=62;
  Right[62]:=71;
  Right[71]:=79;
  Right[79]:=88;
  Right[88]:=93; 

Bien sûr, nous remployons les résultats accumulés dans les expériences précédentes. Le nombre d'éléments de la liste associée à l'entier s croît rapidement. En démarrant avec s=2, on a successivement les valeurs 21, 26, 72, 200, 596, 1756, 5260, 15876, 47816 en terminant avec s=10 (ces valeurs peuvent être fournies en modifiant très légérement la procédure que nous allons écrire). Avec une petite régression linéaire, on constate une croissance exponentielle, ce qui n'est guère surprenant.

L'algorithme va consister à passer d'une valeur s à une valeur supérieure s+delta(s). La variation d'un cran au suivant sera fournie par un deuxième argument passée à la procédure tricol, une procédure delta. On suppose que cette procédure est définie sur les entiers supérieurs ou égaux à 2 et renvoie un entier strictement positif. Si l'on voulait programmer dans le style du logiciel, on rendrait cet argument optionnel en prenant pour valeur par défaut la procédure qui renvoie la constante 1.

D'autre part il nous faut un test qui permette de reconnaître qu'un entier naturel possède une écriture décimale ne comportant que les mots (non vides) sur l'alphabet {1,4,9}. Ceci va nécessiter une deuxième structure de données. Nous créons une table Nb indexée par les entiers à partir de zéro et dont les valeurs sont les mots (non vides) sur l'alphabet {1,4,9}. On réalise ainsi la suite strictement croissante des entiers dont l'écriture décimale ne comporte que 1, 4 ou 9. D'autre part et de manière à pouvoir gérer cette table, nous créons une table B. Pour l'indice s, cette table B donne l'indice du premier mot de longueur s dans la table Nb. On voit que B[s] vaut (3^s-3)/2. Puisqu'on a décidé de commencer à la longueur 2, on démarre la construction de cette table par les instructions suivantes.

  B[1]:=0;  
  Nb[0]:=1;
  Nb[1]:=4;
  Nb[2]:=9;
  B[2]:=3;
  Nb[3]:=11;
  Nb[4]:=14;
  Nb[5]:=19;
  Nb[6]:=41;
  Nb[7]:=44;
  Nb[8]:=49;
  Nb[9]:=91;
  Nb[10]:=94;
  Nb[11]:=99;

Ensuite ces deux tables seront mises à jour au cours de l'itération. Évidemment la taille de la table Nb croît en 3^s.

Pour reconnaître qu'un entier a une écriture décimale qui ne comporte que 1, 4 ou 9, on emploie une table is149. Les entiers admissibles sont les indices de cette table. Quant à la valeur associée à un entier admissible, c'est la longueur de son écriture décimale. En effet les expériences précédentes nous ont montré que nous avions besoin de cette information. Quand nous vérifions qu'un nouvel entier est admissible, nous le découpons en tranches de longeur s et seule la dernière tranche, du côté des poids forts, peut être plus courte.

Dans la suite les marques #i font référence au contenu du fichier ex9_bis_.mpl (ou ex9_bis_V4_.mpl).

Le calcul consiste en une boucle. La condition d'arrêt est que la variable k qui compte les nombres tricolores obtenus atteignent la valeur N. Nous passons de l'entier s à l'entier nexts=s+delta(s). Nous préparons la table Right pour la longueur nexts, en initialisant la liste chaînée (#2). Ensuite (#3), nous mettons à jour les tables B, Nb et is149.

La phase suivante est le coeur du calcul. Elle consiste à trouver les préfixes possibles pour les suffixes qui figurent dans la liste chaînée associée à s. Précisément, on veut à la fois les préfixes qui vont donner les solutions modulo 10^nexts et les solutions en entiers comprises entre 10^s et 10^nexts. Les préfixes possibles sont les écritures des entiers de zéro à 10^delta(s)-1.

La valeur zéro demande un traitement spécial. Par exemple, l'entier 771 a pour carré 594441. Il va apparaître comme suffixe pour s=3 et doit être conservé pour s=4 et s=5. Il sera évacué pour s=6. Il doit figurer dans les trois listes chaînées associées à s=3, s=4 et s=5. Cependant nous employons la même table Right pour toutes ces listes. Pour ne pas perturber la table de manière inopinée, nous sommes amenés à utiliser provisoirement une table specialRight (#4). Après le traitement du cas général nous actualisons la table Right en remettant en tête de la liste chaînée associée au niveau nexts la liste chaînée représentée par la table specialRight (#14). On pourrait revoir le programme en employant une table par liste chaînée pour éviter ce problème. Nous laissons le lecteur améliorer ceci (et tout ce qu'il veut d'ailleurs). Il faut noter que le fait de préfixer par zéro ne peut pas fournir de nouveau nombre tricolore.

Pour le cas général d'un préfixe entre 1 et 10^delta(s)-1 (#5), on teste les suffixes disponibles de longueur s et on regarde si l'on obtient un suffixe acceptable pour la longueur nexts, c'est-à-dire une solution modulo 10^nexts (#6). Si c'est le cas on se demande si l'on affaire à un nouveau nombre tricolore (#7). On notera que dans la définition initiale de la table is149 figure l'instruction (#0)

  is149[0]:=0;

pour le cas particulier où le carré de l'entier considéré aurait une écriture dont la longueur est multiple de nexts.

Nous vérifions la correction syntaxique du programme à l'aide de l'utilitaire Mint. Cet utilitaire a été utilisé plusieurs fois au cours de l'écriture du programme. On évite ainsi des erreurs grossières sans trop d'effort. Sous Maple, on peut aussi employer maplemint. Pour tout cela voir les pages d'aide ?maplemint et ?mint.

quarts.inria.fr% mint ex9_bis_.mpl
    |\^/|      Maple V Release 5 Diagnostic Program
._|\|   |/|_.  Copyright (c) 1981-1997 by Waterloo Maple Inc. 
 \  MINT   /   All rights reserved. 
 <____ ____>   Maple and Maple V are registered trademarks of
      |        Waterloo Maple Inc.

Il n'y a pas de message d'erreur donc le programme est syntaxiquement correct.

Passons à l'exécution. On peut hésiter sur le choix de la fonction delta. Nous testons deux exemples simples. L'information est fournie grâce à l'emploi de userinfo dans la procédure.

> read "ex9_bis_.mpl";

> infolevel[tricol]:=2:

> tricol(14,proc(x) 1 end);

tricol:   "slicesize="   3

tricol:   8   107

tricol:   "time="   .32e-1

tricol:   9   212

tricol:   "time="   .48e-1

tricol:   "slicesize="   4

tricol:   "slicesize="   5

tricol:   10   31488

tricol:   "time="   .569

tricol:   11   70107

tricol:   "time="   .754

tricol:   "slicesize="   6

tricol:   12   387288

tricol:   "time="   1.824

tricol:   "slicesize="   7

tricol:   "slicesize="   8

tricol:   13   95610729

tricol:   "time="   25.344

tricol:   "slicesize="   9

tricol:   14   446653271

tricol:   "time="   63.683

[Maple Math]

> tricol(14,proc(x) 2 end);

tricol:   "slicesize="   4

tricol:   8   107

tricol:   "time="   .55e-1

tricol:   9   212

tricol:   "time="   .73e-1

tricol:   "slicesize="   6

tricol:   10   31488

tricol:   "time="   1.681

tricol:   11   70107

tricol:   "time="   1.858

tricol:   12   387288

tricol:   "time="   3.633

tricol:   "slicesize="   8

tricol:   13   95610729

tricol:   "time="   49.821

tricol:   "slicesize="   10

tricol:   14   446653271

tricol:   "time="   151.933

[Maple Math]

> tricol(14,proc(x) 3 end);

tricol:   "slicesize="   5

tricol:   8   107

tricol:   "time="   .237

tricol:   9   212

tricol:   "time="   .255

tricol:   10   31488

tricol:   "time="   5.370

tricol:   11   70107

tricol:   "time="   9.981

tricol:   "slicesize="   8

tricol:   12   387288

tricol:   "time="   18.505

tricol:   13   95610729

tricol:   "time="   154.715

tricol:   "slicesize="   11

tricol:   14   446653271

tricol:   "time="   715.890

[Maple Math]

Il est clair qu'il vaut mieux avancer de 1 à chaque pas. Allons y donc pour le beau cas.

> tricol(16,proc(x) 1 end);

tricol:   "slicesize="   3

tricol:   8   107

tricol:   "time="   .39e-1

tricol:   9   212

tricol:   "time="   .57e-1

tricol:   "slicesize="   4

tricol:   "slicesize="   5

tricol:   10   31488

tricol:   "time="   .735

tricol:   11   70107

tricol:   "time="   .983

tricol:   "slicesize="   6

tricol:   12   387288

tricol:   "time="   2.243

tricol:   "slicesize="   7

tricol:   "slicesize="   8

tricol:   13   95610729

tricol:   "time="   26.916

tricol:   "slicesize="   9

tricol:   14   446653271

tricol:   "time="   64.089

tricol:   "slicesize="   10

tricol:   15   3148717107

tricol:   "time="   242.668

tricol:   "slicesize="   11

tricol:   16   21081079479

tricol:   "time="   1279.577

[Maple Math]
[Maple Math]

Nous obtenons le résultat cherché dans un temps raisonnable. Nous constatons qu'avec cette nouvelle version, le temps de calcul a été divisé par 15.

> 19029./1279;

[Maple Math]

En corrigeant l'erreur de conception signalée plus haut, on peut encore gagner un peu de temps (ex9_ter_.mpl). Le problème qui surgit ensuite est celui de la place en mémoire. En tout cas, le gain est important et il est dû à l'emploi des tables.

Peut-être peut-on encore améliorer la procédure. Par exemple, nous avons tenu compte des chiffres de poids faibles mais aucunement des chiffres de poids forts. Il faut cependant être prudent : quand on emploie des tranches de largeur 4 on trouve pour la tranche 9479 un préfixe possible qui est 7 et dans le calcul il donnera plus tard le seizième nombre tricolore 21081079479. Pourtant 79479 n'est pas un nombre tricolore. Il n'est donc pas évident que l'on puisse éviter de tester tous les préfixes. On voit que l'on peut encore réfléchir sur ce problème. D'un autre côté, il est tout à fait particulier et l'intérêt de la notion de nombres tricolores est bien faible. Il est bien plus important de garder en mémoire l'apport des tables pour l'efficacité du calcul.