A faire comme Jürgen Keller

Les derniers trucs auxquels vous avez joué, les derniers ordinateurs que vous avez bidouillés.

Modérateur : Politburo

Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6167
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: A faire comme Jürgen Keller

Message par Marge »

zpalm a écrit : 01 mars 2018 20:26 Sur 29C/19C la partition mémoire programme / registres est fixe: 98 pas de programme et 30 registres dont 14 accessibles uniquement de manière indirecte.
En effet, j'avais oublié que ce sont 30 registres au total. Comme l'accès est indirect, pour notre problème il faut en décompter un, le registre 0 qui permet justement l'adressage indirect. Après, il est possible de jongler (en utilisant par exemple un registre pour deux informations différentes), mais souvent le fait d'exploiter ces infos possède un coût en mémoire programme exorbitant.
3 hommes, 3 demis, un 3a... Magnéto, Serge !

Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67
__: A L I E N .

« Boris », c'était juste Maurice enrhumé.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Jürgen Keller

Message par C.Ret »

OK merci pour ces informations, je peux maintenant me lancer.

Avec 30 registres et presque 100 pas de programme, il y a de quoi faire.
Il faut juste que je démonte un de mes programmes pour HP-15C dans lequel j'utilise des drapeaux et des instruction RCL+ ou RLC/.
Je vais garder leur architecture mais refaire certains tronçons pour n'utiliser que des fonctions disponiblessur l'HP-19C.
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
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Jürgen Keller

Message par C.Ret »

Marge a écrit : 01 mars 2018 21:10 [...], mais souvent le fait d'exploiter ces infos possède un coût en mémoire programme exorbitant.
Effectivement, mais ici nous avons la chance que le pointeur en question peut rester en permanence (ou presque) dans le registre 0:

En tout cas le développement avance bien de mon coté, les intempéries m'ayant contraint à annuler quelques déplacements. Une solution semble se dégager (à l'inverse du ciel) qui a les avantages suivants:
  • Paramétrique: les nombres premiers sont recherchés jusqu'à m donné en argument
  • Autodidacte: au fur et à mesure de leur découverte, les facteurs premiers sont mémorisés pour servir aux futurs tests,
  • Raisonnable: pour ne pas dépasser la limite des 24/25 registres disponible cette mémorisation s'interrompt définitivement lorsqu'on atteint √m.
  • Efficiente: Une fois interrompue, le test évitant la mémorisation doit être simple et rapide, éviter tout calcul car il sera effectué plus de 1200 fois. Comme il n'y a pas de drapeaux sur les HP-2x, j'utilise un test de signe.
  • Parcimonieuse: Tous les entiers ne sont pas testés, bien au contraire, seuls ceux ayant une chance d'être premier. Pour l'instant seuls les nombres pairs et les multiples de trois sont évités avec l'astuce des pas alternatifs +2/+4.
  • Astucieuse: Le facteur 3 n'est mémorisé que le temps de découvrir que 5 est premier. Ce dernier facteur vient alors remplacer 3 en mémoire; ce qui était au début une maladresse d'adressage et devenu une astucieuse astuce.
  • Paresseuse: Le test de primalité par division sera répété 29986 fois autant dire qu'il doit tenir en un minimum d'instructions. (Notons qu'il est réalisé 57184 dans la version de Wilfred Astan ce qui fait une économie d'à peine 47.5%) Et surtout il faut un test simple et efficace pour se limiter au justes facteurs nécessaires pour ne pas dépasser √n et ne pas utiliser tous les facteurs mémorisés. En effet, la mémorisation va bien plus vite que la progression de la racine de n.
  • Economique: Le temps d'impression et la longueur de papier sont économisés en imprimant deux nombres premiers par ligne (voir aperçu d'impression ci-dessous). Mais si cela a un coût négligeable en terme de registre (cela ne nécessite qu'un registre mémoire supplémentaire qui sert de "tampon d'impression"), il n'en est pas de même en terme de complexité et nombre total d'instructions. Cela allonge un peu le code (environ 20 pas dans la dernière version en développement soit un allongement de 33.90%) et donc ralenti chaque instruction de saut GTO ou GSB.
  • Evolutive: N'étant pas persuadé que le double affichage ait un réel intérêt, voir ne soit pas une entrave à la performance globale, il est facile à partir de la version 'double impression' d'obtenir une version plus légère imprimant un nombre par ligne en remplaçant chaque GSB8 par PRX dans le début du code et en effaçant les 20 dernières instructions qui contiennent les trois sous-programmes de gestion de l'impression LBL7, LBL8 et LBL9
  • Perfective: Pour l'instant seul l'algorithme, la gestion des registres et l'impression semblent à peu près au point. Mais le code obtenu est encore loin d'être optimisé. Il y a encore bien trop de répétitions d'instruction ou de groupes d'instructions, l'ordre d'implémentation des sous-parties est maladroit. Il doit être possible de raccourcir tout cela en ordonnant mieux les sous-parties (ce qui rendra les sauts moins nombreux et plus rapides) et en évitant les répétitions inutiles d'instructions en utilisant mieux la pile de donnée...
100 GSB0
100 GSB0
autoprime v2.png (72.42 Kio) Vu 13326 fois
D'ailleurs, je n'ai pas trouvé l'information ; lors d'un saut vers un label (les sauts rapides utilisant i étant proscrits car i est déjà bien utilisé pour parcourir les facteurs mémorisés) dans quel sens l'HP-19C (ou HP-29C) parcours le code ? Vers la fin ou le début ?

C'est juste une petite question qui me permettra de mettre les sous-parties dans un ordre rationnel en fonction de la fréquence des différents sauts GTO ou GSB
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 : 2917
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: A faire comme Jürgen Keller

Message par zpalm »

C.Ret a écrit : 03 mars 2018 09:08 D'ailleurs, je n'ai pas trouvé l'information ; lors d'un saut vers un label [...] dans quel sens l'HP-19C (ou HP-29C) parcours le code ? Vers la fin ou le début ?
Vers la fin:
Programming Techniques
Addressing
The calculators use label addressing. Labels available are the digits 0 through 9. The calculator always searches downward through program memory from the current location. If there are multiple copies of a label it will execute the first one it finds. After it gets to the end of memory it resumes searching from the beginning.
Source: hpmuseum

J'ai hâte de voir le résultat :slime:
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Jürgen Keller

Message par C.Ret »

Merci, en plus j'utilise cette page comme référence. Il était tard hier soir, l'info m'avait échappée.

Pas de résultat avant dimanche. Je ne veux pas influencer les travaux de Marge ou des autres passionnés...

Je ne sais pas ce que cela donnera sur une vraie HP-19C, j'utilise mon HP-41C pour émuler une "classique". J'ai même dû créer un programme 'ISZ" pour mimer le comportement de la 19C car l'instruction ISG d'une HP41C n'utilise pas le compteur et ne fait pas les sauts comme l'ISZ

Ce qui d'ailleurs justifie pleinement que ces deux instructions aient des mnémoniques différents :)

En tout cas l'HP-19Cest pleine de ressource.
Manque peut-être un drapeau ou deux :(

EDIT: Il y a donc trois cas de figure :
.. rapides .. courts .. longs

Code : Tout sélectionner

01             01            01          ╓┐
..             ..            ..          ║│
..             ..            ..          ║│
40     ←────┐  40  GTO1 ───╖ 40 *LBL1 ←──╜│
..          │  ..          ║ ..           │
46    9     │  ..          ║ ..           │
47   CHS    │  ..          ║ ..           │
48  STO0    │  ..          ║ ..           │
49 GTO i ───┘  49 *LBL1 ←──╜ 49  GTO1 ───╖│
..             ..            ..          ║│
..             ..            ..          ║│
99             99            99          ║│
                                         ╙┘
L'optimisation étant, puisque les sauts rapides sont proscrits, de minimiser le nombre de sauts longs surtout aux endroits où l'on passera 29936 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
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6167
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: A faire comme Jürgen Keller

Message par Marge »

Bonjour,

Bravo C.Ret, ça a l'air bien parti. Attention à ton point 3 cependant : si tu dépasses les 29 registres en adressant au-delà avec l'index (R0), tu obtiendras une erreur et la bobinette cherra.

La recherche des libellés se fait vers l'avant, comme l'a signalé zpalm. Il y a une astuce (je pense inapplicable ici) qui permet à la 29/19C de revenir en arrière du nombre de pas indiqués dans le registre 0 si ce dernier est négatif, si ma mémoire est bonne - il me semble que c'est illustré dans ton dernier schéma, première colonne.

J'ai commencé à réfléchir. Je vais être bien pris ce week-end pour cause de jouet à confectionner pour mon petiot pour l'école (une console Super Mario en carton !!! 8O ), mais j'espère avoir fini ce jouet aujourd'hui pour me consacrer demain pleinement à ce défi. Taïaut !
3 hommes, 3 demis, un 3a... Magnéto, Serge !

Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67
__: A L I E N .

« Boris », c'était juste Maurice enrhumé.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Jürgen Keller

Message par C.Ret »

Je serai moi aussi assez pris demain.

Nous pourrions peaufiner tout cela dans le mois à venir et ne rien publier avant encore une bonne semaine afin de laisser monter la tension et laisser le temps à d'autres d'entrer dans la valse !

P.S.:
Concernant le point 3. Je me rends compte que tel qu'il fonctionne actuellement, le code utilise effectivement les registres de 6: à 29: pour mémoriser les facteur de 5 à 101.
Donc effectivement, un faux pas et la bobinette chèrera effectivement. Ce qui serait d'autant plus regrettable que cela n'adviendrait que dans les dernières minutes de la course (ou si l'on a de la chance, au début lors que la mémorisation délictueuse d'un 25ième facteur )
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
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6167
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: A faire comme Jürgen Keller

Message par Marge »

C.Ret a écrit : 03 mars 2018 13:34 Je serai moi aussi assez pris demain.

Nous pourrions peaufiner tout cela dans le mois à venir et ne rien publier avant encore une bonne semaine afin de laisser monter la tension et laisser le temps à d'autres d'entrer dans la valse !
Ça m'arrangerait en effet, et d'autres aussi peut-être... :D
3 hommes, 3 demis, un 3a... Magnéto, Serge !

Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67
__: A L I E N .

« Boris », c'était juste Maurice enrhumé.
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6167
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: A faire comme Jürgen Keller

Message par Marge »

Bonjour,

J'avance lentement. Pour obtenir quelque chose de comparable au programme de C.Ret, j'essaie de suivre point par point ses caractéristiques, ce qui n'est pas toujours facile - j'ai du mal à transformer mes erreurs en astuces astucieuses. ;)

Sinon, j'ai les noms de ceux qui pourraient nous rejoindre ! Allez, les gars, ne me laissez pas seul avec mon pôv' programme ! Vous avez une HP-19C (ledudu, hobiecat), voire une HP-29E (zpalm), c'est le moment de montrer ce que vos bécanes ont dans le ventre !

P.-S. : ledudu, à propos d'HP-19C, j'ai quelque chose pour toi... ;)
3 hommes, 3 demis, un 3a... Magnéto, Serge !

Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67
__: A L I E N .

« Boris », c'était juste Maurice enrhumé.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Jürgen Keller

Message par C.Ret »

Bon, j'ai moi aussi un peu avancé.

En particulier, les sous-parties s'enchaînent mieux, il n'y a plus que 6 GTO et 3 GSB au lieu des 9 GTo et 3 GSB dans premier prototypes !


Pour donner une idée de ce à quoi cela ressemble, et sans dévoiler trop le code , voici un petit schéma :
AutoPrimes HP19C - 75 Steps - 30 Register
AutoPrimes HP19C - 75 Steps - 30 Register
AutoPrimes_HP19C.png (112.17 Kio) Vu 13227 fois
P.S.: Un point a disparu; l'astuce du facteur 5 remplaçant le facteur 3 car ce dernier facteur n'est plus mémorisé !
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
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6167
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: A faire comme Jürgen Keller

Message par Marge »

Joli, l'organigramme ! - vu sur téléphone, autant dire : pas détaillé.

Il reflète bien la difficulté de la conception ; pour être franc, je rame beaucoup. Je souhaite néanmoins obtenir un résultat (j'avais cette idée d'utiliser ces registres précis depuis longtemps), mais je dois reconnaître que j'aurai du mal à obtenir quelque chose de solide pour dimanche...

Si c'est le cas, je publierai un résultat après la sortie de la G11, car j'y ai un article à vraiment bichonner. Mais que cela ne t'empêche pas d'en dire plus ni de publier ton programme !
3 hommes, 3 demis, un 3a... Magnéto, Serge !

Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67
__: A L I E N .

« Boris », c'était juste Maurice enrhumé.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Jürgen Keller

Message par C.Ret »

Je suis en train de profiler mon code, c'est à dire de compter le nombre d'occurrence de chaque instruction et d'en déduire l'importance des sauts et des répétitions.

C'est un sacré challenge, imprimer tous le nombres premiers inférieurs à 10'000 est un défi de taille. Non seulement toute la mémoire (ou presque) est utilisée, mais en plus, le cœur du code va devoir fonctionner plusieurs dizaines de milliers de fois.

En effet, si les parties "Initialisation" (LBL0), "End print" (LBL7) et la négation de la racine √m mémorisé dans r ne sont effectuées qu'une seule fois
,et,
si l'incrément de p et la mémorisation des facteurs premiers F() ne seront répétés que 24 fois, les occurrences des autres parties du code donnent le vertige.

Le l'incrémentation de n (LBL1) sera répété 3331 fois; en effet parcourir les entiers de 5 à 10'000 par pas alternatifs d de +2 ou +4 revient à avancer en moyenne de trois entiers à chaque tour.

Mais le plus terrible est le taux de bouclage dans le test (LBL2), en réalité 29'986 quotients q=n/F(i) seront calculés et donc autant de tests pour la multiplicité - MOD, en réalité la fonction FRC sur une HP19C - et le dépassement de √n. Ces deux tests déclencheront respectivement 2'104 retours au LBL1 lors de nombre multiples (c'est à dire lors des quelques nombre composés que ne sait éviter la méthode +2/+4) et 1'227 retours vers le LBL3 lors de la détection des nombres premiers.
Quand à elle, l'instruction d'incrémentation de i (ISZ) sera répétée 26'655 fois !

Enfin le sous-programme LBL8 de préparation de l'impression sera appelé 1'230 fois. Une fois sur deux l'effet se limitera à mémoriser n dans le registre a "tampon d'impression", et donc également une fois sur deux il déclenchera l'impression des 615 duo de nombres premiers.

Pour bien mémoriser cela, je reproduit ci-dessous l'organigramme général en indiquant l'occurance de chaque étape par l'épaisseur des traits.
AutoPrime HP19C: épaisseur = LOG(répétitions)
AutoPrime HP19C: épaisseur = LOG(répétitions)
AutoPrimes_HP19Ce.png (63.68 Kio) Vu 13190 fois
Attention, l'échelle d'épaisseur est logarithmique, un trait deux fois plus épais signifie une occurrence plus de 10x supérieure !



On comprend alors pourquoi il faut 15h et 5.28 m de papier pour arriver à bout de ce challenge !

Et aussi pourquoi quelques propriétaires d'HP19C ou HP29C fragilisées par des années de service hésitent à ce lancer dans une telle aventure !
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
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Jürgen Keller

Message par C.Ret »

A titre de comparaison, voici l'organigramme correspondant au code utilisé par Jürgen KELLER, c'est à dire le code publié par Wilfred ASLAN dans le mensuel BYTE d'octobre 1980 (Volume 5, Numéro 10, p. 54).
Wilfred ASLAN HP-19C code chartflow
Wilfred ASLAN HP-19C code chartflow
2018-03-17.png (26.46 Kio) Vu 13076 fois
Présenté ainsi, on se rend compte que le code est très proche de l'organigramme et il est assez facile d'observer comment l'algorithme est implémenté dans le code de l' HP-19C.

On remarquera aussi que l'opération d'initialisation du facteur ( F <-- 1 c'est à dire 1 STO1) est répétée trois fois alors qu'il aurait suffit de faire figurer cette opération quelque part dans la sous-partie LBL1 pour économiser quelques pas et un peu de temps.

Cet organigramme fait ressembler celui de mon code à une véritable usine à gaz !
Cela est surtout dû au fait qu'il n'y a pas ici les trois sous-routine pour l'affichage DUAL des nombres, ni la partie nécessaire à la mémorisation (et à son arrêt ) des premiers facteurs premiers dans les registres de la machine.


En tout cas, c'est un algorithme plus rapide, mais aussi plus compliqué, que le code initial proposé par Jmes R lewis dans la revue BYTE de mars 1980 (Volume 5 Numéro 03 p.84). Dans cet article, il s'agit d'un code en BASIc assez surprenant, mais très simple; retranscript pour mon CommodoreC128D cela donne quelque chose comme :

Code : Tout sélectionner

10 PRINT 1,2,3,
20 FOR M=5 TO 1E4 STEP 2
30 FOR K=3 TO M/2 STEP 2
40 IF INT(M/K)*K=M THEN GOTO 70
50 NEXT K
60 PRINT M,
70 NEXT M
Et oui, vous ne rêvez pas, la boucle de test se prolonge jusqu'à M/2 !
L'auteur indique que son (pauvre) TRS-80 met entre 6 et 8h pour afficher les 1230 nombres premiers jusqu'à 10'000 !

Avec le même algorithme, mon (brave) Commodore ne mets que 2h30min.

Alors qu'il suffit d'un tout petit détail pour obtenir la même liste de nombre en moins de 9 min :

Code : Tout sélectionner

1 PRINT1,2,3,:FORN=5TO1E4STEP2:FORK=3TOSQR(N)STEP2:IFN/K-INT(N/K)THENNEXTK:PRINTN,:ELSENEXTN:PRINT:END
Et le petit détail ne provient pas du fait que ce soit un ONE-LINER, en utilisant M/2, il faudra ici aussi plus de 2h pour finaliser le listing !

Sur mon (véloce) Commodore, le record actuel est de moins de 6 min avec un code plus complexe :

SHARP PC-1360  chart flow for AutoPrime
SHARP PC-1360 chart flow for AutoPrime
2018-03-18.png (40.12 Kio) Vu 13069 fois

Dont voici le listing pour SHARP PC 1360 et consœurs :

Code : Tout sélectionner

1:CLEAR : DIM F(29) : INPUT "Max ";M : R=√M , N=5 , D=2 , P=0 : WAIT 0 : PRINT 2;3;
2:PRINT N; : IF R LET P=1+P , F(P)=N : IF N>R LET R=0
3:N=N+D , D=6-D , I=0 : IF N>M BEEP 1 : END
4:I=I+1 , Q=N/F(I) : GOTO 3+(Q<> INT Q)* SGN (Q-F(I)) 
Mon SHARP PC-1360 vient de mettre 45 min pour afficher (je n'ai pas d'imprimante) les 1229 nombres.
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
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Jürgen Keller

Message par C.Ret »

En relisant mon dernier post, je me rends compte que je n'ai pas donné le tableau résumé statistique:

Je l'ai construit à partir d'un même programme paramètré de façon à compter et évaluer l'éfficacité des différentes options utilisées dans les programme BASIC initiaux, les versions anciennes et actuelles. Mon idée est d'évaluer les gains potentiels et leur importance relative :

Code : Tout sélectionner

   Méthodes :                    Statistiques 	       
Inc.N      Inc.F  Lim.F      Temps    Nb.n Nb.prim Nb.Comp Nb.Test  Prim'T      %      n/s  test/s
-------+-------+-------+  +-------+-------+-------+-------+-------+-------+-------+-------+-------+
n+2         f+2     n/2       6h49    4998    1227    3771 1451624 1447853    99.7     0.2    59.2    
n+2         f+2   SQR n       0h16    4998    1227    3771   56569   52798    93.3     5.2    58.9
n+2        F(i)   F()>Q       0h12    4998    1227    3771   34983   31212    89.2     6.9    48.6
n+2        F(i)   nb.x²       0h12    4998    1227    3771   34982   31211    89.2     6.9    48.6
n+2/+4      f+2     n/2       6h19    3332    1227    2105 1446628 1444523    99.9     0.1    63.6  
n+2/+4      f+2   SQR n       0h13    3332    1227    2105   54903   52798    96.2     4.3    70.4
n+2/+4     F(i)   F()>Q       0h11    3331    1227    2105   29986   27881    93.0     5.0    45.4
n+2/+4     F(i)   nb.x²       0h10    3331    1227    2105   29986   27881    93.0     5.5    50.0
-------+-------+-------+  +-------+-------+-------+-------+-------+-------+-------+-------+-------+
L'idée maitresse était de mesurer l'avantage de la méthode +2/+4 par rapport aux tests utilisant tous les impairs afin de voir s'il était intéressant d'utiliser d'autres méthodes de parcours des entiers pseudo-prime.

Par exemple en utilisant les séquences +4/+2/+4/+2/+4/+6/+2/+6 ou
+2/+4/+2/+4/+6/+2/+6/+4/+2/+4/+6/+6/+2/+6/+4/+2/+6/+4/+6/+8/+4/+2/+4/+2/+4/+8/+6/+4/+6/+2/+4/+6/+2/+6/+6/+4/+2/+4/+6/+2/+6/+4/+2/+4/+2/+10/+2/+10 qui permettent d'éliminer les nombres multiples de 5 et 7 de la liste des nombres testés et corolairement ces deux facteur de la liste à mémoriser.

Je me rends compte en fait que le gain de temps n'est pas fameux. Qu'utiliser +2/+4 permet en moyenne d'avancer de 3 par 3 (diminuant ainsi la quantité de nombre à tester que de 2/3 par rapport à la liste limité aux nombres entiers impairs) et que les autres séquences n'avance que de 2/3.75 ou 2/4.375 de et dont ne résout en rien le principal défaut de cette méthode: il faut faire des dizaines de milliers de divisions.

En effet, quoi qu'il arrive, le principe du test par division nécessite de tester TOUS les facteurs premiers au moins jusqu'à la racine. ce qui ralenti fortement le processus et explique les 29'986 test de divisibilité qui restent un invariant de cette méthode. Et donc chercher à diminuer la quantité de nombre composés testés ne réduit pas énormément le temps du programme, car la plupart des nombres composés sont détectés très vite (c'est à dire avec les plus petits facteurs) et par contre déniché les 1227 nombre premier entraine inévitablement les nombreuses divisions...


La méthode n'est donc pas la bonne !!


Alors que le Crible d'Ératosthène est si simple et que trouver tous les nombres composés se fait à moindre effort !

En effet :

Si 2 est premier, alors 4, 6, 8,10, ... , 9996, 9998, 10'000 ne le sont pas
Si 3 est premier, alors 9,12,15,..., 9994, 9997, 10'000 sont composés (multiples de 3 en fait)
Si 5 est premier, alors 25,30,35, ..., 9990, 9995, 10'000 sont composés
...
Si p est premier, alors tous les n = p² + k*p ( avec k>0 ) ne le sont pas


D'où d'ailleurs le code basé sur ce principe simple :

Code : Tout sélectionner

10 M%=10000 : R%=101 : DIM P%(M%)
20 FOR N=2 TO M%  
30 :  IF P%(N)=0 THEN PRINT N; : IF N<R% THEN FOR I=N*N TO M% STEP N : P%(I)=N : NEXT I
40 NEXT N : PRINT : END
(Avec cet algorithme, même mon C128D met moins de 2min15s pour imprimer les 1229 nombres premiers inférieurs à 10'000

Algorithme qu'il nous reste à optimiser un peu et à simplement adapter à l' HP-29C et ses 29 registres indexés par R0.


P.S.:

L'HP-29C a été conçue en 1977 c'est à dire qu'elle est contemporaine (voir même un peu postérieure) à l'invention de l'évaluation paresseuse (LAZY EVALUATION). Et donc je tiens à rassurer les lecteurs de ce forum, elle possède bien tous les attributs nécessaires et suffisants pour exploiter comme mon Commodore C128D ce délicieux crible.
D'ailleurs on peut n'utiliser que 24 de ses registres indexés pour mener à bien cette mission et en bien moins d'heures qu'il ne le faut avec la recherche par test de divisibilité.
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
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Jürgen Keller

Message par C.Ret »

J'oubliais un indice de taille, l' HP-29C n'ayant que 29 registres indexés, il vous faudra pour réaliser un crible d'Eratosthène sur les 10'000 premiers entiers très certainement développer une stratégie d'évaluation paresseuse optimisée à l'aide une file de priorité qui, faute de place, sera très probablement basée sur un tas binaire.

J'avais oublié de préciser mon plan, c'est peut-être pour cela que personne n'a encore proposé ici un code pour cette mémorable et vénérable HP-29C ?
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.
Répondre

Retourner vers « A quoi t'as joué hier ? »