HP 30b

[C.Ret]

Effectivement, il doit y avoir une bonne raison et il n'est pas sûr que de tenter d'exclure plus de multiples fasse gagner beaucoup de temps au programme.

Quoi que, je me suis amusé à faire un peu de statistiques dans le cas fort long de la recherche des facteurs premiers de 9999999967, il faut que mon code génére autant que possible des nombre premiers jusqu'à environ 99999 (~ 1E6)

Si l'on évite de tester les multiples de 2,3 et 5 (donc par pas de 3à comme dans le code exposé ci-dessus) on se rend compte que seulement 36% des "facteurs p" testés sont premiers. C'est à dire à peine plus d'un tier. C'est à dire que la calculatrice passe environ les deux tiers du temps de recherche à re-tester des multiples de facteurs premiers déjà testés !

Il y a donc là peut-être une piste pour augmenter les performances du programme ?

Si l'on utilise l'astuce avec les multiples de 2, 3, 5 et 7 (donc 210) on arrive alors seulement à env. 42% et 46.5% avec 2,3,5,7 et 11 (donc 2310), Il faut utiliser 2,3,5,7,11 et 13 (soit 30030) pour péniblement atteindre 58%. On pourrait espérer 71% de facteur testé premiers, en tenant compte de 2,3,5,7,11,13 et 17 (soit 510510). On a une chance de faire 2x plus vite ? Mais il y a alors près 10000 termes dans la somme de la boucle. Difficile de programmer cela sur un Pocket sans gestion de fichiers.

Et tant qu'à utiliser des fichiers importants, autant utiliser directement la liste des nombres premiers, on fera alors 100% de tests avec des facteurs premiers et on aura alors réellement optimisé le temps de recherche des facteurs.

J'attends toujours avec impatience l'algorithme de gege, car comme il le souligner, la recherche de la décomposition en facteur premiers n'est pas exactement un test de primalité.

Code : Tout sélectionner

+1   10%
+2

[gege]

Oui oui j'arrive !!
Mais j'ai laissé ma TI89 au boulot... Ce sera pour demain.

Pour info, il s'agit d'un test basé sur le petit théorème de Fermat (p premier => a^(p-1)=1 [p] ) un peu amélioré, et ça tourne en quelques secondes.
G.E.

[C.Ret]

Je trépigne d'impatience.

Mais je n'aurais pas trop le temps avant le prochain Week-End.
Alors je vais ronger mon frein d'ici là.

Je viens de me rendre compte que je n'ai pas posté la version BASIC du programme de décomposition en produit de facteurs premiers. C'est important, car bien qu'utilisant exactement le mêm principe que cemui en RPL, il est d'une structure très simple et qui paraitra plus lisible aux lecteurs de ce forum et autre utilisateur de Pockets basiques:

Comme pour la version RPL, le programme BASIC utilise un sous-programme pour faire les tests de divisbilité et afficher l'expression algébrique.

Cette version a mis 33min pour "décomposer" 9999999967 en ces deux facteurs 1 et 9999999967 sur une Ti-74 BASICALC.

Code : Tout sélectionner

 10 INPUT "N=";X:IF X=0 OR X<>INT(X) THEN END
 20 PRINT X;"=";SGN(X);:X=ABS(X)
 30 P=2:GOSUB 100:P=3:GOSUB 100:P=5:GOSUB 100:P=7
 40 GOSUB 100:P=P+4:GOSUB 100:P=P+2:GOSUB 100:P=P+4:GOSUB 100:P=P+2
 50 GOSUB 100:P=P+4:GOSUB 100:P=P+6:GOSUB 100:P=P+2:GOSUB 100:P=P+6
 60 IF P*P<=X THEN 40
 70 IF X>1 THEN PRINT "x";X;
 80 PRINT ".":PAUSE:RUN
 90 REM ----------------------------------------------------------------------------------------------
100 N=0
110 IF X/P=INT(X/P) THEN N=N+1:X=X/P:GOTO 110
120 IF N>0 THEN PRINT "x";P;
130 IF N>1 THEN PRINT "^";N;
140 RETURN

[gege]

Coucou, voici mon programme, mais je ne suis plus sûr qu'il fonctionne, il y avait une ligne incorrecte, et j'ai fait selon mes lointains souvenirs.

Code : Tout sélectionner

lehmann(n)
Func
@ (n) test de primalite
Local v
If 0=mod(n,2)
Return false
seq(rand(n-1),I,1,20)->v
If 1<product(gcd(n,v))
Return false
seq(powermod(v[i],(n-1)/2,n),i,1,20)->v
seq(when(n=1+v[i],-1,v[i]),i,1,20)->v
If 1<abs(product(v))
Return false
Return true
EndFunc

powermod(a,b,c)
Func
@ (a,b,c) a^b mod c
Local p
1->p:While 0<>b
If 1=mod(b,2)
mod(p*a,c)->p
mod(a*a,c)->a
(b-mod(b,2))/2->b
EndWhile
Return p
EndFunc

Et si on tape lehmann(9999999967), la TI89 renvoie true au bout de 1 minute 15 secondes.
Il faudra que je retrouve le principe théorique si ça intéresse quelqu'un.
D'ailleurs les habitués vont tout de suite me citer la série d'articles parus sur ce thème dans les premiers numéros de "l'Ordinateur de Poche", non ??
A bientôt
G.E

EDIT : même programme retapé sur la nSpire, s'exécute en un peu moins de 2 secondes. C'est mieux qu'une minable accélération d'un facteur 26 par rapport à la factorisation complète en BASIC

[C.Ret]

Ah, oui je vois le type de test. basé sur 20 valeurs tests prises au hasard.

Mais 1'15" pour un test probalistique qui dit si le nombre est composé ou s'il a une grande chance d'être premier, c'est encore beaucoup. Je suis sûr que sur la Ti89, un test déterministe de 99999999967 comme celui que je proposais se fait pour un temps à peine plus long (en tout cas pas les 20 ou 30 min des antiquité que sont la HP-28S ou le BASICL TI-74, ou plus d'une heure le truc étrange et récent de chez HP-30b)

Sinon, merci, l'idée de faire un test probalistique en choisissatn suffisamment de valeurs (ici 20) doit donner tout de même la bonne réponse dans 99.999999% des cas, et comme il n'y a pas tant que ça de nombre premiers entre 1 et 9999999967, ce test peut être considéré comme "déterministe".

Pour les fans de RPL: l'équivalent du programme proposé par gege adapté pour une HP28C/S

Code : Tout sélectionner

STACK      1:n       ----> 0  =composite  |  1 =prime

« -> n
  « 0                         @ False/composite
    IF n 2 MOD
    THEN
      1 20 START
        RAND n * IP           @ 0 <= INTEGER RND  < n  
        -> v
          «
            IF n v GCD 1 > 
            THEN ABORT        @ return false
            END
            v
            n 1 - 2 /
            n PWRMOD          @ a^b MOD c
             
            IF n OVER 1 + ==
            THEN DROP -1      @ when n=1+v(i)
            END
             
            IF ABS 1 > 
            THEN ABORT        @ return false
            END
          »
      NEXT
      DROP 1                  @ return True/ (greatly prim's probable)
   END
  »
»
'ISPRIM?' STO

Code : Tout sélectionner

STACK   @ 2: a
        @ 1: b    --------->  1: gcd(a,b)

« WHILE DUP                   @ tant que b>0
  REPEAT
    SWAP                      @ a<->b
    OVER MOD                  @ b <- a MOD b
  END
  DROP                             
»
'GCD' STO

Code : Tout sélectionner

STACK  @ 3: a
       @ 2: b
       @ 1: c    -- ------->  1: a^b MOD c

« 1  ROT                      @ 4:a 3:c 2:p 1:b
  WHILE DUP 0 <>
  REPEAT
    IF DUP 2 MOD 1 ==         @ b MOD 2 == 1
    THEN 
      4 PICK ROT *            @ 1:a.p
      3 PICk MOD              @ a.p MOD c
      SWAP                    @ -> p
    END
    4 ROLL DUP * 4 PICK MOD   @ a.a MOD c
    4 ROLLD                   @ -> a
    DUP 2 MOD - 2 /           @ (b-(b MOD 2))/2 ->b
  END
  DROP ROT ROT DROP2          @ return p   (drop a b & c )
»
'PWRMOD' STO

P.S.: J'ai un soucis avec cet algorithme pour tester des nombres N supérieur à 10^6, car lors du calcul de POWERMOD, il faut calculer (a*a MOD c). Or, mon HP28S n'a que 12 chiffres significatifs et donc le résultat de MOD est irrémédiablement faux.

Tout nombre supérieur à 1E6 pose ce problème (dont 9999999967 qui est vu comme 'composé') à cause de cet inconvénient du calcul de a^b MOD c.

Sinon, effectivement la méthode est bonne et permet à une HP28S de déterminer si un nombre est composé ou très probablement premier en moins de 35s (avec les 20 tests aléatoires).

[Gilles59]

Pas terrible, une HP28S met environ 20min pour découvrir que 9999999967 est premier,

Mon expérience me dit qu'une HP48 doit faire cela en moint de 10min et il y a toutes les chances qu'une 50g le fasse en moins d'une minute !

Effectivement cette 30b est surprenante !

Je réveille ce topic, car j'ai vu sur HPMUSEUM qu'une 30B effectuerait le Savage Benchmark (voir le topic 15 CLE) en 6,5 sec ce qui est étonnamment rapide.... et un peu contradictoire avec ce topic.

qq'un en a ici .?

Pour revenir au sujet d'ici sur 50G, c'est intégré : (sur 48SX dejà il me semble)

9999999967 ISPRIME?
renvoie 'vrai' en 0.43 sec

Idem pour les facteurs.Par ex :

12 FACTORS
renvoie { 3 1. 2 2. } comprendre 3 x 2²

Il y aussi DIVIS qui donne tous les diviseurs d'un nombre
12 DIVIS
renvoie { 1 2 4 3 6 12 }

Tout çà est tres rapide mais avec des (tres) grands nombres

Je vous passe les cmdes pour les premiers suivants ,précedents etc. Tous cela sur des entiers 'infinis'