Misez rapide, accélérez n°1

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Répondre
caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 434
Enregistré le : 05 juin 2014 22:23
Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau

Misez rapide, accélérez n°1

Message par caloubugs »

Et le bonjour à tous les ordipochosaurophiles (je sais c'est un peu capillotracté) ! :roll:

Je vous propose une variante aux MPO, le MRA (qui pourra pourquoi pas, aboutir au MPROA qui serait la version la plus optimisée et rapide...).

Bref, c'est en tombant sur un article des PPX Exchange sur Texas Instrument (consultable ici) que m'est venue l'envie de vous proposer cela.

Bon, le sujet est d'une incroyable originalité et devrait passionner les foules (oui, j'ose parler de foule), à savoir la détermination de la primalité d'un nombre (oh non ! Encore un vieux truc éculé -> non, non, il n'y a pas de n dans le dernier mot 8O).

L'intérêt malgré tout de cette optimisation est quand on doit faire de nombreux traitements sur des nombres premiers (style défi Turing ou Projet Euler), et qu'on veut faire tourner nos algorithmes sur nos vieux tromblons, c'est que l'algo soit performant en temps de réalisation.
In fine, un gain parfois minime peut se transformer en plusieurs minutes de gagnées sur la machine.

Du coup, l'algorithme proposé dans l'article ci-dessus (et que j'ai aussi retrouvé dans le programme assembleur qui a été fait sur HP71B et qu'on trouve dans les Lif) s'appuie sur le principe suivant :
Rien de bien compliqué, on prend le crible d'Eratosthène (je ne sais plus où se met le h d'ailleurs) et on se limite aux trois premiers nombres premiers 2, 3 et 5. On regarde ensuite s'il n'y a pas une cyclicité dans le crible, et ô joie et avec grande surprise, elle apparait tous les 30 nombres (2*3*5).
En fait si on regarde bien, les nombres premiers sont toujours à regarder parmis les suivants : 30n-13, 30n-11, 30n-7, 30n-1, 30n+1, 30n+7, 30n+11, 30n+13 (ce qui fait 8 nombres à tester sur 30, après bien entendu avoir testé les nombres 2, 3, 5 et on démarre ensuite à 30n+7 avec n=0). :ugeek:
Enfin, pour tester un nombre x et voir s'il est premier, il faut donc vérifier s'il est divisible par 2, 3, 5 et par un des nombres de la précédente liste en s'arrêtant à sqr(x).
On retourne alors soit x si le nombre est premier ou le premier diviseur de x.

Je vous propose donc une course de vitesse, rien ne vous empêche d'améliorer l'algo proposé bien au contraire c'est bien le but du jeu (l'implémentation qui en est faite est d'ailleurs déjà largement améliorable, j'en proposerai une version sur TI95).
Le programme doit donc, à partir d'un nombre saisi, renvoyer soit ce nombre s'il est premier, soit son premier diviseur.

Le problème est bien sûr de comparer les perfs entre machines différentes, on pourra toujours faire un tableau des perfs (si en fait ça intéresse au moins quelqu'un, sinon snif, je repartirai tout seul bouder dans mon coin avec mon chrono). L'idéal aussi est d'utiliser, si disponible, les horloges internes (même si parfois, on n'est qu'à la seconde près). Ca pourrait donner aussi quelques benchmarks sympa pour nos machines (je ne dis pas que le sujet est forcément sympa là... :oops:)

Bref, sortez vos montres au 1/100e (sauf pour la HP15c, à la minute près suffira :mrgreen:) et bonne optimisation...

Sommaire des MPO
-------------------------------
Résumé des perfs (en prenant le ratio le plus élevé sur les calculs effectués entre la racine carrée du nombre et le temps mis pour le déterminer premier) :

Code : Tout sélectionner

gege      - Casio Graph 85 : 562 (soit environ 150 tests de division / s)
          - PB700 : 13,1 (3,5)          *
          - PB100 : 71 (19)             **
C.Ret     - C128D : 381 (102)           **************************************
          - TI74 : 111 (30)             ***********
          - HP28S : 177 (47)            ******************
          - HP41C : 20,8 (5,5)          **
zpalm     - HP41CX : 24,8 (6,5)         **
          - HP29E : 11,5 (3)            *
          - HP15CLE : 810 (216)         *********************************************************************************
alain1261 - PB100 : 75 (20)             *******
          - Fx702p : 17,2 (4,5)         **
caloubugs - TI95 : 45 (12)              *****
          - X07 : 88 (23,5)             *********
          - Z-1GR Basic : 375 (100)     **************************************
          - Z-1GR C : 673 (179)         *******************************************************************
          - HP39gII : 2750 (733)        XXX
          - HP71B Assembleur : 333 (89) *********************************
          - PSION 5MX : 71870 (19200)   XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
          - PB-1000 : 95 (25)           **********
          - FX-880P : 126 (34)          *************
          - PC-1403 : 32 (9)            ***
Modifié en dernier par caloubugs le 12 sept. 2015 17:43, modifié 15 fois.
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: Misez rapide, accélérez n°1

Message par gege »

Bonjour,
Voici un programme en trois sous-programmes qui fait quasiment cela sur Casio Graph 85 :

Code : Tout sélectionner

---DIV---
"N"?->N:Prog "DIV0"
List 1

---DIV0---
1->D:1->L
{0}->List 1:0->P
Prog "DIVθ":Prog "DIVθ":2->L:Prog "DIVθ"
While N>D²
Prog "DIVθ":6-L->L
WhileEnd
If N>1:Then P+1->P:N->List 1[P]:IfEnd

--DIVθ--
D+L->D
While 0=Frac(N/D)
N/D->N:P+1->P
D->List 1[P]:WhileEnd
Avec les exemples du document auquel tu fais référence, on a :
10000019 : 6s
les autres : moins de 1s
J'ajoute les exemples de 31629593 (premier) calculé en 10s, et 8043509 (non premier) en 5s.

Cette machine a été choisie pour sa vitesse :D
Les diviseurs testés sont de la forme 6P+/-1, plus simple que de parcourir une liste d'incréments.
G.E.
Avatar du membre
charognard
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4412
Enregistré le : 06 juin 2007 19:28
Localisation : Indre et loire
Contact :

Re: Misez rapide, accélérez n°1

Message par charognard »

Ce n'est pas un Ordinateur de poche !
Et en plus ça n'a rien d'ancien



Sans parler que ce soit du Casio :arrow:


Pour les benchs anciennes machines j'avais fait ça (les anciens du forum connaissent déjà).
ça peut donner des idées de classement
Image
Image
hp41cx
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 195
Enregistré le : 09 déc. 2012 20:51

Re: Misez rapide, accélérez n°1

Message par hp41cx »

===========================
Systems Analyst
My passions (Facebook)
48G+/58C/85B/PC1500A
TH-D74/Samsung A51
Focal & All Basic´s
===========================
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez rapide, accélérez n°1

Message par C.Ret »

En attendant les versions pour calculettes et pockettes, voici une version 8 bits 1 MHz :

Code : Tout sélectionner

LIST

1 INPUT n:t0=TIMER:FAST
2 k=0:f=2:GOSUB 6:f=3:GOSUB 6:f=5:GOSUB 6
3 f=k+7:GOSUB 6:f=k+11:GOSUB 6:f=k+13:GOSUB 6:k=k+30:f=k-13:GOSUB 6
4 f=k-11:GOSUB 6:f=k-7:GOSUB 6:f=k-1:GOSUB 6:f=k+1:GOSUB 6:IF f<q THEN 3
5 PRINT "is prime";:GOTO 8
6 q=n/f:IF q<>INT(q) THEN RETURN
7 PRINT f;
8 PRINT TAB(29);:PRINT USING "(####.# s)";(timer-t0)/60:SLOW:END

READY.

Code : Tout sélectionner

RUN
? 1231            is prime                     (   0.2 s)
? 2007             3                           (   0.1 s)
? 71327           is prime                     (   0.8 s)
? 123679           337                         (   0.9 s)
? 1000003         is prime                     (   2.7 s)
? 2100151          29                          (   0.1 s)
? 10000019        is prime                     (   8.4 s)
? 998812807        31601                       (  83.0 s)
? 999999937       is prime                     (  83.2 s)

Modifié en dernier par C.Ret le 21 oct. 2017 10:05, modifié 4 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez rapide, accélérez n°1

Message par zpalm »

Sur HP 41CX (ou 41C/CV avec module time): on entre le nombre puis XEQ "MRA", à la fin le temps total est affiché, en appuyant sur <- on obtient soit le nombre s'il est premier, soit son premier diviseur.

Ce programme teste les diviseurs 2, 3 et 5 puis passe à 30n+7 avec n=0, puis il boucle sur les 8 diviseurs de la forme 30n+/-x. Le nombre n est dans le registre 00 et le diviseur courant dans le registre 01.

Les pas 2 à 14 servent à initialiser, démarrer puis arrêter le chrono et afficher le temps d"exécution.

Comme le but est d'aller le plus vite possible on ne cherche pas à économiser des pas de programme mais à réduire le nombre total d'instructions exécutées. Pour cela il faut proscrire les appels aux sous programmes et ne pas hésiter à dupliquer des séquences de code similaires.

Dans ma première version je testais si le diviseur était supérieur à racine(n) pour chaque diviseur, mais en fait pour optimiser le temps d'exécution il suffit de le faire tous les 8 diviseurs (1 fois par boucle). J'ai ainsi gagné 27% de temps d'exécution, très utile sur les grands nombres, au détriment d'un peu de temps perdu sur quelques petits nombres premiers.

Code : Tout sélectionner

01   LBL"MRA     20   FRC         39   LBL 00      58   X=0?        77   ST+ 01      96   /
02   0           21   X=0?        40   6           59   GTO 01      78   RCL 00      97   FRC
03   SETSW       22   GTO 01      41   ST+ 01      60   2           79   RCL 01      98   X=0?
04   RDN         23   RCL 00      42   RCL 01      61   ST+ 01      80   /           99   GTO 01
05   RUNSW       24   3           43   x^2         62   RCL 00      81   FRC        100   2
06   XEQ 02      25   STO 01      44   RCL 00      63   RCL 01      82   X=0?       101   ST+ 01
07   STOPSW      26   /           45   X<Y?        64   /           83   GTO 01     102   RCL 00
08   RCLSW       27   FRC         46   RTN         65   FRC         84   4          103   RCL 01
09   FIX 6       28   X=0?        47   LASTx       66   X=0?        85   ST+ 01     104   /
10   CLA         29   GTO 01      48   /           67   GTO 01      86   RCL 00     105   FRC
11   ATIME24     30   RCL 00      49   FRC         68   4           87   RCL 01     106   X=0?
12   AVIEW       31   5           50   X=0?        69   ST+ 01      88   /          107   GTO 01
13   RDN         32   STO 01      51   GTO 01      70   RCL 00      89   FRC        108   GTO 00
14   RTN         33   /           52   4           71   RCL 01      90   X=0?       109   LBL 01
15   LBL 02      34   FRC         53   ST+ 01      72   /           91   GTO 01     110   RCL 01
16   STO 00      35   X=0?        54   RCL 00      73   FRC         92   6          111   RTN
17   2           36   GTO 01      55   RCL 01      74   X=0?        93   ST+ 01         
18   STO 01      37   1           56   /           75   GTO 01      94   RCL 00         
19   /           38   STO 01      57   FRC         76   2           95   RCL 01         


  nombre     temps    diviseur
    1231      3"58        1231   ->premier
    2007      0"90           3
   71327     21"33       71327   ->premier
  123679     26"27         337
 1000003   1'17"80     1000003   ->premier
 2100151      2"85          29
 8043509   3'13"64        2543
10000019   4'02"71    10000019   ->premier
31629593   7'10"40    31629594   ->premier
Bon, après tous ces tests il va falloir que j'aille acheter des piles pour ma 41CX, l'indicateur BAT est affiché en permanence ...

Si on supprime les pas 1 à 14, ce programme doit pouvoir s'exécuter tel que sur toute HP RPN disposant d'une centaine de pas de programme.
Je viens de le tester sur ma 29E (rev 1.03) qui chronométrée manuellement est à peine moins rapide que ma 41CX (j'adore voir les LEDs rouges clignoter dans tous les sens pendant l'exécution d'un programme):

Code : Tout sélectionner

  nombre      41CX       29E
   71327     21"33      24"8
  123679     26"27      29"9
 1000003   1'17"80    1'28"5
 8043509   3'13"64    3'41"9
10000019   4'02"71    4'36"7
31629593   7'10"40    8'11"0
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: Misez rapide, accélérez n°1

Message par gege »

Bonjour,
Tiens après portage du programme Graph 85 sur PB-700, les temps sont très similaires à ceux de la HP41 !!

Code : Tout sélectionner

  71327   21
 123679   27
1000003   79 (1'19")
8043509  194 (3'14")
Ce n'est pas flatteur pour le pauvre PB-700 qui n'avait déjà bas très bonne réputation...
G.E.

EDIT : le programme...

Code : Tout sélectionner

100 CLEAR:DIM F(60)
110 INPUT N:D=1:L=1:P=0:GOSUB 150:GOSUB 150:L=2:GOSUB 150
120 IF N>D*D THEN GOSUB 150:L=6-L:GOTO 120
130 IF N>1 THEN P=P+1:F(P)=N
140 FOR L=1 TO P:PRINT F(L);:NEXT L:END
150 D=D+L
160 IF N=D*INT(N/D) THEN N=N/D:P=P+1:F(P)=D:PRINT D:GOTO 160
170 RETURN
Modifié en dernier par gege le 30 août 2015 09:53, modifié 3 fois.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez rapide, accélérez n°1

Message par zpalm »

Il serait intéressant de voir ce que ça donne sur fx-602p.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez rapide, accélérez n°1

Message par C.Ret »

Code : Tout sélectionner

              zpalm     zpalm     C.Ret      gégé
            HP-41CX    HP-29E     C128D    PB-700
     1231                            "1
     2007                            "1
    71327     21"33      24"8        "8       27"
   123679     26"27      29"9        "9    
  1000003   1'17"80    1'28"5       2"7     1'19"
  2100151                            "1
  8043509   3'13"64    3'41"9               3'14"
 10000019   4'02"71    4'36"7       8"4
 31629593   7'10"40    8'11"0     
998812807                        1'23"0
999999937                        1'23"2
Je n'ai pas on HP-41C Sous la main pour chromométrer, mais j'aurais bien proposer pour faire court et rapide:

Code : Tout sélectionner

001 LBL "MRA   RCl X  2  XEQ 03  3  XEQ 03  5  XEQ 03
009 LBL 00     RCL X  2  XEQ 02  4  XEQ 02  2  XEQ 02  4  XEQ 02  2  XEQ 02  4  XEQ 02  6  XEQ 02  6  XEQ 02
027            Lastx  x^2  x<>y  x>y? GTO 00
032            NEG  NEG  GTO 09
035 LBL 02     LastX  +
038 LBL 03     MOD  x=0?  GTO 09
042            RDN  RCL X  RTN
045 LBL 09     LastX END
Modifié en dernier par C.Ret le 21 oct. 2017 10:16, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez rapide, accélérez n°1

Message par zpalm »

@C.Ret: sur ma 41CX ton programme s'exécute en 1'20"44 pour 1000003, soit presque 3" de plus que le mien, par contre il retourne 1025. A quoi ça correspond ?

EDIT: il y a deux problèmes dans ce programme :
  • il faut remplacer les deux NEG par STO L pour avoir la bonne valeur lorsque le nombre est premier.
  • lorsque le nombre n'est pas premier le programme ne s'arrête pas à la fin du LBL 09 comme il faudrait mais revient et continue après le XEQ 02 ou 03 précédent...
alain1261
Fonctionne à 75 bauds
Fonctionne à 75 bauds
Messages : 21
Enregistré le : 11 juil. 2015 00:28

Re: Misez rapide, accélérez n°1

Message par alain1261 »

Bonjour à tous, merci pour ce nouveau défi.

Justement, je testais dernièrement la vitesse de différentes (vieilles) machines pour déterminer si un nombre est premier.

Je me suis inspiré du test sur le blog http://chipotman.blogspot.fr/ pour tester mes machines.

J'ai été étonné par la célérité du petit Casio PB-100 avec son écran tout riquiqui. 8O

L'algorithme est plus simple que celui proposé ici, mais sur ce pocket, il semble rapide.

Code : Tout sélectionner

10 INPUT"A",A
20 B=INT (SQR(A)):C=2
30 IF FRAC(A/2)=0 THEN 80
40 FOR C=3 TO B STEP 2
50 IF FRAC(A/C)=0 THEN 80
60 NEXT C
70 PRINT"1":GOTO 10
80 PRINT C:GOTO 10
test 2003 : 1"
test 4093 : 1+"
test 71327 : 5"
test 123679 : 7" (337)

test 524287 : 15"
test 1000003 : 20"
test 3263443 : 40"

(mesures au chrono manuel)

Pour comparer, mon FX-702p donne un résultat en 42s sur le test de 524287 avec le même algorithme soit presque 3 fois plus lent que le PB-100.
De mes machines de la même époque, seul le Canon X-07 est (un peu) plus rapide que le PB-100 (en Basic) sur ce test.

Sur le PB-100, il semble que la boucle FOR soit nettement plus rapide qu'une autre solution à base de IF et GOTO pour boucler, du coup l'algorithme en début de fil risque d'être plus lent sur le PB-100.

Du coup, le PB-100 a eu droit à un jeu de CR2032 neuves, parce qu'il le vaut bien... :D
Mon parcours : TI30 -> F-73 -> PC1261 -> PC1475 -> TI92 -> Voyage 200
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez rapide, accélérez n°1

Message par C.Ret »

zpalm a écrit : il y a deux problèmes dans ce programme :
Je suis content de voir qu'il n'y en a pas plus, car je n'avais de machine sous la main.

Je rentre seulement chez moi, et je me penche sur ces deux problèmes. Qui en fait n'en sont pas.

L'idée des deux NEG tait d'afficher l'opposé du nombre lorsuqe celui-ci est premier. un peu comme dans le sous-programme B de l'article donnée en référence.

Mais l'idée d'afficher le nombre lui-même me conviens parfaitement.

Seul souci est que l'HP-41 ne s'arrête pas à l'instruction END, mais fait un RTN. Il manque donc un R/S (pardon un STOP !)

Autre souci, et de taille, est que la s"quence n'est pas correcte -: -> IL MANQUE UN 2 ENTRE LES DEUX 6 <<-- :twisted:
et l'ajout de 2 pour passer de 5 à 7 ne doit pas être dans la boucle

Voilà le code corrigé et testé :

Code : Tout sélectionner

001 LBL "MRA   RCl X  2  XEQ 03  3  XEQ 03  5  XEQ 03  7  XEQ 03
011 LBL 00     RCL X  4  XEQ 02  2  XEQ 02  4  XEQ 02  2  XEQ 02  4  XEQ 02  6  XEQ 02  2  XEQ 02  6  XEQ 02
029            Lastx  x^2  x<>y  x>y? GTO 00
034            STO L
035 LBL 01     LastX  TONE 1  STOP
039 LBL 02     LastX  +
042 LBL 03     MOD  x=0? GTO 01
046            RDN  RCL X  RTN
J'ai ajouté un BEEP pour faciliter le chronométrage.

C'est clair que ce code, bien que plus court, est bien plus lent !

Est-ce la fonction MOD ou le grand nombre d'appels XEQ 02 ? :?:
Modifié en dernier par C.Ret le 21 oct. 2017 10:25, modifié 4 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 434
Enregistré le : 05 juin 2014 22:23
Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau

Re: Misez rapide, accélérez n°1

Message par caloubugs »

Bon, pour la TI95, en cherchant l'optimisation de zpalm (qui limite le contrôle sur sqr(n) une seule fois par cycle principal, ça gagne 15% en gros !) et en faisant un maximum d'adressages directs sur les numéros de ligne (pas de label) :

Code : Tout sélectionner

000 CMS STO 000 SQR STO 001 2 SBR 068 
012 1 SBR 068 2 SBR 068 2 GTO 0045
024 4 SBR 068 2 SBR 068 4 SBR 068
036 6 SBR 068 2 SBR 068 6 SBR 068
048 4 SBR 068 2 SBR 068 RCL 002 IF> 001
062 GTO 0089 GTO 0024 ST+ 002 
071 RCL 000 / RCL 002 = STO 003 FRC
083 IF= T GTO 0102 RTN RCL 000 'Prime' 
097 COL 16 MRG = HLT RCL 000 / 
106 RCL 003 = 'Div' COL 16 MRG = HLT
Voici quelques temps et j'ai calculé le ratio sqr(n)/temps qui normalement doit converger...
1231 (premier) - 1"5 - r=23.4
71327 (premier) - 7" - r=38.2
123679 (337) - 8" - r=42.1 (je divise 337 par 8).
1000003 (premier) - 23" - r=43.5
10000019 (premier) - 1'11" - r=44.5
31629593 (premier) - 2'06" - r=44.6
999999937 (premier) - 11'45" - r=44.9

J'ai constaté un petit temps de latence pour le démarrage d'environ 1/2 seconde au démarrage du programme, ce qui explique aussi l'amélioration progressive de la performance.
C'est quand même pas une bête de course... Je vais faire le test pour la TI74 qui normalement va un peu plus vite.
Modifié en dernier par caloubugs le 30 août 2015 09:40, modifié 2 fois.
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
alain1261
Fonctionne à 75 bauds
Fonctionne à 75 bauds
Messages : 21
Enregistré le : 11 juil. 2015 00:28

Re: Misez rapide, accélérez n°1

Message par alain1261 »

Programme pour Casio PB-100 avec l'algorithme proposé.

Codage pas très élégant mais facile à écrire et comprendre:

Code : Tout sélectionner

10 INPUT"A",A
20 B=INT (SQR(A)/30)
30 C=2:IF FRAC(A/C)=0 THEN 210
40 C=3:IF FRAC(A/C)=0 THEN 210
50 C=5:IF FRAC(A/C)=0 THEN 210 
60 C=7:IF FRAC(A/C)=0 THEN 210 
70 C=11:IF FRAC(A/C)=0 THEN 210 
80 C=13:IF FRAC(A/C)=0 THEN 210 
90 FOR D=1 TO B
100 E=30*D
110 C=E-13:IF FRAC(A/C)=0 THEN 210 
120 C=E-11:IF FRAC(A/C)=0 THEN 210 
130 C=E-7:IF FRAC(A/C)=0 THEN 210 
140 C=E-1:IF FRAC(A/C)=0 THEN 210 
150 C=E+1:IF FRAC(A/C)=0 THEN 210 
160 C=E+7:IF FRAC(A/C)=0 THEN 210 
170 C=E+11:IF FRAC(A/C)=0 THEN 210 
180 C=E+13:IF FRAC(A/C)=0 THEN 210 
190 NEXT D
200 PRINT A:GOTO 10
210 PRINT C:GOTO 10
Astuce pour la saisie: Pour entrer la ligne 40, faire un LIST 30 et changer 30 en 40 et 2 en 3, faire pareil pour les lignes suivantes. Le même principe s'applique pour les lignes 110 à 180. :idea:

test 71327 : 3"
test 123679 : 5" (337)
test 524287 : 10"
test 1000003 : 14"
test 3263443 : 24"

:arrow: On constate un gain d'environ 40% en temps de calcul par rapport à l'algorithme simplifié précédent qui testait tous les nombres impaires >=3.

Je vais essayer avec un GOSUB pour voir si on ne perd pas trop. :?:
Mon parcours : TI30 -> F-73 -> PC1261 -> PC1475 -> TI92 -> Voyage 200
alain1261
Fonctionne à 75 bauds
Fonctionne à 75 bauds
Messages : 21
Enregistré le : 11 juil. 2015 00:28

Re: Misez rapide, accélérez n°1

Message par alain1261 »

Sans surprise, en utilisant GOSUB, c'est deux fois plus lent. :(
On pert donc l'avantage de l'algorithme optimisé à cause de la lenteur du GOSUB ! :?

Code : Tout sélectionner

10 INPUT"A",A
20 B=INT (SQR(A)/30)
30 C=2: GOSUB 220 
40 C=3: GOSUB 220 
50 C=5: GOSUB 220 
60 C=7: GOSUB 220 
70 C=11: GOSUB 220 
80 C=13: GOSUB 220 
90 FOR D=1 TO B
100 E=30*D
110 C=E-13: GOSUB 220 
120 C=E-11: GOSUB 220 
130 C=E-7: GOSUB 220 
140 C=E-1: GOSUB 220 
150 C=E+1: GOSUB 220 
160 C=E+7: GOSUB 220 
170 C=E+11: GOSUB 220 
180 C=E+13: GOSUB 220 
190 NEXT D
200 PRINT A:GOTO 10
210 PRINT C:GOTO 10
220 IF FRAC(A/C)=0 THEN 210 
230 RETURN 

test 123679 : 10 sec (337)
test 524287 : 20 sec
test 1000003 : 28 sec
Mon parcours : TI30 -> F-73 -> PC1261 -> PC1475 -> TI92 -> Voyage 200
Répondre

Retourner vers « Tous les Pockets »