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
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
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 »

Voici le résultat de la recherche des nombres premiers jusqu'à 121 inclus selon deux algorithmes:

Les cases noires indiquent les nombres non testés.
Les cases blanches les nombres premiers trouvés.
Les cases avec une bordure sont les nombres candidats mais dont le test a échoué.
Le nombre indique d'ailleurs le facteur mis en évidence par le test !

Pour une machine peu rapide, bien choisir son algorithme doit donc théoriquement bien facilité les chose et donc accélérer la découverte des nombres premiers jusqu'à 10'000.


Ce qui m'inquiète un peu (beaucoup) est que le code que j'ai déduit dudit algorithme fait le double, en nombre de pas, que le programme de Wilfred ASLAN !
Suis-je plus rapide que lui ? Deux fois plus de choses à faire c'est beaucoup !
m121d7.png
m121d7.png (28.28 Kio) Vu 9918 fois
m121d5.png
m121d5.png (38.72 Kio) Vu 9919 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: A faire comme Jürgen Keller

Message par zpalm »

Je vois sur ta deuxième capture d'écran que tu as des nombres candidats qui se révèlent multiples de 5. Il doit être facile d'éviter de les tester et ainsi d'accélérer ton algorithme.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
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 »

Facile, facile,...

Oui sur une HP-15C ou une HP-41C c'est très facile.

Mais l'HP-29C ne dispose que de 99 pas et pas de ROLL UP

Prise de la tête manque mois de 12 pas :twisted:

EDIT:

Code : Tout sélectionner

 Etapes :   0  1 2  3              4        5           6   7     8        9 ...
Nombres : 2 3  5 7 11 13 17 19 23(25)29 31(35)37 41 43 47 (49)53(55)59 61(65) 
SunDaRAM:     25.                 35.      45.         49  55    63       75.        
                49.               49       49          55. 63.   65.      77.        
                  121.           121      121         121 121   121      121         

        ...        10       11    12   13             14              15   16   17 
          67 71 73(77)79 83(85)89(91) (95)97 101 103(105)107 109 113(115)(119)(121)
                   85.      91    95  105            115             119  121    >
                   91.      95.  105. 115.           119.            121    >    >
                  121      121   121  121            121               >.   >.   >.

Code : Tout sélectionner

 Etapes :     0 1 2                                 3           4        5      ...
Nombres : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47(49)53 59 61 67 71 73(77)79 83
SunDaRAM:      49.                                 63.         77.      91.       
                 121.                             121         121      121          


       ...    6              7           8    9 
          89(91)97 101 103 107 109 113(119)(121)
            105.           119.        121    >
            121            121           >.   >.
Evidemment, si l'on veut aller jusqu'à 10'000, il faut un peu organiser son SunDaRAM, par exemple en le disposant comme un tas. voici ce que contient la mémoire de l'HP-29C alors qu'elle vient d'imprimer le nombre premier 4999 :

Code : Tout sélectionner

R1:    5005.07
R2:    5005.13  5005.11
R4:    5015.17  5015.59  5025.67  5031.43
R8:    5035.19  5035.53  5017.29  5053.31  5063.61  5029.47  5037.23  5069.37  5043.41
R(16): 5041.71  5329.73  6241.79  6889.83  7921.89  9409.97 10000.
Cela parait mal ordonné, mais il n'en est rien. Ce faux "à peu près" économise bien les efforts de maintenance.
Et il suffit simplement de comparer le nombre n à tester (contenu dans la pile) avec le seul registre R1 pour savoir immédiatement s'il est premier ou non, s'il faut passer au nombre suivant ou faire évoluer son SunDaRAM et le tas binaire qui le contient !





P.S.: Désolé pas moyen d'insérer les deux images au bon endroit ou dans le bon sens ! Je voulais justement mettre celle sans les multiples de 5 après celle avec !!
:|
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 : 3404
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 quand même fini par y arriver. Mais il manque deux ou trois pas de programme pour que cela tienne complètement dans une HP-29C.

Peu importe, le lancement de l'impression des nombres premiers jusqu'à m nécessite d'initialiser quelques registres :

Code : Tout sélectionner

Pour imprimer les nombres premiers jusqu'à m (m compris entre de 50 et11449):
 * saisir le programme (97 pas),
 * vérifier l'imprimante, éventuellement y mettre un rouleau de papier neuf,
 * initialiser les registres mémoire R1, R2 , R3 et R4 avec les valeurs suivantes :
    4  STO1  m STO2  7 STO3 et  200 STO4 
 * lancer le programme :
    GSB0 ou  RTN  R/S
Je sais ! J'aurais pû laisser la machine initialiser R1 et R2, mais comme cela il n'y a pas de STO dans l'initialisation et quelques pas libres peuvent toujours servir pour d'éventuels débogages :)

En attendant que je mette en forme et commente le code, voici l'organigramme général:
AutoHeapPrime1.png
AutoHeapPrime1.png (88.29 Kio) Vu 9833 fois
L'épaisseur des traits correspond au nombre de répétitions pour m = 10'000. L'échelle d'épaisseur est la même que pour les précédents posts. la boucle la plus répétée fait 12111 itérations.

L'avancement des pseudo-premiers à tester est en moyenne de 3.75 unités entre deux tests et de 30 unités par tours de la boucle principale. Les multiples de 2, 3 et 5 sont tous évités. C'est presque 2x fois moins de tests qu'avec les autres algorithmes.

La vitesse est presque constante, le ralentissement est dû à l'introduction dans la partie active du min.Heap des facteurs au fur et à mesure du dépassement des carrés des 22 premiers nombres premiers (entre 7 et 97). Par ailleurs, le tas est bien utilisé, seules les opérations de "push down" sont nécessaires, les carrés étant introduits dans l'ordre croissant et ne risquent pas d'interférer avec la "partie active" (donc pas de "pop up" à implémenter). Les 22 facteurs et leurs carrés sont mémorisés dans seulement 22 registres. Il reste trois registres libres. Le tas ne fait pas plus de 5 niveaux. A chaque tour de la boucle, il n'y a donc au plus 4 échanges dans l'arbre.

Le scan avançant d'environ 3.75 et le premier facteur étant 7 (soit un pas de 14), il n'y a jamais plus de 6 mises à jour du min-heap H1 pour chaque nombre n testé. Parfois il y en a même aucune, en général 2 ou 3, en moyenne 2,25. En effet, le tas contient les nombres multiples à venir, il est maintenu en avance sur la progression générale. Les multiples (initiés au carré du facteur) sont augmentés au fur et à mesure de l'avancement d'un pas pair (donc deux fois la valeur du facteur premier). C'est le principe d'un crible de Sundaram, implémenté à l'aide d'un tas binaire minimal et géré par l'unique registre d'indexation que l'on dispose sur une HP-19C. Sur ce point, les HP-41C et autres pockets BASIC sont plus faciles à utiliser; les indirections étant plus faciles. Les multiples et facteurs sont mémorisés dans le même registre selon une des méthodes chère à nos M.P.O. (la partie entière pour le carré et la partie décimale pour le facteur) ce qui facilite leurs nombreux échanges simultanés.


Petite capture de la structure en mémoire lors de l'avancement pour donner une idée du principe :

Code : Tout sélectionner

i: 6    k: 26    m: 10000    n: 2707    R4: 200              ┴
                                 ┌───────────────────────2709.07───────────────┐
                ┌────────────2737.17──────────────┐                     ┌──2717.11──────┐
        ┌───2709.43─────┐                ┌────2717.13─────┐      ┌──2747.41──┐    ┌──2737.23──┐
 ┌──2775.37──┐    ┌──2717.19──┐    ┌──2773.47──┐    ┌──2759.31  2755.29 2809.53  3481.59 3721.61
4489.67 5041.71  5329.73 6241.79  6889.83 7921.89  9409.97   .  .   .   .   .    .   .   .   .
R27: 0 R28:0 R29: 0
Nous sommes à l'étape n=2707, le tas (Heap) contient les 22 prochains nombres composés que l'on s'attend à rencontrer. Ils sont construit à partir des 22 facteurs intervenant jusqu'à 10'000 (22 parmi les 27 car les facteurs 2 3 et 5 sont évités par la méthode de progression)

L'avantage du tas est qu'il donne automatiquement le prochain nombre composé à venir (ici 2709). Une fois que nous l'aurons dépassé, il sera augmenté de 2 x 7 pour donner la position du prochain multiple de 7. On ajoute deux fois le facteur afin d'avancer d'un intervalle pair et conserver l'imparité. En effet, les nombres pairs ne sont jamais rencontrés par construction de la progression de n.

Le nouveau multiple va donc être "enfoncé" (PUSH DOWN) dans le tas en l'échangeant avec des multiples inférieurs. La structure en arbre permettant un nombre minimal de tests et donc aussi d'échanges tout en garantissant de faire remonter au sommet du tas le prochain minium. C'est à dire le prochain multiple qui sera bientôt atteint.
Comme il y a des répétitions et que l'on avance d'un pas variable, plusieurs nombre composés minimum (min-Heap H1) peuvent surgir au même nombre n. On boucle donc sur le label LBL 6 tant que le min-Heap n'a pas rattrapé le rang n.
* Si min-Heap H1 est égal à n cela signifie que n est composite et l'on passe immédiatement au rang n suivant (rien ne sert de continuer à mettre à jour le tas alors que l'on va à nouveau augmenter n).
* Si n est inférieur au plus petit multiple attendu, alors cela signifie que n est premier, car le tas contient tous les multiples possibles car tous les facteurs premiers possibles sont envisagés.
* Si n est supérieur au plus petit multiple attendu, alors il faut continuer à mettre à jour le min-Heap et "enfoncer" dans le tas le prochaine multiple obtenu avec (deux fois) ce facteur.

Autre avantage du tas, les éléments sont introduits égaux au carré du facteur et donc restent en "sommeil" le temps d'arriver à ce rang. Le tas s'active donc progressivement au fur et à mesure de la progression. Par exemple dans le tas ci-dessus, les nodes issus des facteurs 53 et suivants sont encore en "sommeil" et n'ont pas bougés depuis le début du programme. Les multiples formés par 53 n'entreront dans la danse qu'à partir de 2809, ceux de 59 à partir de 3481, et ainsi de suite jusqu'au dernier node s'activant à seulement 9409 (facteur 97).

Par contre, je suis inquiet, c'est beaucoup d'instructions, trois niveau d'appels des sous-programmes, beaucoup de tests et d'adressages indirects !
AutoHeapPrime2.png
AutoHeapPrime2.png (104.84 Kio) Vu 9833 fois
Comment va réagir une vraie HP-19C ??


EDIT :
Corrigé des valeurs pour l'initialisation correcte du programme.
Merci à THOMAS KLEMM du forum de l' HP Museum pour sa lecture attentive de mes publications.
Ce sujet est suivi en anglais ici
Modifié en dernier par C.Ret le 07 nov. 2020 17:03, modifié 3 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
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
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 »

L'intervention de Thomas Klemm, m'a donné l'idée d'adapter le programme pour HP-19C pour mon HP-41C.

J'ai pu imprimer les nombres premiers de 2 à 9973. Pour économiser le papier, j'en mets 5 par ligne ! L'impression ne prends pas plus de 3h09'14" et nécessite environ 63 cm de papier . Pas plus !
AutoHeapPrime41.gif
AutoHeapPrime41.gif (157.52 Kio) Vu 9478 fois
Les couleurs du listing ci-dessus sont celles de l'organigramme précédant. Seule la partie en cyan, qui correspond au regroupement des 5 nombres premiers par ligne d'impression (grâce au registre Alpha: qui sert de tampon d'impression) est d'une nouvelle couleur. Sinon, toutes les autres parties correspondent exactement à l'algorithme utilisé pour l'HP-19C. Le jeu d'instructions et la possibilité d'indexer les registres à partir de la pile ou d'un autre registre permet d'être bien plus concis !

Le Flag 29 est désactivé afin de ne pas avoir de séparateur des milliers lors de l'impression. Ce qui permet, par ligne d'imprimer 5 nombres de quatre chiffres et quatre séparateurs (un espace en fait que je trouve plus lisible que les point, virgule et tiret - voir instruction 089)


Il est possible de réduire le code, en particulier en ne comptant pas les nombre premiers et en affichant un nombre par ligne et ne pas formater l'affichage. On pourra faire disparaitre de nombreuses lignes, le temps d'exécution sera sensiblement le même, par contre, il faudra 3,30 m de papier !!
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 : 6172
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: A faire comme Jürgen Keller

Message par Marge »

Bravo !
Cinq par ligne, tu les imprimes via l'infrarouge ? J'ai l'impression que l'imprimante filaire est plus étroite que l'autre, je me trompe ?
(bon, j'ai les deux, je pourrais regarder, hein, en plus elles ne sont vraiment pas loin... :wink: )
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 : 3404
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 »

Oui, j'utilise le module IR 'blinck' pour partager mon imprimante HP82240A entre ma HP-41C et mon HP-28S.

Elle imprime 24 caractères par ligne et avec le module enfiché, le registre Alpha est aussi de cette longueur. Je pensais que l'82143A avait les mêmes caractéristiques.
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 ? »