 |
Apprendre Maple
Site dédié au logiciel de calcul formel Maple
|
| Voir le sujet précédent :: Voir le sujet suivant |
| Auteur |
Message |
Erable
Inscrit le: 06 Fév 2010
Messages: 16
|
 Posté le: 27 Mai 2010 17:38 Sujet du message: Exponentiation rapide qui ralentit |
 |
|
| Code: | ExponentiationRapide := proc (Matrice, Puissance, Taille)
local A, Resultat, n; A := Matrice; n := Puissance; Resultat := Matrix(Taille, Taille, shape = identity);
while 0 < n do
if type(n, odd) then Resultat := evalm(`&*`(Resultat, A)); n := n-1
else A := evalm(`&*`(A, A)); n := (1/2)*n
end if
end do;
evalm(Resultat)
end proc |
Le temps d'exécution est plus long que quand je fais calculer normalement la puissance d'une matrice... Maple12 utilise déjà cette technique dans ses calculs? |
|
| Revenir en haut de page |
|
 |
ALS
Inscrit le: 11 Sep 2006
Messages: 647
|
| Posté le: 28 Mai 2010 7:38 Sujet du message: |
|
|
Bonjour,
J'ai modifié &* en Multiply, sinon j'avais une erreur sous MAPLE 14. Maintenant, cela fonctionne et j'ai mesuré le temps de calcul sous les 2 méthodes pour une matrice aléatoire 100x100. Pour les petites valeurs de Taille, c'est maintenant légèrement meilleur avec ExponentiationRapide quand je remplace "if type(n,odd)" par "if n mod 2 =1". Pour les grandes valeurs de Taille, je suis d'accord avec vous.
Je pense qu'en interne MAPLE utilise cet algorithme, mais comment le savoir? on ne réussit pas à lister le code des fonctions du package LinearAlgebra.
| Code: |
> ExponentiationRapide := proc (Matrice, Puissance, Taille)
> local A, Resultat, n;
> A := Matrice; n := Puissance; Resultat := Matrix(Taille, Taille, shape = identity);
> while 0 < n do
> if n mod 2=1 then Resultat := Multiply(Resultat, A);
> n := n-1
> else A := Multiply(A, A);
> n := (1/2)*n
> end if
> end do;
> evalm(Resultat)
> end proc:
> with(LinearAlgebra):
> A:=RandomMatrix(100,100,generator=1..9);
[ 100 x 100 Matrix ]
A := [ Data Type: anything ]
[ Storage: rectangular ]
[ Order: Fortran_order ]
> t:=time(): ExponentiationRapide(A,15,100): time()-t;
> t:=time(): evalm(A^15): time()-t;
4.047
4.109
> t:=time(): ExponentiationRapide(A,100,100): time()-t;
> t:=time(): evalm(A^100): time()-t;
10.328
9.422
|
Je pense qu'il vaudrait mieux comparer ExponentiationRapide avec l'algorithme naif ExponentiationNaive:
| Code: |
> ExponentiationNaive := proc (Matrice, Puissance)
> local A,k, Resultat:
> Resultat := Matrice;
> for k to Puissance-1 do
> Resultat:=Multiply(Matrice,Resultat)
> end do:
> evalm(Resultat)
> end proc:
> A:=RandomMatrix(100,100,generator=1..9);
[ 100 x 100 Matrix ]
A := [ Data Type: anything ]
[ Storage: rectangular ]
[ Order: Fortran_order ]
> t:=time(): ExponentiationNaive(A,15,100): time()-t;
> t:=time(): ExponentiationRapide(A,15,100): time()-t;
11.485
3.969
|
A plus tard. |
|
| Revenir en haut de page |
|
|
Erable
Inscrit le: 06 Fév 2010
Messages: 16
|
| Posté le: 28 Mai 2010 22:58 Sujet du message: |
|
|
| Oui, Maple doit utiliser cet algorithme en interne, il est quand même assez basique... mais pratique. |
|
| Revenir en haut de page |
|
|
|
|
Vous ne pouvez pas poster 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 voter dans les sondages de ce forum
|
Développé par phpBB © 2001, 2006 phpBB Group
Traduction par : phpBB-fr.com
Apprendre Maple - ©
- Alain Le Stang - Navigation optimisée pour une résolution 1024 x 768.
|
Page d'accueil
FAQ
Rechercher
Liste des Membres
Groupes d'utilisateurs
S'enregistrer
Profil
Se connecter pour vérifier ses messages privés
Connexion
