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.
A faire comme Jürgen Keller
Modérateur : Politburo
- Marge
- Fonctionne à 14400 bauds
- Messages : 6192
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: A faire comme Jürgen Keller
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é. ♥ ♠
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é. ♥ ♠
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: A faire comme Jürgen Keller
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.
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.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: A faire comme Jürgen Keller
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...
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.
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2936
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: A faire comme Jürgen Keller
Vers la fin:
Source: hpmuseumProgramming 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.
J'ai hâte de voir le résultat
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: A faire comme Jürgen Keller
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
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
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 ║│
╙┘
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.
- Marge
- Fonctionne à 14400 bauds
- Messages : 6192
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: A faire comme Jürgen Keller
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 !!! ), mais j'espère avoir fini ce jouet aujourd'hui pour me consacrer demain pleinement à ce défi. Taïaut !
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 !!! ), 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é. ♥ ♠
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é. ♥ ♠
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: A faire comme Jürgen Keller
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 )
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.
- Marge
- Fonctionne à 14400 bauds
- Messages : 6192
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: A faire comme Jürgen Keller
Ça m'arrangerait en effet, et d'autres aussi peut-être...
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é. ♥ ♠
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é. ♥ ♠
- Marge
- Fonctionne à 14400 bauds
- Messages : 6192
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: A faire comme Jürgen Keller
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...
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é. ♥ ♠
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é. ♥ ♠
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: A faire comme Jürgen Keller
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 :
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é !
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 :
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.
- Marge
- Fonctionne à 14400 bauds
- Messages : 6192
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: A faire comme Jürgen Keller
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 !
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é. ♥ ♠
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é. ♥ ♠
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: A faire comme Jürgen Keller
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. 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 !
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. 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.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: A faire comme Jürgen Keller
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).
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 :
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 :
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 :
Dont voici le listing pour SHARP PC 1360 et consœurs :
Mon SHARP PC-1360 vient de mettre 45 min pour afficher (je n'ai pas d'imprimante) les 1229 nombres.
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
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
Sur mon (véloce) Commodore, le record actuel est de moins de 6 min avec un code plus complexe :
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))
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.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: A faire comme Jürgen Keller
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 :
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 :
(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é.
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
-------+-------+-------+ +-------+-------+-------+-------+-------+-------+-------+-------+-------+
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
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.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: A faire comme Jürgen Keller
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 ?
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.