Par exemple tu fais un programme avec puiss(a,n) qui doit retourner a^n en ne faisant que des multiplications. Il peut fonctionner avec puiss(2 % 101, 10**6) mais
on pourrait aussi verifier facilement qu'il marche bien et illustrer le nombre de tours avec puiss(g,10**6)
Si le cout de g^a*g^b est de l'ordre du cout de a+b ca marche tres bien.
Mais ce qui m'inquiète plus ce sont les lenteurs et complications innatendues qui apparaissent dans les calculs.
Ex: j'ai une config en mode regroup, le résultat que j'obtiens est regroupé donc c'est surprenant que l'on ait besoin de regrouper des calculs non?
Code : Tout sélectionner
puiss(g,n,loi):={ local u,v;
u:=1;v:=g;
while(n>1){
if (irem(n , 2 )==0)
{ v:=loi(v,v) ; n:=n/2; }
else
{ u:=loi(u,v) ; v:=loi(v,v) ; n:=(n-1)/2; }
}
return loi(u,v);
};
Sous xcas14 les trois lois suivantes donnent le même résultat pour n petit mais avec des temps tres différents:
Code : Tout sélectionner
mult0(u,v):=u*v;
mult1(u,v):=regrouper(u*v);
mult2(u,v):=lin(regrouper(u*v));
Sous xcas
Code : Tout sélectionner
puiss(g,10^6,mult0); // 0.85s retourne: g^1000000
time(rep1:=puiss(g,10^6,mult1));rep1// 2000 fois plus rapide que mult0; retourne aussi g^1000000
time(rep2:=puiss(g,10**6,mult2));rep2 // La c'est comme avec mult1
on comprend mieux sous icas:
Code : Tout sélectionner
6>> puiss(g,10**2,mult0); // d'ou la lenteur
g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g*g
Ensuite, même si l'on utilise regroup, on peut avoir des expressions qui ne se simplifient plus facilement (simplify n'aide pas) alors que je n'ai entré que des polynomes.
Code : Tout sélectionner
16>> puiss(g,10**30,mult1); // regroup se complique
g^1073741824*exp(2147483648*ln(g))^216652756*exp(4611686018427387904*ln(g))^2092069697*exp(9903520314283042199192993792*ln(g))^100
// Time 0.03
17>> puiss(g,10**30,mult2); // lin + regroup peut melanger les ecritures et complique ausi.
g^1073741824*exp(999999999999999999998926258176*ln(g))
// Time 0.03
18>> puiss(g,10**60,mult1); // lorsque l'on augmente encore regroup est de pire en pire
exp(2147483648*ln(g))^536870912*exp(4611686018427387904*ln(g))^1368802148*exp(9903520314283042199192993792*ln(g))^991039844*exp(21267647932558653966460912964485513216*ln(g))^572805149*exp(45671926166590716193865151022383844364247891968*ln(g))^1692713715*exp(98079714615416886934934209737619787751599303819750539264*ln(g))^10195
// Time 0.05
19>> puiss(g,10**60,mult2); // lorsque c'est assez grand, iin + regroup obtient une certaine coherence
exp(1000000000000000000000000000000000000000000000000000000000000*ln(g))