Misez p'tit Optimisez n°84 : la comète de Goldbach

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

Modérateur : Politburo

Répondre
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

Misez p'tit Optimisez n°84 : la comète de Goldbach

Message par C.Ret »

Alors que le ciel de cette fin d'après-midi estivale est ici d'un beau azur léger et immaculé, je me demandais si votre Calculette ou Pocket préféré serait capable de voir passer une comète de Goldbach ?

Image

J'espère au moins que combien même votre Calculette ou Pocket préféré (ou non d'ailleurs) n'en a pas vu passer - contrairement à mon pauvre SHARP PC-1211 que je soupçonne de maintenant fortement halluciner sous l'effet toxique de l'huile noire qui envahit ses cristaux - ), il est au moins capable de vous aider à en dessiner une !
D'ailleurs, je vois que certains d'entrevous ont dans leur poche ou entre leurs mains de quoi dessiner ou imprimer une telle comète.

Mais je n'en demande pas autant, ce qui permettra à tous les systèmes, il compris les plus vintages de participer.

En fait, le but de cet M.P.O. est de construire le tableau suivant :

Code : Tout sélectionner

                2:  0         4:  1        6:  1        8:  1
 10:  2        12:  1        14:  2       16:  2       18:  2
 20:  2        22:  3        24:  3       26:  3       28:  2
 30:  3        32:  2        34:  4       36:  4       38:  2
 40:  3        42:  4        44:  3       46:  4       48:  5
 50:  4        52:  3        54:  5       56:  3       58:  4
 60:  6        62:  3        64:  5       66:  6       68:  2
 70:  5        72:  6        74:  5       76:  5       78:  7
 80:  4        82:  5        84:  8       86:  5       88:  4
 90:  9        92:  4        94:  5       96:  7       98:  3
100:  6       102:  8       104:  5      106:  6      108:  8
110:  6       112:  7       114: 10      116:  6      118:  6
120: 12       122:  4       124:  5      126: 10      128:  3
Comme vous le savez peut-être, le 7 juin 1742, (j'ai loupé la date anniversaire le mois dernier où je n'ai pas pris le temps de poster mon petit problème) le mathématicien prussien Christian Goldbach a écrit au mathématicien suisse Leonhard Euler une lettre à la fin de laquelle il proposait la conjecture suivante :

"Tout nombre strictement supérieur à 2 peut être écrit comme une somme de trois nombres premiers."

(Goldbach admettait 1 comme nombre premier ; la conjecture moderne exclut 1, et remplace donc 2 par 5.)

Dans sa réponse datée du 30 juin 1742, Euler rappelle à Goldbach que cet énoncé découle d'un énoncé antérieur que Goldbach lui avait déjà communiqué :

"Tout nombre pair peut être écrit comme somme de deux nombres premiers."

(Comme précédemment, « nombre » est à prendre au sens « entier strictement supérieur à 0 » et la conjecture moderne remplace 0 par 2.)

(source Wikipédia)


Mais ce que ne dis pas Euler, c'est qu'il y a souvent bien plus qu'une seule façon de faire la somme de deux nombres premiers pour obtenir un nombre pair.
Et c'est là que nous intervenons, ou du moins nos Calculettes et Pockets préférés. Le tableau ci-dessus donne pour les entiers pairs entre 2 et 128, le nombre de somme de deux nombres entiers possibles.

Pour un nombre pair E=2N , il y a différentes façon de déterminer et d'énumérer les sommes de deux nombres premiers p et q telles que 2N = p + q.
La conjecture indique qu'au delà de N=1, il existe au moins une somme 2N= p+ q

La figure ci-dessous montre les solutions de l’équation 2N = p + q représentées par des ronds, où 2N est un nombre pair entre 4 et 50, et p et q sont deux nombres premiers ː les nombres 2N sont représentés par les lignes horizontales et les nombres premiers p et q sont représentés par les lignes rouges et bleues. La conjecture de Goldbach correspond au fait qu’aussi loin qu’on prolonge la figure vers le bas, toute ligne horizontale grise contiendra au moins un rond :
Image



La fonction de Goldbach g ( E ) est définie pour tous les entiers pairs E > 2 pour être le nombre de façons différentes dans laquelle E peut être exprimée comme la somme de deux nombres premiers. La comète de Goldbach est le nom donné au tracé de la fonction de Goldbach g( E ).

Par exemple, g ( 22 ) = 3 car 22 peut être exprimée comme la somme de deux nombres premiers de trois manières différentes:
22 = 11 + 11
22 = 5 + 17
22 = 3 + 19

le tableau ci-dessus donne donc les valeurs de la fonction de Goldbach entre 2 et 128 inclus.
(Notons que g(2)=0 car 1 n'est plus considéré comme premier, il n'y a donc pas de somme de deux nombres premiers possible pour 2)


Le défi proposé par cet M.P.O. est, si vous l'accepté, de programmer, de la façon la plus efficace possible, la fonction de Goldbach. Le but est de pouvoir utiliser votre Calculette ou Pocket afin de tracer une comète de Goldbach.


Il n'est pas demandé d'afficher ou de lister les différentes sommes, ni même de tracer la comète. Même si je sais que certains le feront, au moins dans un premier temps pour peut-être tester et éprouver leurs algorithmes.

Par contre, il sera tenu compte du fait que certains Pocket et systèmes récents manipulent fort adroitement les nombres premiers à l'aide de fonctions natives. Les codes de ces machins seront donc jugés sévèrement est sans aucune indulgences. Par contre, ceux ou celles qui proposeront des codes efficaces pour les Calculettes ou Pockets dépourvus de fonctions ISPRIME ou NEXTPRIME auront toute la sympathie et l'indulgence des jurés.
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: Misez p'tit Optimisez n°84 : la comète de Goldbach

Message par zpalm »

Intéressant ce MPO, je ne connaissais pas cette fonction ni son histoire.

Voici un petit programme sur HP Prime qui calcule la fonction de Goldbach pour les nombres pairs de 2 à 20000:

Code : Tout sélectionner

EXPORT MPO84()
BEGIN
 LOCAL j,n=3,g,m,p={};
 g:=MAKELIST(I==2,I,1,10000);
 WHILE n<20000 DO
  p(0):=n;
  FOR j FROM 1 TO SIZE(p) DO
   m:=(n+p(j))/2;
   IF m<=10000 THEN g(m):=g(m)+1 ELSE BREAK; END; 
  END;
  n:=nextprime(n);
 END;
 L1:=g;
END;
Les résultats sont retournés dans la liste L1: L1(n)=Goldbach(2n), ainsi L1(63)=10 qui est la valeur de la fonction de Goldbach pour 126.

Et voici un petit programme pour tracer la comète de Goldbach à partir des valeurs stockées dans une liste:

Code : Tout sélectionner

EXPORT PLOT_L(List)
BEGIN
LOCAL i,x_max,y_max;
  RECT();
  x_max:=SIZE(List); y_max:=MAX(List);
  LINE_P(10,230,320,230);LINE_P(10,10,10,230);
  TEXTOUT_P(2*x_max,286,232,1);
  TEXTOUT_P(y_max,0,2,1);
  TEXTOUT_P(0,4,232,1);
  FOR i FROM 1 TO x_max DO
    PIXON_P(IP(i*300/x_max)+10,220-IP(List(i)*220/y_max)+10,#FFh);
  END;
  FREEZE;
END;
Après l'exécution de MPO84 qui prend environ 6'15" sur mon HP Prime, on peut tracer la comète par PLOT_L(L1):

Image
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: Misez p'tit Optimisez n°84 : la comète de Goldbach

Message par C.Ret »

Astucieux ce programme qui précalcule toutes les valeurs paires de la fonction de Goldbach en une seule boucle !

Effectivement, c'est une stratégie payante, car il suffit de parcourir les nombres premiers une seule fois jusqu'à l'extrémité de la liste pour incrémenter au fur et à mesure g(n) - c'est à dire g(e) avec e=2n - Et cela est très facile sur une HP prime qui maitrise bien la primalité des nombres même grands.

Grands, par rapport à ce que je fais sur mon SHARP PC-1211 ou une HP-15C. Sur ces machines classiques, je n'ai pas une seule seconde envisager un algorithme efficace pour des dizaines de milliers.

Je suis tout de même très satisfait de pouvoir vérifier que Gb(126) fait bien 10. à l'aide de mon SHARP PC-1360 en effet :
Goldbach_PC1360_126.png
Goldbach_PC1360_126.png (124.84 Kio) Vu 10345 fois
Mais il y a trois points qui ne vont pas dans ce que nous présente zpalm (j'avais bien prévenu que je serai intransigeant avec ces machins):

-1- La comète ne se dessine pas au fur et à mesure du précalcul, c'est dommage cela aurait permis de patienter les 6" (c'est long sur cette machine). Il faut deux programmes ? Il n'y apas sur l'HP prime une instruction simple pour afficher le contenu d'une liste, d'un vecteur ou d'une matrice ?
-2- Il y a deux boucles imbriquées, une pour parcourir les nombres premiers, l'autre pour mettre à jour la liste des g(n). Deux boucles sur un vecteur ce n'est pas quelque part une seule instruction matricielle ?
-3- Malgré tous les efforts, est contrairement aux antiques, ce code ne donne pas la liste exhaustive des sommes des deux nombres premiers.


Laissons un peu de temps à zpalm pour qu'il corrige ces petits détails...

En attendant voici un code encore optimisable qui permet de calculer la fonction de Goldbach sur SHARP PC-1360

Code : Tout sélectionner

1 "G" AREAD N: DIM P(N) : G=N/2-1 : FOR F=2 TO N-2 : J=P(F) , I=F+J : IF J=0 LET J=F , I=F*F 
2 IF I>N-2 GOTO 6
3 IF P(I) LET I=I+J : GOTO 2
4 IF P(N-I)=0 LET G=G-1
5 P(I)=J
6 NEXT F: LPRINT "Gb("; STR$ N ;") = ";G

8 FOR F=2 TO N/2: IF P(F)+P(N-F)=0 LPRINT RIGHT$("   "+STR$ F,4);"+";LEFT$( STR$ (N-F)+"  ",3);
9 NEXT F: LPRINT : ERASE P : END
Les lignes 8 et 9 sont optionnelles, elles permettent d'imprimer la liste des somme de deux nombres premiers.

Ne cherchez pas de test ISPRIME? dans ce code, il utilise un crible de Sundaram, pour Gb(126) l'impression ci-dessus est terminée environ 40s. après avoir saisi 126 et pressé sur [def][ G ].

Dans cette version, on ne peut aller au-delà de N=254 - à cause de la limite induite par le DIM P() - Une version plus complexe permet d'aller jusqu'à 514. Elle est basée sur le même principe mais plus complexe car utilise plus habilement le tableau P() pour éviter les valeurs paires. Mais les jeux d'indexage la rende difficile à décryptée.

Alors que cette version présente un mécanisme fort simple et bien plus facile à encoder.
Modifié en dernier par C.Ret le 10 juil. 2018 20:19, modifié 6 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: Misez p'tit Optimisez n°84 : la comète de Goldbach

Message par Marge »

MPO très intéressant ! je me demande combien de temps il me faudrait pour faire fonctionner un programme permettant d'obtenir de si belles courbes sur mon HP-41cx et sa HP 82240B... :roll: :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 : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°84 : la comète de Goldbach

Message par C.Ret »

P.S.: J'oubliais la version SHARP PC-1211

Code : Tout sélectionner

1:CLEAR :USING "####":INPUT A:C=A/2-1:FOR B=2 TO A-2:D=A(4+B),E=B+D:IF D=0 LET D=B,E=BB
2:IF E>A-2 GOTO 5
3:IF A(4+E) LET E=E+D:GOTO 2
4:C=C-(A(4+A-E)=0),A(4+E)=D
5:IF A<=2B IF A(4+B)+A(4+A-B)=0 PRINT A-B;" +";B
6:NEXT B:BEEP 1:PRINT "G(";A;" )=";C:END

1242 STEPS 155MEMORIES
La ligne 5 peut être retirée, elle en sert qu'à afficher les sommes premières.
On peut calculer la fonction de Goldbach et afficher les sommes premières jusqu'à 174.

Code : Tout sélectionner

(MODE)           >
RUN(ENTER)       ?
126(ENTER)       126_                         1'54"
(ENTER)            59 +  67
(ENTER)            53 +  73
(ENTER)            47 +  79
(ENTER)            43 +  83
(ENTER)            37 +  89
(ENTER)            29 +  97
(ENTER)            23 + 103
(ENTER)            19 + 107
(ENTER)            17 + 109
(ENTER)            13 + 113     "bip"
(ENTER)          G( 126 )=  10
(ENTER)          >

Ainsi que l'équivalent pour HP Prime :

Code : Tout sélectionner

define Gb(N) := ΣLIST(isprime(MAKELIST(I,I,1,N/2).*isprime(MAKELIST(N-I,I,1,N/2)))
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: Misez p'tit Optimisez n°84 : la comète de Goldbach

Message par C.Ret »

Comme c'est un M.P.O., je me permets de proposer un perfectionnement du programme de zalpm pour HP Prime.

Cette nouvelle version fait disparaitre malheureusement qu'une partie des "défauts" que je trouvais à la version fort astucieuse de notre ami. J'avais trouvé un moyen d'éviter la boucle " FOR i FROM … " de lignes 12 à 13 par une seule instruction, mais cela ralentissait bien trop le déroulement du programme.
Je me retrouve donc avec un programme très proche de celui de zalpm mais qui présente l'avantage de dessiner la "comète" au fur et à mesure des calculs:
MPO84_HPprime_1.png
MPO84_HPprime_1.png (22.75 Kio) Vu 10286 fois
En argument, on indique le nombre de nombres premiers à utiliser, pour dessiner les 10'000 premiers nombres pairs, il faut utiliser 2261 nombres premiers. Dans ce cas, le graphique sera achevé au bout d'environ 6'26".
MPO84_HPprime_2.png
MPO84_HPprime_2.png (8.38 Kio) Vu 10286 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 : 2917
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°84 : la comète de Goldbach

Message par zpalm »

C.Ret a écrit : 16 juil. 2018 22:34 Je me retrouve donc avec un programme très proche de celui de zalpm mais qui présente l'avantage de dessiner la "comète" au fur et à mesure des calculs:
Joli ! Je suis en vacances, loin de mon HP Prime... Je n'avais pas trouvé la formule permettant de calculer Ymax à l'avance, c'est pourquoi je traçais la comète à la fin.
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: Misez p'tit Optimisez n°84 : la comète de Goldbach

Message par C.Ret »

Marge a écrit : 09 juil. 2018 21:17 […] je me demande combien de temps il me faudrait pour faire fonctionner un programme permettant d'obtenir de si belles courbes sur mon HP-41cx et sa HP 82240B[...]

Bien plus de temps que sur l'HP Prime qui, outre son petit cœur qui bat fort vite, profite d'une mémoire immense qui permet de manipuler des listes de 10'000 éléments.
==> Ce qui permet un algorithme simple de calcul de la fonction de Goldbach par simple comptage de l'occurrence des nombres pair entre 2 et 20'000. Comptage d'autant plus facile que les cette machine connait les nombres premiers long jusqu'à plus de 12 chiffres.

Les Pockets comme le PC-1211 ou le PC-1360 ont plusieurs centaines de registres, ce qui permet pour un nombre pair donné - en fait cela marche aussi pour un nombre impair - de calculer la fonction de Goldbach à l'aide d'un crible (ou d'une autre technique) au fur et à mesure de la détermination des nombres premiers jusqu'à la moitié de ce nombre. Calculer la fonction de Goldbach pour N revient à créer un tableau P(N), remplir ce tableau avec la valeur des facteurs pour les nombres composés et compter les couples (P(i),P(N-i)) égaux à (0,0). l'algorithme présenté dans l'un des posts précédents effectue le travail en ne parcourant qu'une fois le tableau P().

Par contre, l' HP-41C, comme l'HP-15C n'ont que quelques dizaines de registres. La fonction de Goldbach va devoir être déterminée plus laborieusement pour chaque nombre N puisqu'il va falloir trouver (ou tester) tous les nombres premiers p et q tels que N = p+q. On peux cependant s'inspirer de la méthode utilisée pour les Pockets, mais comme il n'y aura pas de tableau, il faudra répéter les déterminations pour tous les couples (p,q) envisagés.


Par contre, pour gagner du temps, sans trop alourdir le code, on peut tester les primalités de p et q - avec q = N -p - simultanément. Dès que l'un ou l'autre est composé on arrête la détermination - le résultat pour son camarade n'ayant plus d'importance -
Comme de plus on se limitera à par exemple à chercher p<q pour ne pas compter deux fois les mêmes sommes premières - eh oui : p+q = q+p héhé ! - Cette contrainte introduit tout un tas de propriétés fort sympathiques pour réduire le code, trouver une condition de fin, limiter le nombre de facteurs de divisibilité à tester, simplifier les tests ...


On obtient alors un algorithme fort sympathique qui peut se schématiser comme suit :
Ordigram MPO84_1.png
Ordigram MPO84_1.png (30.58 Kio) Vu 10199 fois
Mais, qu'il reste à implémenter convenablement en RPN comme il se doit pour son (ou ses) HP Classic, Woodstock, , Spice, Coconut, Voyager ou même Pionneer !


Ce qui donne le code suivant - code qui reste évidemment à optimiser - :
MPO84_HP15C_1.png
MPO84_HP15C_1.png (93.93 Kio) Vu 10199 fois
Ce programme se compose de deux parties :
LBL A : qui pour tout entier N calcule la fonction de Goldbach en affichant temporairement toutes les sommes premières trouvée.
LBL D : sous-programme d'affichage qui peut être utilisé indépendamment qui permet d'afficher deux entiers Y et X sous la forme d'un nombre décimal yy.xxx


Le programme A n'est pas le plus rapide. Par contre il fonctionne pour tout entier à partir de 2. Il peut même trouver des sommes premières pour les nombres impairs. Mais il n'est pas rapide. Je compte sur vous pour l'optimiser.
Fichiers joints
Ordigram MPO84_1.png
Ordigram MPO84_1.png (30.58 Kio) Vu 10202 fois
MPO84_HP15C_1.png
MPO84_HP15C_1.png (94.5 Kio) Vu 10202 fois
MPO84_HP15C_1.png
MPO84_HP15C_1.png (94.5 Kio) Vu 10204 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 : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°84 : la comète de Goldbach

Message par C.Ret »

Comme vous avez pû vous en rendre compte, le code précèdent n'est pas rapide. Surtout sur une HP-15C originale qui n'a pas la vélocité de l'édition spéciale.

Pour corriger cela, je vous propose de suivre l'algorithme suivant:

MPO84_Ordigram_2.png
MPO84_Ordigram_2.png (105.15 Kio) Vu 10067 fois

Je vous laisse le soin d'implémenter cela sur votre Calculette ou Pocket préféré.


Une autre solution consisterai à n'envisager que les nombres impairs et d'utiliser un petit crible astucieux dont l'usage sera accéléré et fluidifié par l'intermédiaire d'un tas adroitement géré :D
MPO84_Ordigram_3.png
MPO84_Ordigram_3.png (118.84 Kio) Vu 10049 fois
Je sais. Il fait chaud; installez vous dans un endroit aéré, à l'ombre et hydratez vous convenablement… je ne voudrai pas que vous séchiez sur ce problème.


P.S.: Le dernier algorithme fonctionne pour tous les nombre positifs pairs mais aussi pour la plupart des nombres impairs. Il manque juste quelque test dans la partie "P & Q primes" pour que tous les N, même impairs ou premiers fonctionnent.

- Attention la flèche avant M(1) signifie en fait qu'il faut prendre INT(M(1)) ou FLOOR(M(1)) - Le tableau M() commence à M(0) dont la valeur doit rester nulle. La taille du tableau dépend de la limite supérieur pour N. Avec les coefficients 1E-3 (et 2000) on doit se contenter de N<1000 et il faut alors pas plus de 166 valeurs dans M().
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: Misez p'tit Optimisez n°84 : la comète de Goldbach

Message par C.Ret »

J'ai trouvé un coin bien aéré et à l'ombre: je m'attendais à trouver dès ce soir vos versions pour les différents algorithmes proposés ci-dessous.

Je vous laisse un peu de temps.


Je suis déjà en train de faire une version pour HP-19C qui s'inspire fortement de cette version pour PC-1360 qui a passé une partie de la matinée avec moi au frais dans le jardin:

Code : Tout sélectionner

REM  ----  Init MinBinHeap 
 1:CLEAR : DIM M(255): INPUT "N=";N: WAIT 0:E=1E4,P=2: IF n<4 GOTO 6
 2:GOSUB 22: IF N<6 GOSUB 10: GOTO 6
 
REM  ----  Main loop : P  
 3:FOR P=3 TO N-2 STEP 2: GOSUB 11+(P= INT M(1))
 4:IF P>= INT M(1) GOSUB 13: GOTO 4
 5:NEXT P

REM  ----  End of Program
 6:PRINT "Gb("; STR$ N;")=";G: END

Code : Tout sélectionner

REM  ====  Primary Sum Display sub-routine
10:G=G+1: PRINT STR$ (N-P);"+";P;: RETURN

REM  ====  Redirections sub-routines
11:GOTO 10+8*(P<N-P)
12:IF 2*P<N GOTO 17

Code : Tout sélectionner

REM  ====  PUSH M(1) into MinBinHeap stack
13:M(1)=M(1)+2* INT (E*(M(1)- INT M(1))),I=1,M=M(1)   : REM  === Increase M(1) 2x factor (keep parity - Sadaram trick
14:I=2*I: IF I<K IF M(I+1)<M(I) LET I=I+1             : REM  === Select min leaf when two exist
15:IF I<=K IF M(I)<M LET M(I/2)=M(I),M(I)=M: GOTO 14  : REM  === Swap nodes to push M down in heap & loop
16:RETURN                                             : REM  === exit when heap is ok

Code : Tout sélectionner

REM  ====  POP up MinBinHeap sub-routines
17:M=N-P+N/E: GOTO 19                                 : REM  === Store Q in Heap when P is not prime (Q maybe prime)
18:M=P*P+P/E                                          : REM  === Store P² in heap for Sadaram's prime cribling 
19:I=K                                                : REM  === Enter new value at end of heap and POP it UP 
20:M(I)=M: IF M(I/2)>M LET M(I)=M(I/2),I=I/2: GOTO 20 : REM  === Pop up new value and loop until heap is OK
21:IF M(K)>N RETURN                                   : REM  === Too large value not kept, reduce size of heap
22:K=K+1,M(K)=N: RETURN                               : REM  === Increase size of Heap, set last element to infinity
Cette nouvelle version n'est pas la plus rapide pour les petites valeurs de N - elle met 1'09" pour trouver les sommes premières de 126 au lieu des 0'40" de la version précédente -
Son réel avantage est qu'elle est bien plus rapide pour les grandes valeurs de N.
Les 28 sommes premières de N=1000 sont effectivement imprimées en moins de 18' :
MPO84_PC1360_1.gif
MPO84_PC1360_1.gif (80.38 Kio) Vu 10034 fois

Bon, je prépare des piles pour mon HP-41C et son imprimante qui ne demandent qu'à tracer des comètes. C'est bien la saison des étoile filantes non ?
Modifié en dernier par C.Ret le 01 févr. 2019 19:57, 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
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6167
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez p'tit Optimisez n°84 : la comète de Goldbach

Message par Marge »

Bonne sueur, C.Ret ;)

Je suis toujours impressionné par tes présentations d'algorithmes d'excellente qualité (comment fais-tu ?), mais je crois surtout que c'est ton intelligence et ta force de travail qui emportent mon adhésion !
La comète de Goldbach est un bon thème, mais personnellement je suis ailleurs - toutefois toujours en mathématiques. Peut-être aussi, la lenteur de mes vieux engins à tracer ces étoiles sur le papier ne m'encourage guère, qui sait ?

Je n'ai pas l'excuse de la canicule. Ici, il fait frais. Je vous recommande de visiter des grottes. Ou des caves.

J'espère revenir plus tard à ces amours, les nombres premiers sur 19c et cette figure étonnante.
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: Misez p'tit Optimisez n°84 : la comète de Goldbach

Message par C.Ret »

Marge a écrit : 09 juil. 2018 21:17 MPO très intéressant ! je me demande combien de temps il me faudrait pour faire fonctionner un programme permettant d'obtenir de si belles courbes sur mon HP-41cx et sa HP 82240B... :roll: :wink:
Voilà de quoi répondre à cette question :

MPO84_HP41C_printer1.jpg
MPO84_HP41C_printer1.jpg (73.09 Kio) Vu 9958 fois

Le code a été essayé sur une HP-41C et une HP 82240A également reliés par un module I.R. "blinky". Les commandes d'impression utilisées sont standards et utilisées comme il se doit. J'imagine qu'il ne posera donc aucun soucis avec une HP 82240B ou même une imprimante HP 82143A reliée par HP-IL.
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: Misez p'tit Optimisez n°84 : la comète de Goldbach

Message par Marge »

Magnifique !

Je vais essayer cela dans la semaine. Merci !
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: Misez p'tit Optimisez n°84 : la comète de Goldbach

Message par C.Ret »

A priori, il permet de tracer une comète allant jusqu'à 4244 grâce aux 166 colonnes que contient une ligne d'impression.

MAIS, j'ai peur que cela ne prenne plus d'une semaine et épuise complètement les batteries. En effet, contrairement à l'HP Prime qui résous le problème du temps d'exécution en mémorisant les 581 nombres premiers nécessaires, calcule les 2122 valeurs de G() par une simple suite de 2¼ millions d'additions avant de directement les afficher en allumant simplement un des 76'800 pixels de son écran LCD, nos pauvres HP 41 sont obligées de redécouvrir à chaque ligne de pixels tout ou partie des nombres premiers, tester les divisibilités des deux termes de la somme, comptabiliser les valeurs de G() 7 par 7 pour correspondre à la hauteur d'encodage graphique et tracer la courbe en imprimant jusqu'à 166 colonnes de 7 pixels dont il faut encoder les bits.

Malheureusement, le temps d'impression croît dans ces atroces conditions opératoire de façon exponentielle; je pense que l'on est pas prêt de voir la fin de la comète …::::;;;;;!!!!!!!! ?


Mais, cela va répondre très pragmativement à la question posée. Et trouver une réponse expérimentale aux questions les plus ardues est toujours source de progrès et d'espoir.

(Sans compter que le code présenté est loin d'être optimisé et qu'il ne demande qu'à être convenablement MPOïsé)
GoldBach Printed Comet HP 82242A.gif
GoldBach Printed Comet HP 82242A.gif (71.44 Kio) Vu 9917 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.
Répondre

Retourner vers « Tous les Pockets »