Valuation p-adique

Bugs

Modérateur : xcasadmin

joaopa
Messages : 29
Inscription : dim. sept. 14, 2014 10:18 pm

Valuation p-adique

Message par joaopa » lun. oct. 12, 2020 5:57 am

Bonjour,

est-il possible de calculer la valuation p-adique d'un entier relatif sans passer par la factorisation complète qui est très gourmande en temps?

Merci d'avance.

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

Re: Valuation p-adique

Message par parisse » lun. oct. 12, 2020 6:19 am

Il suffit de faire un petit programme du style

Code : Tout sélectionner

valu(n,p):={ local v:=0; tantque irem(n,p)=0 faire n=n/p; v++; ftantque; return v;}

joaopa
Messages : 29
Inscription : dim. sept. 14, 2014 10:18 pm

Re: Valuation p-adique

Message par joaopa » lun. oct. 12, 2020 6:39 am

Merci c'est que j'avais fait en attendant qu'il y est une fonction native dans XCas... :mrgreen:
En fait, ce message était pour savoir si elle ne pourrait pas être implémentée dans Xcas.

Je l'avais codée comme ceci: penses-tu qu'elle est moins rapide que ta fonction?

Code : Tout sélectionner

v(n,p):= {b:=0;tantque n mod p^b==0 faire b:=b+1; ftantque; return b-1;};

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

Re: Valuation p-adique

Message par parisse » lun. oct. 12, 2020 1:10 pm

Pas pour de petites valuations, car je fais deux divisions par iteration. Je pourrais optimiser en utilisant iquorem, et ca serait alors un peu plus rapide lorsque la valuation est grande, parce qu'en divisant par p, on diminue la taille des arguments alors que votre version travaille toujours avec n et un entier de taille croissante, a quoi il faut ajouter le temps de calcul de p^b.
Une version native serait un peu plus rapide, en appelant directement les fonctions de la libgmp sans mettre les quotients intermediaires dans des giac::gen. Mais pas enormement plus rapide, peut-etre un facteur 2 ou 3.

joaopa
Messages : 29
Inscription : dim. sept. 14, 2014 10:18 pm

Re: Valuation p-adique

Message par joaopa » mer. oct. 14, 2020 2:30 am

Penses-tu l'implémenter en native? Elle est vraiment pratique cette fonction.

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

Re: Valuation p-adique

Message par parisse » mer. oct. 14, 2020 6:21 am

Ok, j'ajoute cette fonctionnalite a la commande valuation.

joaopa
Messages : 29
Inscription : dim. sept. 14, 2014 10:18 pm

Re: Valuation p-adique

Message par joaopa » mer. oct. 14, 2020 7:02 am

Super!! 8) Merci

Répondre