grande puissances formelles

Utilisation de Xcas

Modérateur : xcasadmin

frederic han
Messages : 1113
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

grande puissances formelles

Message par frederic han » jeu. nov. 02, 2017 12:28 pm

Actuellement, si g est un symbole, g^n bascule en notation exponentielle à partir de 2^31.

Code : Tout sélectionner

0>> g^(2^30)
g^1073741824
// Time 0
1>> g^(2^31)
exp(2147483648*ln(g))
// Time 0.01
2>> g^(2^31)*g^(2^31)
exp(2147483648*ln(g))*exp(2147483648*ln(g))
// Time 0
3>> simplify(g^(2^31)*g^(2^31)) 
exp(2147483648*ln(g))^2
4>> simplify(g^(2^31)*g^(2^31)-g^(2^32))
exp(2147483648*ln(g))^2-exp(4294967296*ln(g))
du coup, comment identifier les deux expressions pour avoir 0 au 4?
Mais aussi c'est un peu foutu pour ilustrer les puissances rapides avec une lettre non?

alb
Messages : 1229
Inscription : ven. août 28, 2009 3:34 pm

Re: grande puissances formelles

Message par alb » jeu. nov. 02, 2017 3:47 pm

salut,
lin(g^(2^31)*g^(2^31)-g^(2^32))

frederic han
Messages : 1113
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: grande puissances formelles

Message par frederic han » ven. nov. 03, 2017 9:05 am

OK mais lin tout seul se met a pédaler assez vite lorsque je fais a:=a*a:

Code : Tout sélectionner

a:=g;for(j:=0;j<13;j++){a:=(a*a)}; // 0.75s
a:=g;for(j:=0;j<16;j++){a:=factor(a*a)};// erreur pour j=15
a:=g;for(j:=0;j<12;j++){a:=lin(a*a)};// met deja 0.5s
a:=g;for(j:=0;j<10**4;j++){a:=lin(regroup(a*a))}; // Ouf, celui la fonctionne en 0.5s
a:=g;for(j:=0;j<10**4;j++){a:=(regroup(a*a))}; // celui aussi la fonctionne en 0.5s (meme si differe en ecriture du precedent)

parisse
Messages : 5081
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: grande puissances formelles

Message par parisse » ven. nov. 03, 2017 2:05 pm

Je ne comprends pas comment de grandes puissances formelles peuvent servir a illustrer la puissance rapide.

frederic han
Messages : 1113
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: grande puissances formelles

Message par frederic han » sam. nov. 04, 2017 9:50 am

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

parisse
Messages : 5081
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: grande puissances formelles

Message par parisse » sam. nov. 04, 2017 4:03 pm

En symbolique c'est tres difficile de controler la complexite d'une operation. A mon avis, il faut se limiter a des types qui sont representes par une forme normale, ici ca voudrait dire remplacer une variable formelle par un polynome creux.

Répondre