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 de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1848
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Jürgen Keller

Message par C.Ret » 28 avr. 2018 18:12

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) Consulté 703 fois
m121d5.png
m121d5.png (38.72 Kio) Consulté 704 fois
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-15C | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator . .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
zpalm
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2390
Inscription : 03 mai 2008 15:33
Localisation : Grenoble

Re: A faire comme Jürgen Keller

Message par zpalm » 28 avr. 2018 18:52

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 de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1848
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Jürgen Keller

Message par C.Ret » 28 avr. 2018 20:14

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 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-15C | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator . .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1848
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Jürgen Keller

Message par C.Ret » 02 mai 2018 12:41

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émoires 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) Consulté 618 fois
L'épaisseur des traits correspond aux nombres 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 qu'au plus 4 échanges.

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-29C. 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 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 automatique le prochain à 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é" dans le tas en l'échangeant avec des multiples inférieurs. La structure en arbre permettant un nombre minimal de tests et donc d'échanges tout en garantissant de faire remonter au sommet du tas le prochain minium. C'est à dire le prochain multiple à atteindre.
Comme il y a des répétitions et que l'on avance d'un pas variable, plusieurs min-Heap H1 peuvent surgir tous inférieurs au nombre n. On boucle donc au rang n jusqu'à mettre à jour le Heap.
* 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 issus de tous les facteurs premiers possibles.

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é 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) Consulté 618 fois
Comment va réagir une vraie HP-29C ??


EDIT :
Corrigé valeurs correctes pour l'initialisation 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
Pièces jointes
AutoHeapPrime2.png
AutoHeapPrime2.png (104.84 Kio) Consulté 620 fois
AutoHeapPrime1.png
AutoHeapPrime1.png (88.29 Kio) Consulté 621 fois
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-15C | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator . .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1848
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Jürgen Keller

Message par C.Ret » 09 sept. 2018 21:41

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) Consulté 263 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 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-15C | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator . .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
Marge
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4108
Inscription : 01 oct. 2008 14:39
Localisation : En bas à gauche.

Re: A faire comme Jürgen Keller

Message par Marge » 10 sept. 2018 02:02

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 !

aut nunquam tentes _________
_________________ aut perfice

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1848
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Jürgen Keller

Message par C.Ret » 10 sept. 2018 11:15

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 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-15C | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator . .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Répondre

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