Maple : décomposition en facteurs premiers

[Lemniscate]

autant !!! Chez moi, c'est instantané ! (j'ai pourtant un PC qui a 5 ans, mais maple 7...)

Pour factoriser 10^8+1 , ça commence à compter en secondes...

Euhh moi pour 10^8+1 ca met 3,6 sec... , j'ai un PC qui a 1an, j'ai peut-être un virus ????

EDIT :

Ainsi, on peut encore accélérer : au lieu de tester 2 puis 3 +2+2+2 ..., on peut tester 2 et 3, puis tester les nombres 5 +2+4 +2+4 +2+4...
On va alors gagner un tiers du temps de calcul.

Alors j'ai essayé ceci dans Maple :

premier_diviseur := proc(N) # N est supposé >= 2
> #leon and me's optimisation 4sec pour 10^8+1
> local p;
> if irem(N,2)=0 then RETURN(2) fi ;
> if irem(N,3)=0 then RETURN(3) fi ;
> p:=5;
> while irem(N,p)0 do
> if irem(p-5,6)=0 then p:=p+2;
> else p:=p+4;fi;
> od;
> RETURN(p);

Comme je l'ai marqué dans Maple, ca met 4sec environ (j'ai fais plusieurs répétitions et ca donne tjrs 4sec) pour 10^8+1

Avec ceci maintenant :

premier_diviseur := proc(N) # N est supposé >= 2
> #leon's optimisation 3.6sec pour 10^8+1
> local p;
> if irem(N,2)=0 then RETURN(2) fi ;
> if irem(N,3)=0 then RETURN(3) fi ;
> p:=5;
> while irem(N,p)0 do p:=p+2;od ;
> RETURN(p);
> end:

Ca met, comme je l'ai mis, 3.6sec pour 10^8+1

Pourquoi perd-t-on du temps alors qu'on a optimisé ?

Je signale que j'ai à chaque fois revalider la procédure "décomposition" après avoir validé l'une ou l'autre des procédures "premier_diviseur"

[leon1789]

Euhh moi pour 10^8+1 ca met 3,6 sec... , j'ai un PC qui a 1an, j'ai peut-être un virus ????

Nan, pas un virus... mais peut-être la version de maple.

Essaie de programmer le coup de la racine carrée, tu vas voir que le temps de calcul tombe à... 0 ms !

[Lemniscate]

On va alors gagner un tiers du temps de calcul.

Tu vois pourquoi ?

Oui car au lieu de
2+2=4 on aura
2+4=6
et que (6-4)/6=1/3


Sinon :

Essaie de programmer le coup de la racine carrée, tu vas voir que le temps de calcul tombe à... 0 ms !

Bon alors j'ai pas compris le théorème que tu utilise (j'essaierais de le prouver plus tard, là j'ai pas trop envie car je vois pas du tout comment faire !) mais j'ai essayé ceci dans la procédure "premier diviseur" :

premier_diviseur := proc(N) # N est supposé >= 2
> #leon's optimisation2 0sec pour 10^8+1
> local p;
> if irem(N,2)=0 then RETURN(2) fi ;
> if irem(N,3)=0 then RETURN(3) fi ;
> p:=5;
> while irem(N,p)0 do
> if p>evalf(sqrt(N)) then p:=N
> else p:=p+2;fi;od;
> RETURN(p);
> end:

Effectivement le temps de calcul chute littéralement !!!

Merci bien !

[leon1789]

ok !

Voilà ce à quoi je pensais :

Code: Tout sélectionner

premier_diviseur := proc(N) # N est supposé >= 2
 local p,RN ;
   if irem(N,2)=0 then RETURN(2) ;
   elif irem(N,3)=0 then RETURN(3) fi ;
   p := 5 ;
   RN := floor(evalf(sqrt(N))) ;
   do
     if p>RN then RETURN(N) ;
     elif irem(N,p)=0 then RETURN(p) fi ;
     p := p+2 ;
 #    if p>RN then RETURN(N) ;
 #    elif irem(N,p)=0 then RETURN(p) fi ;
 #    p := p+4 ;
   od ;
 end :


Les symboles # sont là pour être enlever et constater l'effet +2+4+2+4... au lieu de +2+2+2+2...

De plus, au lieu de calculer un nombre important de fois (comme tu le fais), je le stocke dans une variable (constante) RN (comme Racine de N)

Remarque aussi que RN est un entier (à cause du floor), ce qui accélère encore les calculs.

Du coup, on peut tester maintenant 10^18+1 :id:

[leon1789]

Autre remarque sur ta programmation : essaie d' indenter les lignes :id: c'est plus simple pour bien se repérer dans le code, non ? :zen:

[fatal_error]

Je reviens :D
pour le pas :
on écrit la suite :
2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19
On vire les multiples de 2 et 3:
3,5,7,11,13,17,19
On a bien l'alternance 2-4 a partir de 7.

On peut donc ecrire :
(je connais pas la syntaxe maple donc pseudo code :D)
/***
i:=7
R:=sqrt(n)
tant que i^2<=R et n%i != 0
pas:=6-pas
i:=i+pas
fin tant que
retourner i
***/



Deuxieme remarque, premier diviseur ne retourne normalement qu'une seule fois (si c'est possible) la valeur 2. idem pour 3 et 5 et tous les autres nombres.
Jor si jprends 256*39*25
au premier appel, j'ai 2 qui sort, et le nouveau nombre n est
n/256
Le diviseur 2 est donc exclut.
Inutile de se coltiner les tests 2 3 et 5 dans premier diviseur.
Il voit mieux dans la fonction principales traiter ces 3 cas

Ensuite pour le 10^18, j'ai lu qu'avec multiplequadratic sieve ou pollard rho (dans de moinres mesures) ca roxxait pas mal. Genre 5s avec un 2ghz

J'essaie de tester en c++ là, (genre lalgo de leon1789) mais je suis stupidement bloqué sur un long long int qui veut pas me prendre plus de 10^10 XD

edit:revenge of my unique_neurone

[Patastronch]

Je comprends pas pourquoi changer la syntaxe influe sur le nombres d'opérations de mon algorithme ?

Bien sur que ca change tout. TU apelle 2 fois la fonction au lieu d'une fois a chaque passage.

Un exemple :

Je veux coder la suite :



Mais j'impose la contrainte de n'utiliser que des additions (les multiplications sont presque 10 fois plus couteuse qu'une addition en temps).

Si je fais:

[PHP]
f(entier n): entier
si n>0 alors retourner f(n-1)+f(n-1)+1;
sinon retourner 1;[/PHP]

J'aurais appels à la fonction f.
Par contre si on fait :
[PHP]
f(entier n): entier
si n>0 alors
x=f(n-1);
retourner x+x+1;
sinon retourner 1;[/PHP]

J'aurais seulement appels à f.

Dans le premier cas avec n>80 tu peux revenir l'année prochaine pour avoir ton résultat. Dans le second cas, meme en prenant n =1000000 ca sera quasi instantané.

[leon1789]

[quote="fatal_error"]
On peut donc ecrire :
(je connais pas la syntaxe maple donc pseudo code )
/***
i:=7
R:=sqrt(n)
tant que i^2 une fois qu'un diviseur a été traité, on poursuit la marche en avant dans la recherche du prochain diviseur...


En revanche, je ne suis pas convaincu qu'il faille le mettre dans la routine principale...

[leon1789]

Code: Tout sélectionner

premier_diviseur := proc(N, p0)
# N >=2
# on cherche un nombre premier > p0 et divisant N
 local p,RN ;
   if p0 p0
   fi ;
   RN := floor(evalf(sqrt(N))) ;
   do
     if p>RN then RETURN(N) ;
     elif irem(N,p)=0 then RETURN(p) fi ;
     p := p+2 ;
   od ;
end :

decomposition := proc(N) # N >= 2
 local n,p,e,q,f ;
  n := N ;
  p := 1 ; f := NULL ;
  while n>1 do
    p := premier_diviseur(n,p) ;
    e := 0 ;
    while irem(n,p,'q')=0 do n := q ; e := e +1 od ;
    f := f, p^{e} ; 
  od ;
  RETURN([f]) ;
end ;


Par exemple, le temps de calcul est divisé par deux sur N=1000073001431003663

[leon1789]

R:=sqrt(n)
tant que i^2<=R et n%i != 0

là, il faut choisir entre i^2 <= n ou i <= R :zen:

[fatal_error]

i^2 <= n ou i <= R

si j'ai grillé mon 50/50 je t'appelerai :we:

La raison pour sortir 2 3 et 5, c'est que la suite alternée 2-4-2 commence a partir de 7
(si on a 2-3-5 on a pas l'alternance)

Du coup il est possible d'omettre des diviseurs. Avec mon ptit c++ (c'est triché vu que compilé), j'arrive a moins d'une seconde (en fait la reponse est instanée et mon (clockfin()-clockdebut())/clock_per_sec me retourne 0)

[fatal_error]

Concernant le pas=6-pas
[PHP] do
if p>RN then RETURN(N) ;
elif irem(N,p)=0 then RETURN(p) fi ;
p := p+2 ;
od ;[/PHP]
Ici, on va rajouter un passage de boucle sur 3 :
11-13-17 //avec pas alternatif
11-13-quinze-17 //sans pas alternatif
une soustraction, sauf erreur, c'est un complement a 2
+ l'opération d'adition
soit trois instructions "de base"

Ca compense largement les tests conditionnels
Ensuite,
[PHP]if p0 p0
fi ;[/PHP]
Je trouve dommage a chaque appel de fonctions de tester si N est multiple de 2 ou 3, et même de tester si p0<5. Ces cas sont des cas particuliers et doivent etre traités a part.
Pour ma part, je testerai les diviseur 2 3 et 5 a part avant le while, et mon po vaut alors minimum 7

[Lemniscate]

Bien sur que ca change tout. TU apelle 2 fois la fonction au lieu d'une fois a chaque passage.

Dans le premier cas avec n>80 tu peux revenir l'année prochaine pour avoir ton résultat. Dans le second cas, meme en prenant n =1000000 ca sera quasi instantané.

Ok merci, mais sinon on est d'accord que le nombre de caractères que j'utilise pour nommer une variable n'influe pas sur le temps de calcul ? sauf peut-être si je mets 10^n termes avec n très grand.

Par exmple si je nomme ma procédure (ou une variable même) "calcul" au lieu de "calcul_de_la_decomposition_en_facteurs_premiers_de_tout_entier_N_superieur_a_2" cela ne changera rien ?

Par contre si je change "calcul" par "calculcalculcalcul...calcul" où "calcul" est répété 10^n fois (autrement dit "calcul"^(10^n)) la j'aurais peut être le temps de calcul qui va augmenter ?

Au revoir
Par contre peut-être que si je change "calcul" par

[Patastronch]

mais sinon on est d'accord que le nombre de caractères que j'utilise pour nommer une variable n'influe pas sur le temps de calcul ?

Oui tout a fait, ca n'influence pas vraiment. Tu peux appeler tes variables comme tu veux et c'est meme conseillé de leur donner des noms explicite (donc parfois assez long) afin de comprendre le code facilement.

[leon1789]

Je trouve dommage a chaque appel de fonctions de tester si N est multiple de 2 ou 3, et même de tester si p0<5.

il n'y a que le test p0<5 qui est systématique.

Ces cas sont des cas particuliers et doivent etre traités a part.
Pour ma part, je testerai les diviseur 2 3 et 5 a part avant le while, et mon po vaut alors minimum 7

Ok, si tu veux.

Au fait, pour 2 et 3 je comprends, mais pourquoi 5 ? 5 n'est pas particulier : 5 +2+4+2+4...

[leon1789]

Oui tout a fait, ca n'influence pas vraiment. Tu peux appeler tes variables comme tu veux et c'est meme conseillé de leur donner des noms explicite (donc parfois assez long) afin de comprendre le code facilement.

D'où l'intérêt d'utiliser un éditeur de texte qui complète facilement les noms en appyant sur une simple touche (comme emacs par exemple)

[Patastronch]

D'où l'intérêt d'utiliser un éditeur de texte qui complète facilement les noms en appyant sur une simple touche (comme emacs par exemple)

Non emacs le fait pas nativement Mais peut le faire (Emacs peut potentiellement tout faire si on sait programmer en Lisp).

[leon1789]

Non emacs le fait pas nativement Mais peut le faire (Emacs peut potentiellement tout faire si on sait programmer en Lisp).

Il ne le fait pas nativement, mais il le fait facilement avec cette commande
[FONT=System](global-set-key [tab] 'dabbrev-expand)[/FONT]
La touche TAB permet alors cette complétion.
Maitenant, on peut aussi recommander word pour écrire des sources... :ptdr:

[fatal_error]

mais pourquoi 5 ? 5 n'est pas particulier : 5 +2+4+2+4...

En fait oui tu as raison. Je traitais 5 a cause de mon implémentation super foireuse.

Edit : en fait, jme trimballe mon 5 car dans ma fonction premier diviseur, j'utilise un modolo 6 sur le dernier (plus grand) diviseur qu'on a trouvé.
Du coup, si j'ai 5 qui arrive tout va bien.
Par contre si j'ai 3, 3%6=3 or c'est différent de 1 et 5
Conséquemment, je traite 5 a part.

Apres, on peut certainement s'en sortir, mais la ca chauffe, partiel de math discrètes dans trois jours.... :briques: