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
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5217
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

Re: MPO n°112 : fonction récursive

Message par bernouilli92 »

Voici ma version pour hp48 sans réflexion aucune :

Code : Tout sélectionner

U : « → N 'IFTE(N==1,7,IFTE(FP(N/2)==0,3*U(N/2),2*U((N-1)/2)-1))' »
Elle donne 18051 pour U(574).
HP, Casio, Sharp, Psion, quelques TI et divers autres
Zebulon
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 569
Enregistré le : 28 juin 2022 10:21

Re: MPO n°112 : fonction récursive

Message par Zebulon »

Oui gege j'espère que tu ne l'as pas mal pris. Ton programme est très lisible et encore une fois je n'aurais pas pensé à faire usage des GOSUB et ainsi profiter de la pile d'appel du basic. :P

D'accord pour les spaghettis j'adore les pâtes. :wink:
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,
Aucun souci, j'aime bien cette polémique (Victor), on rigole ! Je fais exprès de chercher des trucs qui ne se programment bien qu'avec des GOTO...
Ici ce n'est pas évident, mais impossible de ne pas taquiner un peu !

Avec le tableau, et tant qu'à faire en piquant l'idée d'antoine, ça donne sur TI74 (139 octets) :
10 INPUT N:I=1:U=7:DIM L(20)
20 M=INT(N/2):L(I)=N-2*M:N=M:I=I+1:IF N>1 THEN 20
30 I=I-1:U=(3-L(I))*U-L(I):IF I>1 THEN 30
40 PRINT U:PAUSE

Hop ! Et oui, on pourrait utiliser WHILE et FOR :-)
G.E.
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 »

Bonjour,
gege a écrit : 06 août 2022 09:42 En comprimant le programme sur X07 on tombe à 90 octets :
(…)
Grattons les octets...
Oui, je me souviens qu'en supprimant tous les espaces, on pouvait gagner des octets.
Et en remplaçant le PRINT par un « ? », cela ne permet-il pas d'en gagner encore qq uns ?

En revanche (j'ai cherché y'a peu), je ne sais plus comment on peut avoir l'équivalent en RPL d'un MEM (mém totale dispo) ou d'un BYTES (taille d'un prog.) sur le X-07.

Faut-il créer une "fichier RAM" avec FSET + taille, puis sauvegarder son prog avec SAVE dans cet espace ?
Ensuite avec DIR, on doit obtenir la taille RAM restante dans cette zone et par déduction la talle du prog sauvegardé.

Procédure un peu longue et indirecte… mais je ne vois que cela. (??)
Souvenirs d'une autre vie… :)
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
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 »

FLISZT a écrit : 07 août 2022 05:04Hop ! Et oui, on pourrait utiliser WHILE et FOR :-)
Bof! Pour une fois que ton programme ne fait que 4 lignes et qu'il n'y a pas de spaghettis (les seuls GOTO pointent vers le début de la ligne) je ne suis pas sûr que ce soit utile ! :mrgreen: Les GOTOs c'est bien - C.Ret la girouette :mrgreen:

Pour le WHILE j'ai tout de suite vu où en mettre (les GOTO qui pointent vers l'autre bout de la ligne). Alors j'ai sorti mon Ti-74 BASICALC. Et j'ai bien rit !

Mais pour les FOR, tu peux te vanter de m'avoir fait réfléchir, j'ai pas tout de suite vu ! Pour tant c'est évidant, il y a même d'ailleurs déjà le compteur I dans ton code ! Pas bien réveillée la girouette ce matin.

Par contre, je ne suis pas d'accord avec le décompte des octets, sur mon TI-74 ton code recopier mot à mot donne un FRE(1) de 147. Comme cette valeur inclut 11 octets nécessaires à la mémorisation du programme, cela signifie que ton programme ne fait que 136 octets (et non 139 comme indiqué).

Bon, il y a quand même ce tableau DIM L(20) qui prend pas mal d'octets et que l'on ne compte pas.
Mais est-il nécessaire ?


Suggestion:

Code : Tout sélectionner

1 P=1:U=7:INPUT N 
2 IF N>=2 THEN N=INT(N)/2:P=2*P+N-INT(N):GOTO 2
3 IF P=1 THEN PRINT U:PAUSE:END ELSE IF P>INT(P) THEN U=2*U-1 ELSE U=3*U
4 P=INT(P)/2 :GOTO 3
Variables:
N : indice n de la suite u(n)
U: valeur de la suite u(n)
P: Bits de parité successifs de la décomposition de n et bit d'arrêt. C'est le bit (-1) qui a chaque étape indique la parité du n/2° décomposé. C'est dire la première décimale qui est soit 0 ( n/2° pair) ou 5 (n/2° impair).
Comme le TI-74 travaille sur 13 chiffres décimaux, P a donc le même rôle qu'un tableau DIM L(43)

Conclusion:
On obtient un code qui à un ou deux octets près a la même taille que le code précèdent de gege avec cependant l'absence d'un tableau DIM L(20) très gourmant en octets pour juste mémorisé à chaque étage un seul bit.
Par ailleurs, les relations qui définissent la suite U₀=7, U=2U-1 et U=3U sont clairement visibles dans le code qui peut être adapté à une autre suite.

Je trouve que u(12884901887)≈8.589935E+10 ce qui me parait correct pour une machine travaillant sur 46 bits soit 13.8 chiffres décimaux.
Une machine non BASIC d'une marque historiquement concurrente me confirme que u(12884901887)=8599345921 exactement.
Modifié en dernier par C.Ret le 07 août 2022 09:36, modifié 12 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 »

Merci C.Ret !

… j'avais oublié les parenthèses : Syntax Error ! :lol:
Je me suis alors dit que je confondais avec Linux : free --m

Cela dit free() donne la quantité de RAM dispo, mais pas la taille d'un programme, si je ne m'abuse (?).
La page 129 du manuel de réf. BASIC (bleu) n'est pas très explicite et j'ai la flemme de sortir le X-07, le transfo, etc. :oops:
:D
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
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 »

Oui, il faut relever la quantité de mémoire disponible avant de saisir ou charger son programme et fonctionner par différentiel.

Attention, FREE(0) ne fonctionne pas, ça c'est de l'Unix ou du Linux. Sur le Canon X 07 la commande est FRE(n) avec un seul E.
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 »

… ah oui quand même ! … je venais juste de refermer le manuel ! :roll:

Faut que je prenne qq calories et un peu de repos ! :)

Encore merci C.Ret
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
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,
Wow super C.Ret, on va avoir du mal à battre cette version !
Pour la taille de mon programme sur TI74, j'avais fait FRE(1) avant de le taper, après un NEW, et ça renvoyait 23 ?
Grrr comment optimiser ce 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 : 07 août 2022 19:52Grrr comment optimiser ce truc ??
J'ai eut le même type de blague ce matin, j'ai tapé ton programme. Puis j'ai voulu voir ce qui ce passe lorsque l'on retire les espaces entre les mots clefs. Mauvaise idée, la TI-74 ne reconnait plus les instructions mais tout est gardé en mémoire sous forme de suite de caracpresqutères.
Si on lance par RUN, il y a dix errors de Syntax par ligne. Et FRE(1) renvoyait déjà le double de 146 c'est passé à 210 octets.

Alors pour corriger, j'ai utilisé INS et j'ai remis les espaces où il faut. Bien. Le code fonctionne, par contre chaque pression sur INS a visiblement inséré des blocks entiers de caractères null et invisibles (comme quand on insère des instructions sur une HP-41C visiblement). Le programme fonctionnait de nouveau bien, mais FRE(1) indiqué plus de 350 octets !

Et je me suis posé la même question que toi.

Une façon de faire c'est la commande NEW qui va remettre de l'ordre. Mais il faudra ressaisir à nouveau l'intégralité du programme. Bof.

J'ai trouvé une astuce, il n'y a pas de commande pour demander à la TI-74 de remettre de l'ordre (ramasse miette ou un quelconque packing).
Par contre, c'est sûr, en toute logique, elle effectuera le 'packing' et 'ramassera les miettes' avant toute opération de sauvegarde du programme. C'est primordiale, les capacités et performances des sauvegardes et les interfaces de l'époque imposent de mettre de l'ordre et d'optimiser.

Je n'ai pas l'interface appropriée, mais j'ai lançé un SAVE "TOTO" qui très vite m'indique une erreur E19 File error.
Mais ça marche, elle a d'abord 'packé' et 'ramassé ses miettes' avant même de se rendre compte qu'il n'y avait pas d'interface.

Héhé, de 350 octets , je suis revenu à 146 en un clin d'œil.



Sinon, battre mon code qui fait quand même 146 octets, c'est facile ! Encore faut-il trouver un pocket au BASIC moins volubile.

Je reviens avec d'autres suggestions mardi soir.
Ce soir c'est relâche. Je suis épuisé, je viens de calculer manuellement (sans programme) que u(20890720927744)=3027258699305175271449.
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,
Très intéressant l'astuce du SAVE, jamais entendu parler...
Ok je vérifie ton 20890720927744 !

Pour gagner des onctets, un Basic plus économique, peut-être dans sa façon de stocker les mots-clef et numéros de lignes, pourrait marcher mais sur l'algorithme je crois que c'est bien optimisé à présent.

On peut toujours autoriser le LMS...
Sans aller vers les HP48 ou équivalents permettant la vraie récursion ?
Qui tente la TI-57 ?
A+
G.E.
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 »

Bonjour,

Cette astuce du SAVE me fait penser à ce que je me suis dit après avoir écrit, à propos du X-07, ceci :
FLISZT a écrit : 07 août 2022 05:04 Faut-il créer une "fichier RAM" avec FSET + taille, puis sauvegarder son prog avec SAVE dans cet espace ?
Ensuite avec DIR, on doit obtenir la taille RAM restante dans cette zone et par déduction la talle du prog sauvegardé.
… SAVE doit être suivi d'un nom ET ce nom va prendre de la place en mémoire !

Bien sûr, si l'on connaît tous les arcanes de son pocket, on pourra déduire la taille en mémoire occupée par le nom…
Pourquoi faire simple ? :wink:

Sinon… un « ? » à la place d'un PRINT (du moins sur X-07)… ça ne permet pas de grapiller qq octets ?
.
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
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,
Non, lorsqu'on tape un "?" dans un programme il est traduit en PRINT, en tout cas c'est ce qu'on voit lors de LIST.

@C.Ret : c'est bien 3027258699305175271449, mais pourquoi ce 19 ??
G.E.
antoine
Fonctionne à 75 bauds
Fonctionne à 75 bauds
Messages : 14
Enregistré le : 04 août 2022 10:18

Re: MPO n°112 : fonction récursive

Message par antoine »

Bonjour,

Depuis mes vacances à la montagne, où j'ai emporté pour tout pocket un emulateur sur smartphone, la place dans le sac à dos étant comptée,
Je vous propose une seconde version en vrai basic pour PB-100 qui totalise 83 octets de mémoire et n'utilise que quatre variables, au prix de quelques calculs tout de même :

Code : Tout sélectionner

10 VAC:A=1:INPUT N
20 C=1-2*FRAC(N/2):N=(N-1+C)/2:A=A/(2+C):B=(B+1-C)/(2+C):IF N≠1 THEN 20
30 PRINT 7/A-B/A
antoine
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 »

Bonsoir,

J'allais posté un truc long et compliqué...

Heureusement antoine m'a devancé avec une idée de génie !

antoine a écrit : 09 août 2022 17:59

Code : Tout sélectionner

10 VAC:A=1:INPUT N
20 C=1-2*FRAC(N/2):N=(N-1+C)/2:A=A/(2+C):B=(B+1-C)/(2+C):IF N≠1 THEN 20
30 PRINT 7/A-B/A
Voici donc l'adaptation pour SHARP PC-1211 qui ne fait que 60 octets:

Code : Tout sélectionner

1:A=1,B=0:INPUT N
2:N=INT N/2:IF N>=1 LET P=N>INT N,B=B+AP,A=3A-AP:GOTO 2
3:PRINT 7A-B

J'avais préparé pleins de choses pour SHARP PC-1211 et SHARP EL-5150 qui tombent à l'eau du coup.
Mais l'idée d'antoine est trop géniale.

Dire que je suis passé à deux doigts:
u(574)='3*(2*(2*(2*(2*(2*(3*(3*(3* 7 )))-1)-1)-1)-1)-1)'
u(574)='3*(2*(2*(2*(2*(54* 7 -1)-1)-1)-1)-1)'
u(574)='3*(2*(2*(2*(108* 7 -3)-1)-1)-1)'
u(574)='3*(2*(2*(216* 7 -7)-1)-1)'
u(574)='3*(2*(432* 7 -15)-1)'
u(574)='3*(864* 7 -31)'
u(574)='2592* 7 -93'
u(574)=1851.

Evidemment, le calcul se fait en réalité dans l'autre sens :

Code : Tout sélectionner

(initial)  u(574)=u(574)                                               A=1, B=0   u(574)=   1*u(574)-0
( pair )   u(574)=3*u(287)                                   p=0       A=3, B=0   u(574)=   3*u(287)-0
(impair)   u(574)=3*(2*u(143)-1)                             p=1       A=6, B=3   u(574)=   6*u(143)-3
(impair)   u(574)=3*(2*(2*u(71)-1)-1)                        p=1      A=12, B=9   u(574)=  12*u( 71)-9
(impair)   u(574)=3*(2*(2*(2*u(35)-1)-1)-1)                  p=1      A=24, B=21  u(574)=  24*u( 35)-21
(impair)   u(574)=3*(2*(2*(2*(2*u(17)-1)-1)-1)-1)            p=1      A=48, B=45  u(574)=  48*u( 17)-45
(impair)   u(574)=3*(2*(2*(2*(2*(2*u(8)-1)-1)-1)-1)-1)       p=1      A=96, B=93  u(574)=  96*u( 8 )-93
( pair )   u(574)=3*(2*(2*(2*(2*(2*3*u(4)-1)-1)-1)-1)-1)     p=0     A=288, B=93  u(574)= 288*u( 4 )-93
( pair )   u(574)=3*(2*(2*(2*(2*(2*3*3*u(2)-1)-1)-1)-1)-1)   p=0     A=864, B=93  u(574)= 864*u( 2 )-93
( pair )   u(574)=3*(2*(2*(2*(2*(2*3*3*3*u(1)-1)-1)-1)-1)-1) p=0    A=2592, B=93  u(574)=2592*u( 1 )-93
(unitaire) u(574)=3*(2*(2*(2*(2*(2*3*3*3*  7 -1)-1)-1)-1)-1) =          18051           =2592*   7  -93
gege a écrit : 08 août 2022 13:21@C.Ret : c'est bien 3027258699305175271449, mais pourquoi ce 19 ??
C'est un truc qui finalement ne marche pas, j'ai passé pas mal de temps à tenter de trouver une relation algébrique directe. Ou presque. Il y avait comme une décomposition en facteurs premiers qui, un moment , m'a semblée fournir une formule directe...

Mais non voilà je perds mon temps à des recherches perdues. Au lieu de bien observer ce que j'ai déjà sous les yeux.
C'est tout moi.
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 »