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/
|
|
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];
> 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;
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;
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;
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;
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)])));
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));
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);
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
> 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;
> 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;
> start:=time():
tricol_.slicesize(12);
time()-start;
Revenons un peu en arrière pour comparer les résultats.
> start:=time():
tricol_4(12);
time()-start;
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+r où r 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
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
> infolevel[tricol]:=1:
Nous atteignons aussi le cas N=16, mais dans un temps déraisonnable.
> start:=time():
tricol(16);
time()-start;
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
> 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
> 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
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
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;
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.