La Question (anticipée) du Dimanche 13 Mars 2022

[Hobiecat]

Je me suis amusé sur le 71B, avec une méthode fortement [s]inspirée[/s] pompée sur celle de Zpalm : ça va assez vite, puisqu'on trouve les 4 solutions en respectivement 4, 8,14 et 20s et la recherche se termine environ en 50s.

Pour 20220313, on trouve vite les 3 premières valeurs, mais après, ça tourne "un certain temps" pour arriver aussi à 4 valeurs.

Voici mon programme:

Il me semble qu'il y a une petite erreur de transcription, la première ligne devant être 44 0 (STO 0) et non 44 10 (STO /) , mais je n'ai plus de pile bouton à mettre dans ma 10C pour vérifier.

[Marge]

Bonsoir,
Je trouve également vos solutions en 30 pas tout compris pour la version courte (220313), mais j'ai un problème sur ma HP-29E pour chronométrer car elle se met automatiquement en veille d'affichage au bout d'un certain temps et il faut presser une touche pour redémarrer. Je vais voir si je peux désactiver ce bazar - ce n'est pas indiqué dans l'aide-mémoire que je conserve dans son étui.

Merci pour cette question du dimanche qui m'a permis de sortir le nez de mon Psion 3a !

PS : je vais peut-être simplement essayer sur la 19C.

PPS : La 19C imprime le premier résultat en 5 minutes 23 secondes, puis les autres en 5 mn 56, 6 mn 34 et enfin 7 mn 02 avant de s'arrêter par un RTN. J'ai moyen de raccourcir ces délais, mais vais-je réduire le nombre de pas ?

PPPS : Eh bien non, j'obtiens un bon gros programme de 37 pas - j'entre toutes les données dedans. Mais j'ai bien réduit le temps d'exécution :

Code : Tout sélectionner

2 mn 14
2 mn 29
2 mn 46
2 mn 58

Et j'obtiens un "Error" à la fin ! Ce n'était pas dans le cahier des charges, mais ce n'est pas interdit !

[zpalm]

Il me semble qu'il y a une petite erreur de transcription, la première ligne devant être 44 0 (STO 0) et non 44 10 (STO /) , mais je n'ai plus de pile bouton à mettre dans ma 10C pour vérifier.

Exact, j'ai corrigé le listing dans le post précédent.

J'utilise sur Excel et Word les fontes suivantes:
"Keyset 4" et "HP Voyager Character Set"
Malheureusement, les liens vers les sites où je les avait téléchargés sont morts depuis longtemps

Ah oui, ce sont les fontes de Luiz C. Viera, je les ai retrouvées sur son site: http://www.lcvdata.com/downloads/lcvfonts/
Le document "14-segment builder_5.pdf" explique comment les utiliser.

Du coup je me suis fait plaisir, et voici le listing complet de mon programme pour la HP-10C:

HP-10C_b.png (24.72 Kio) Vu 2977 fois

Il est facilement adaptable sur la HP-25 qui a plus d'instructions de tests ce qui permet de gagner un pas de programme.

EDIT: j'ai remplacé R/S au pas 08 par GTO 00 pour une meilleure fin de programme permettant d'enchainer avec l'entrée d'une nouvelle valeur suivie de R/S pour lancer l'exécution.

[zpalm]

j'ai un problème sur ma HP-29E pour chronométrer car elle se met automatiquement en veille d'affichage au bout d'un certain temps et il faut presser une touche pour redémarrer. Je vais voir si je peux désactiver ce bazar - ce n'est pas indiqué dans l'aide-mémoire que je conserve dans son étui.

C'est le mode Standby qui est activé/désactivé en pressant 0 lors de la mise sous tension comme indiqué page 18 du ACT Repair Kit User Manual.

[Marge]

j'ai un problème sur ma HP-29E pour chronométrer car elle se met automatiquement en veille d'affichage au bout d'un certain temps et il faut presser une touche pour redémarrer. Je vais voir si je peux désactiver ce bazar - ce n'est pas indiqué dans l'aide-mémoire que je conserve dans son étui.

C'est le mode Standby qui est activé/désactivé en pressant 0 lors de la mise sous tension comme indiqué page 18 du ACT Repair Kit User Manual.

Merci pour l‘info ! Il faudra que je songe à l‘ajouter dans mes notes...

[C.Ret]

PPPS : Eh bien non, j'obtiens un bon gros programme de 37 pas - j'entre toutes les données dedans. Mais j'ai bien réduit le temps d'exécution :

Et j'obtiens un "Error" à la fin ! Ce n'était pas dans le cahier des charges, mais ce n'est pas interdit !

Moi je dis, il faut programmer tout cela comme ça vient ! Diantre, ce n'est pas un MPO, alors on fait comme on aime faire.
Avant de sévir sur Silicium, je ne programmais que comme cela; ma seule inquiétude était d'obtenir un résultat erroné. Alors je faisait simple et didactique et je me moquais du nombre de pas, de la vitesse, de ceci ou cela.

Voilà, en trouvant ce problème, j'ai attrapé la première machine sur l'étagère, c'était une HP-41C et je lui ai tapoté ceci:

Code : Tout sélectionner

01 LBL "QDD
02   CLRG  ENTER^  SQRT  INT  .02  +  3  10↑X  +  LASTX  /                      ;; Initialise compteur → 1.rrr02 où rrr = √(nnnnnn)
13   LBL 01  RCL Y  RCL Y  INT  MOD  x=0?  XEQ 02  RDN  ISG X  GTO 01           ;; Boucle de recherche des diviseurs 
23   RCL 00  CHS  TONE 5  CLD                                                   ;; Affiche -nb de solutions et sonne.
27 RTN

28   LBL 02  X<> L  ST/ T  R^  -  -2  /  ISG 00  PSE  STO IND 00  VIEW X        ;; Mémorise nouvelle solution (et affiche ou imprime)
39 END

Un bon gros programme de 39 pas ! J'aime tapoter !
En tout cas, c'est structuré, méthodique. Et cela mémorise les solutions dans les registres R01, R02, R03, ...
Le registre R00 donne le nombre de solutions trouvées.
Toutes les variables sont dans la pile.

La boucle de recherche LBL 01 est réduite à peu de calculs afin de ne pas perdre de temps en parcourant les valeurs non solutions et utilise l'instruction ISG X pour parcourir les diviseurs candidats deux à deux.

Le sous-programme LBL 02 déduit la nouvelle valeur de n solution à partir du diviseur et de la constante.
J'aime utiliser l'instruction VIEW qui affiche le résultat pendant que l'HP-41Cest déjà en train de rechercher le suivant. Et si l'imprimante est en ligne, cette commande a aussi l'avantage d'imprimer le résultat. Pile Poêle.

QDD-220313- HP41C.gif (180.87 Kio) Vu 2967 fois

Ca marche pour (n²+220313), la vérification complète se fait en environ 1'08".
Les solutions s'impriment dans l'ordre : 110156 (0'02") 3784 (0'09") 1516 (0'14") et 976 (0'20")

Ca ne marche pas pour (n²+20220313) car la racine carrée fait plus de trois chiffres
J'ai dû tapoter autre-chose.

[C.Ret]

Je me suis amusé sur le 71B, avec une méthode fortement [s]inspirée[/s] pompée sur celle de Zpalm : ça va assez vite, puisqu'on trouve les 4 solutions en respectivement 4, 8,14 et 20s et la recherche se termine environ en 50s.

Pour 20220313, on trouve vite les 3 premières valeurs, mais après, ça tourne "un certain temps" pour arriver aussi à 4 valeurs.

Voilà une idée très bizarre; utiliser l'algorithme de zpalm sur une machine qui possède l'instruction MOD !

Pour 220313 et 20220313, mon HP-71B me donne les quatre solutions et boucle la recherche en respectivement 8"63 et 48"35:

[RUN] 220313 [END LINE] affiche 110156 (.14") 3784 (.5") 1516 (1.37") 976 (3.56") NB=4 (8.63")

[RUN] 20220313 [END LINE] affiche 10110156 (.15") 532104 (.48") 61944 (2.88") 1716 (33.04") NB=4 (48.35")

L'algorithme de zpalm est particulièrement court et adapté à l'HP-10C (et les autres voyagers), mais il a l'inconvénient de faire le calcul de nombreux carrés pour rien car ils ne sont pas parfaits et donc ne sont pas affichés.

L'algorithme que j'utilise sur HP-41C, HP28S, HP71B et Hp Prime tire parti du fait qu'il y a sur ces machines des instructions permettant de trouver facilement les diviseurs d'un entier.
Les temps ci-dessus correspondent à l'utilisation de l'instruction MOD dans une boucle FOR TO STEP / NEXT exactement comme pour l'HP-41C

De plus, si j'utilise la fonction PRIM du module JPC de mon HP-71B, alors la boucle de recherche fait des bonds et les temps tombent à respectivement 1.06" et 2.05" En effet, PRIM renvoi 0 pour un nombre premier ou le plus petit diviseur ce qui permet de 'lister' les diviseurs sans avoir besion d'une boucle FOR To STEP / NEXT

[Hobiecat]

L'algorithme de zpalm est particulièrement court et adapté à l'HP-10C (et les autres voyagers), mais il a l'inconvénient de faire le calcul de nombreux carrés pour rien car ils ne sont pas parfaits et donc ne sont pas affichés.

Mais cet algorithme est très efficace, quand je.compare les temps que j'ai indiqués plus haut et ceux que tu indiques

Ça pourrait d'ailleurs être un critère discriminant de MPO, à nombre de pas égaux : celui qui va le plus vite !

[zpalm]

L'algorithme que j'utilise sur HP-41C, HP28S, HP71B et Hp Prime tire parti du fait qu'il y a sur ces machines des instructions permettant de trouver facilement les diviseurs d'un entier.

Bien vu l’utilisation de MOD.

De plus, si j'utilise la fonction PRIM du module JPC de mon HP-71B, alors la boucle de recherche fait des bonds et les temps tombent à respectivement 1.06" et 2.05" En effet, PRIM renvoi 0 pour un nombre premier ou le plus petit diviseur ce qui permet de 'lister' les diviseurs sans avoir besion d'une boucle FOR To STEP / NEXT

Intéressant, combien de solutions trouves-tu pour 14725 en utilisant PRIM?

[Schraf]

Comme je suis en train de travailler sur les HP-48/49/50G, avec les DOLIST, MAP... voici ma contribution pour cette question (uniquement pour les 49 et 50g car les 48G ne connaissent pas DIVIS). Attention également, il faut être en MODE CAS Exact (décocher Approx)

Code : Tout sélectionner

« DUP DIVIS SWAP OVER / - 2 / 
  1 « IF DUP 0 ≤ THEN DROP END » DOLIST 
»
'CP STO

Les résultats sont quasi immédiats :

Code : Tout sélectionner

220313 CP
{976 1516 3784 110156}

20220313 CP
{1716 61944 532104 10110156}

14725 CP
{222 30 378 282 1470 7362}       6 solutions

L'idée est de chercher les diviseurs du nombre N, ce qui donne une première liste L, ensuite de créer une seconde liste N / L. En faisant la différence des 2 listes et en divisant le tout par 2, on obtient les valeurs a priori possibles. Finalement on filtre (compression logique) pour ne garder que les entiers > 0.

[Marge]

Bonjour, voici comment j'ai résolu ce petit problème.

npg220313.png (2.66 Kio) Vu 2913 fois

Avec g entier (grand côté), il faut donc trouver tous les n entiers tels que n²+220313=g².

On voit tout de suite que g=p+n si l'on nomme p le petit côté de la surface verte.

D'autre part, il m'est apparu évident qu'il s'agirait plus facilement de déterminer n en fonction de p et de la moitié de la surface mesurant 220313 unités, soit 220313/2, car le trapèze résultant mesure exactement
p * n + p²/2.

Or si l'on doit chercher n strictement positif en fonction de p, pour déterminer le seuil de recherche sur p, on peut considérer l'équation du second degré avec n=1, soit (après quelques réflexions) : p²+2p-220313=0

Cette équation admet une solution positive qui nous intéresse : p est approximativement égal à 468 par défaut ; il s'agira donc de balayer tous les p impairs de 469 à 1 pour obtenir tous les n candidats sur lesquels un test d'appartenance aux entiers sera réalisé. L'allongement du programme est dû au double test (l'un dès la première division, l'autre après l'ensemble des divisions) qui évite des calculs inutiles.

La formule utilisée est : (220313/p - p)/2

Voici le programme deuxième mouture qui provoque sur l'HP-19C une erreur après avoir donné les quatre bons résultats, dans l'ordre croissant, en un temps relativement bref (moins de trois minutes tout compris). L'erreur est bien sûr provoquée par une division par zéro à la fin de la décrémentation du registre 0.

Code : Tout sélectionner

01 LBL 9   11 9       21 /       31 x=0
02 2       12 STO 0   22 FRAC    32 GSB 0
03 2       13 LBL 8   23 x#0     33 GTO 8
04 0       14 DSZ     24 GTO 8   34 LBL 0
05 3       15 DSZ     25 LAST x  35 LAST x
06 1       16 GTO 7   26 RCL 0   36 PRx
07 3       17 RTN     27 -       37 RTN
08 STO 1   18 LBL 7   28 2
09 4       19 RCL 1   29 /
10 6       20 RCL 0   30 FRAC

Le résultat est imprimé sur un peu plus de 2 cm, C.Ret.

Une fois la cause de l'erreur découverte, j'ai vite réalisé que les pas 16 à 18 étaient devenus inutiles puisqu'il suffirait d'attendre patiemment l'erreur pour considérer le travail comme accompli. J'ai pu réalisé un comparatif entre la 19C et la 29E ; fort du conseil de zpalm qui empêche la mise en veille de l'affichage, j'ai mesuré les résultats suivants :

Code : Tout sélectionner

+---------+---------+--------------+
|Résultat | HP-29E  |    HP-19C    |
+---------+---------+--------------+
|     976 | 52 s. 92| 1 m. 51 s. 61|
+---------+---------+--------------+
|    1516 |+ 6 s. 93|    + 12 s. 40|
+---------+---------+--------------+
|    3784 |+ 8 s. 22|    + 14 s. 15|
+---------+---------+--------------+
|  110156 |+ 5 s. 76|     + 9 s. 89|
+---------+---------+--------------+
|  Error  |+ 1 s. 77|     + 1 s. 70|
+---------+---------+--------------+

Voici le programme pour les deux machines, seul le pas 33 doit être modifié en PRx pour l'impression sur HP-19C.

Code : Tout sélectionner

01 LBL 9   11 9       21 GTO 8   31 LBL 0
02 2       12 STO 0   22 LAST x  32 LAST x
03 2       13 LBL 8   23 RCL 0   33 Pause
04 0       14 DSZ     24 -       34 RTN
05 3       15 DSZ     25 2
06 1       16 RCL 1   26 /
07 3       17 RCL 0   27 FRAC
08 STO 1   18 /       28 x=0 
09 4       19 FRAC    29 GSB 0
10 6       20 x#0     30 GTO 8

[Hobiecat]

Sympa cette méthode "géométrique", Marge !

[Marge]

Oui, merci, mais je n'ai peut-être pas poussé cette logique géométrique aussi loin que j'aurais dû : j'ai visiblement enfoncé une porte ouverte (ou cherché midi à quatorze heures) avec ma recherche de la racine positive de l'équation qui correspond en fait à p quand n=0 pour une surface de 220313. Mais bon, le principal est de trouver une limite et il se pourrait même que le programme soit plus rapide ainsi.

[C.Ret]

Mais cet algorithme est très efficace, quand je compare les temps que j'ai indiqués plus haut et ceux que tu indiques

Oui, on parle bien d'environ ~8s pour 220313 et ~50s pour 20220313 ?

10 DESTROY ALL @ DELAY 0,0 @ INPUT C @ T=TIME
12 FOR D=1 TO SQR(C) STEP 2
14 IF NOT MOD(C,D) THEN GOSUB 20
16 NEXT D @ DISP "Nb:";N; @ GOSUB 22 @ END

20 N=N+1 @ DISP ABS(C/D-D)/2;
22 DISP '('&STR$(TIME-T)&'")'; @ RETURN

[RUN] 20220313 [END LINE] affiche sur mon HP-71B
10110156 (.18") 532104 (.54") 61944 (2.11") 1716 (30.14")Nb: 4 (43.5")

C'est à dire que la boucle prend 43.5 secondes.

Ça pourrait d'ailleurs être un critère discriminant de MPO, à nombre de pas égaux : celui qui va le plus vite !

Tout à fait ! Combien de fois je me suis fais avoir pa run code qui me paraissait plus malin et que j'espérais plus rapide ou efficace alors qu'il n'apportait aucun gain , voir au contraire une perte d'efficacité ou célérité par rapport au code plus simple mais plus court et donc bien mieux !

Bien vu l’utilisation de MOD.

Oui, je donnerai demain quelques explications, cela provient de la méthode de résolution que je détaillerai.

Bien vu l’utilisation de MOD.

Intéressant, combien de solutions trouves-tu pour 14725 en utilisant PRIM ?[/quote]

Oui, intéressant pour 220313 et 20220313, car dans le cas général l'utilisation que je fais de PRIM est licencieuse !

Comme le démontre parfaitement l'exemple avec 14725. Mais même avec 45 mon utilisation licencieuse est mise en défaut et je ne trouve pas pour ces deux nombre toutes les solutions !

En effet, contrairement à 14725, la décomposition en facteurs premiers de 20220313 ou 220313 ne conduit à aucun facteur multiple :
20220313 = 19*163*6529 et 220313 = 29*71*107
Pour ces deux nombres l'utilisation de PRIM est donc simple et directe et prend moins de deux secondes :

10 DESTROY ALL @ DELAY 0,0 @ D=1 @ P=1 @ INPUT C @ T=TIME
12 WHILE D @ GOSUB 20 @ P=P*D @ D=PRIM(C/P) @ END WHILE
14 D=C/P @ GOSUB 20 @ DISP "Nb:";N; @ GOSUB 22 @ END

20 N=N+1 @ DISP ABS(C/D-D)/2;
22 DISP '('&STR$(TIME-T)&'")'; @ RETURN

[RUN] 20220313 [END LINE] affiche sur mon HP-71B
10110156 (.15") 532104 (.39") 61944 (.69") 1716 (.98")Nb: 4 (1.14")

Mais pour 45 ou 14725, on obtient, avec ce code fallacieux, des résultats erronés :
[RUN] 45 [END LINE] affiche quatre solution au lieu de trois en répétant inutilement la solution n=6 :
22 (.12") 6 (.31") 6 (.51") 2 (.71")Nb: 4 (.86")

[RUN] 14725 [END LINE] affiche uniquement quatre solutions au lieu des six solutions attendues en répétant inutilement la solution n=1470:
7362 (.14") 1470 (.35") 1470 (.57") 378 (.71") 222 (1")Nb: 5 (1.14")

Cela provient bien évidemment du facteur multiple.
Donc, pour traiter convenablement le cas général, il faut un code un peu plus élaboré et je ne suis pas sûr que le gain de temps par rapport à la simple boucle FOR TO STEP / NEXT soit significatif.

Je n'ai pas essayé. L'idée serai de créer la liste des diviseurs au fur et à mesure que l'instruction PRIM nous fournit les facteurs

Comme je suis en train de travailler sur les HP-48/49/50G, avec les DOLIST, MAP... voici ma contribution pour cette question (uniquement pour les 49 et 50g car les 48G ne connaissent pas DIVIS). Attention également, il faut être en MODE CAS Exact (décocher Approx)

L'idée de filtrer la liste me parait un peu compliquée. Si j'avais une instruction DIVIS et REVLIST sur mon HP-28S, j'aurais listé les solutions avec un code qui ressemblerai à cela:

Code : Tout sélectionner

« DIVIS DUP REVLIST SWAP - 2 / 1 OVER SIZE 2 / SUB »

C'est d'ailleurs le code que j'ai actuellement dans mon HP Prime :

Code : Tout sélectionner

EXPORT QDD(n)
BEGIN
 LOCAL dv:=mat2list(idivis(n)); 
 LOCAL re:=(REVERSE(dv)-dv)/2;
 RETURN re[{1,SIZE(re)/2}];
END;

Bonjour, voici comment j'ai résolu ce petit problème.

npg220313.png

Très chouette ce schéma, il est tard, j'expliquerai ma méthode demain
Avec un peu de chance, je trouverai aussi à faire quelques schémas

[zpalm]

L'idée de filtrer la liste me parait un peu compliquée. Si j'avais une instruction DIVIS et REVLIST sur mon HP-28S, j'aurais listé les solutions avec un code qui ressemblerai à cela:

Code : Tout sélectionner

« DIVIS DUP REVLIST SWAP - 2 / 1 OVER SIZE 2 / SUB »

C'est d'ailleurs le code que j'ai actuellement dans mon HP Prime :

Code : Tout sélectionner

EXPORT QDD(n)
BEGIN
 LOCAL dv:=mat2list(idivis(n)); 
 LOCAL re:=(REVERSE(dv)-dv)/2;
 RETURN re[{1,SIZE(re)/2}];
END;

Tient, ça m’a donné l’idée d’un "one-liner" pour la HP Prime que l’on peut utiliser pour définir une fonction utilisateur à la place d’un programme :

Code : Tout sélectionner

UNION(ABS(mat2list(revlist(idivis(N))-idivis(N))/2))