MPO n°112 : fonction récursive

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

Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 498
Enregistré le : 05 mars 2020 20:45
Contact :

Re: MPO n°112 : fonction récursive

Message par Schraf »

Voici une version inspirée par le code d'@antoine :

- Transformer N en binaire, enlever le caractère '1' à gauche
- Initialiser a = 1, b = 0
- Parcourir les caractères c ('0' ou '1' -> 0 ou 1) de la droite vers la gauche
- A chaque étape faire b = b + a*c et a = 3*a - a*c
- Renvoyer 7*a - b

Exemple :

N = 574 s'écrit '1000111110' en binaire, on enlève le '1' à gauche '000111110'
On parcourt les caractères de la droite vers la gauche, c'est-à-dire '0' puis '1' 5 fois et '0' 3 fois

Valeurs successives prises par a, b et c :

Code : Tout sélectionner

a b c
1 0 0
3 0 1
6 3 1
12 9 1
24 21 1
48 45 1
96 93 0
288 93 0
864 93 0
2592 93 -
- Valeur retournée = 7*a - b soit 18051
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: MPO n°112 : fonction récursive

Message par C.Ret »

Schraf a écrit : 11 août 2022 15:34 Voici une version inspirée par le code d'@antoine :

Code : Tout sélectionner

- Transformer N en binaire, enlever le caractère '1' à gauche
- Initialiser a = 1, b = 0
- Parcourir les caractères c ('0' ou '1' -> 0 ou 1) de la droite vers la gauche
- A chaque étape faire  b = b + a*c et a = 3*a - a*c
- Renvoyer 7*a - b
[...]
on enlève le '1' à gauche '000111110'
Tiens, c'est la première fois que l'on poste un programme en pseudo-code pour nos MPO !
Bonne idée.

Sinon, le '1' à gauche, je l'ai volontairement gardé; c'est ce que j'ai appelé ci-dessus le 'bit d'arrêt'
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
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 498
Enregistré le : 05 mars 2020 20:45
Contact :

Re: MPO n°112 : fonction récursive

Message par Schraf »

@C.Ret : Je n'avais pas de calculatrice BASIC sous la main, c'est pour ça...

Voici une version pour HP-50g (à voir si fonctionne sur les HP 48 etc) :

Code : Tout sélectionner

U : « DUP 2 IDIV2 → N Q R 'IFTE(N==1,7,(3-R)*U(Q)-R' »

9 U donne 125
574 U donne 18051
Q = quotient entier de N par 2
R = Reste de la division de N par 2
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: MPO n°112 : fonction récursive

Message par C.Ret »

Pas mal, sur HP-28S la traduction est "presque" immédiate :

Code : Tout sélectionner

U: « DUP 2 / IP OVER 2 MOD → n q r « n 1 ==  7 « 3 r - q U * r - » IFTE » »
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
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: MPO n°112 : fonction récursive

Message par gege »

Bonjour,
Ceci est la police des MPO.
Les mains sur le clavier.
Papiers de garantie de la calculatrice.
Merci.

Savez-vous que vous circulez sur une voie réservée à l'optimisation et que vous roulez sans citer le nombre d'octets de vos solutions ???
Ok, pas de problème, j'espère que ça vous servira de leçon.

Bonne optimisation.
G.E.
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: MPO n°112 : fonction récursive

Message par C.Ret »

Je sais pas, j'avais pas l'impression d'aller trop vite ...
... je suivais mon ami Eric et dans la descente, avec trois piles LR1/E90 neuves... il m'a entrainé avec son idée en RPL...

Je trouve plus la facture... ni la garantie...
Je l'ai depuis septembre 1991... non jamais passer le moindre contrôle technique... ni compter les heures de fonctionnement d'ailleurs.

Je sais pas, en tout cas bien plus que 60 octets, je dirais que ce code fait 103.5 Bytes sur une HP-28S.

Mais c'est du matériel américain monsieur, c'est solide mais ça consomme un peu.

Rien avoir avec la délicatesse et la finesse d'une machine Ever-Sharp el-5150:
MPO 112 - Scientific SHARP EL-5150 (43 octets).gif
MPO 112 - Scientific SHARP EL-5150 (43 octets).gif (11.34 Kio) Vu 2476 fois

Image
Modifié en dernier par C.Ret le 13 août 2022 01:05, modifié 2 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.
FLISZT
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 655
Enregistré le : 09 mars 2022 19:14

Re: MPO n°112 : fonction récursive

Message par FLISZT »

Sur hp-50g :

− le programme de Schraf pèse 96,5 octets (+ 7 avec le nom 'U' ) ;
− le progrmme de C.Ret (28s) pèse, en effet, 103,5 octets (+ 7 avec le… ).

Un peu plus lourd, la solution sur hp-28s "tourne" sensiblement plus vite : résultat quasi-immédiat vs environ 1/2 seconde (tests avec 574).
Avec 2000 on a : résultat quasi-immédiat vs environ 1 seconde.
Même avec 100000, la solution de C.Ret donne le résultat quasi-immédiatement… vs environ 2 secondes !

Pas glop la fonction IDIV2 !
Bruno
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 498
Enregistré le : 05 mars 2020 20:45
Contact :

Re: MPO n°112 : fonction récursive

Message par Schraf »

@gege : soyez sympa Monsieur l'agent, je n'ai plus que 5 octets sur mon engin et c'est mon outil de travail 😇🙏🙏

Version intermédiaire pour HP-50g où seuls N et le reste R sont mis en variables locales :

Code : Tout sélectionner

U : « DUP 2 MOD → N R « N 1 == 7 « 3 R - N 2 / IP U * R - » IFTE » »
Pour la taille du programme, je ne sais plus s'il faut regarder dans FILES ou utiliser BYTES ? Dans FILES j'ai 96 octets et avec BYTES 102.

Si N = 1 000 000 le temps du calcul est de 2 secondes (contre 5 secondes avec la version IDIV2 précédente)
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: MPO n°112 : fonction récursive

Message par gege »

Bonjour,
Bravo messieurs !
En reprenant le programme d'antoine sur TI74, on n'a pas FRAC mais on gratte quand même des octets :

Code : Tout sélectionner

10 A=1:INPUT N
20 C=3-N/2+2*INT(N/2):N=(N-3+C)/2:A=A/C:B=(B-3+C)/C:IF N<>1 THEN 20
30 PRINT 7/A-B/A:PAUSE
(119 octets)

Pas besoin de VAC, le TI efface toutes les variables lors du RUN... (Grrrr...).

Je n'ai pas encore compris l'astuce géniale qui fait marcher le truc.
G.E.
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: MPO n°112 : fonction récursive

Message par C.Ret »

gege a écrit : 12 août 2022 12:31Pas besoin de VAC, le TI efface toutes les variables lors du RUN... (Grrrr...).
Ca c'est vraiment casse-pieds. Ma sœur s'était vue offrir cette TI-74 BAISCALC en cadeau d'encouragement pour ses bons résultats scolaires.
Immédiatement, je lui confiais mon carnet à spirale où j'avais noté tous les programmes que j'utilisais depuis la 4ième.

Malheureusement, ces programmes conçus pour un PC-1211 utilisaient beaucoup le AREAD et le fait que les registres (A à Z) sont globaux et partagés entre les programmes et fonctions que l'on charge en mémoire. Dans ce carnet, rares étaient les programmes autonomes et elle ne pu jamais utiliser sa TI-74 en mode BASIC comme j'utilisait mon PC-1211. Elle l'a gardé jusqu'au BAC mais elle a surtout utilisé la partie calculatrice et notamment les fonctions statistiques à une et deux variables ainsi que les regressions linéaires.

(119 octets) Tu as essayer l'astuce du SAVE "TOTO" ?

Sinon (ou si ça ne marche pas, hein!?), tu peux descendre à 105 octets avec ce code, basé lui aussi sur l'algorithme à antoine.

Code : Tout sélectionner

1 A=1:INPUT N:GOTO 3
2 IF N>INT(N) THEN B=B+A:A=2*A ELSE A=3*A
3 N=INT(N)/2:IF N<1 THEN PRINT 7*A-B:PAUSE ELSE 2
Image
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: MPO n°112 : fonction récursive

Message par C.Ret »

Pour ceux qui se font arrêter par la police des MPO en bas de chez eux dès qu'il dépasse le 30 ...

Une solution pour HP-41 qui peut certainement encore être optimisée, mais qui si l'on ne compte pas le label ALPHA et le END final (comme dans les MPO historiques) fait 30 octets:

Code : Tout sélectionner

001 LBL"MPO112
002   STO 02  STO 01  STO 00  ST/ 01  ST- 00
007   LBL 00
008     RCL 02  INT  2  X>Y?  GTO 09
013     ST/ 02  MOD  RCL 00  ST+ IND Y  ST+ 00
018   GTO 00
019   LBL 09
020     7  RCL 00  *  RCL 01  -
025 END
Petite info, pour doubler le volume d'une solution, il suffit simplement de lui ajouter exactement son volume.
Pour multiplier par 3 le volume d'une solution, il suffit d'ajouter deux fois son volume.
Il en est de même pour les valeurs des registres. :)

Image
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 »