Le forum de XCAS

Xcas: un logiciel libre de calcul formel
Nous sommes actuellement le Mer Avr 25, 2018 12:23 pm

Heures au format UTC




Publier un nouveau sujet Répondre au sujet  [ 6 messages ] 
Auteur Message
 Sujet du message: grande puissances formelles
MessagePublié: Jeu Nov 02, 2017 12:28 pm 
Hors-ligne

Inscrit le: Dim Mai 20, 2007 7:09 am
Messages: 1064
Localisation: Paris
Actuellement, si g est un symbole, g^n bascule en notation exponentielle à partir de 2^31.
Code:
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?


Haut
 Profil  
 
MessagePublié: Jeu Nov 02, 2017 3:47 pm 
Hors-ligne

Inscrit le: Ven Aoû 28, 2009 3:34 pm
Messages: 1077
salut,
lin(g^(2^31)*g^(2^31)-g^(2^32))


Haut
 Profil  
 
MessagePublié: Ven Nov 03, 2017 9:05 am 
Hors-ligne

Inscrit le: Dim Mai 20, 2007 7:09 am
Messages: 1064
Localisation: Paris
OK mais lin tout seul se met a pédaler assez vite lorsque je fais a:=a*a:
Code:
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)


Haut
 Profil  
 
MessagePublié: Ven Nov 03, 2017 2:05 pm 
Hors-ligne

Inscrit le: Mar Déc 20, 2005 4:02 pm
Messages: 4301
Je ne comprends pas comment de grandes puissances formelles peuvent servir a illustrer la puissance rapide.


Haut
 Profil  
 
MessagePublié: Sam Nov 04, 2017 9:50 am 
Hors-ligne

Inscrit le: Dim Mai 20, 2007 7:09 am
Messages: 1064
Localisation: Paris
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:
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:
mult0(u,v):=u*v;
mult1(u,v):=regrouper(u*v);
mult2(u,v):=lin(regrouper(u*v));


Sous xcas
Code:
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:
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:
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))


Haut
 Profil  
 
MessagePublié: Sam Nov 04, 2017 4:03 pm 
Hors-ligne

Inscrit le: Mar Déc 20, 2005 4:02 pm
Messages: 4301
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.


Haut
 Profil  
 
Afficher les messages publiés depuis:  Trier par  
Publier un nouveau sujet Répondre au sujet  [ 6 messages ] 

Heures au format UTC


Qui est en ligne ?

Utilisateurs parcourant actuellement ce forum : Aucun utilisateur inscrit et 8 invités


Vous ne pouvez pas publier de nouveaux sujets dans ce forum
Vous ne pouvez pas répondre aux sujets dans ce forum
Vous ne pouvez pas éditer vos messages dans ce forum
Vous ne pouvez pas supprimer vos messages dans ce forum
Vous ne pouvez pas insérer de pièces jointes dans ce forum

Rechercher pour:
Sauter vers:  
cron
Powered by phpBB® Forum Software © phpBB Group
Traduction réalisée par Maël Soucaze © 2009 phpBB.fr