Misez p'tit Optimisez n°53 : la suite de Syracuse

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
Tipoucet
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3665
Inscription : 10 janv. 2009 14:47

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Tipoucet » 28 mars 2014 20:43

Céline a écrit :Je n'ai pas encore de pocket mais j'ai étudié le manuel du sharp pc-1500, et j'ai essayé de programmer la suite de Syracuse en Basic. Quelqu'un pourrait-il le vérifier et me dire si il tourne correctement ? Bien sûr, aucune optimisation, je n'en suis pas là. Mais je me rends bien compte que même s'il tourne, mon programme est vraiment lourdingue !

Code : Tout sélectionner

10 : INPUT "ENTRER U(0) ";A
20 : C=1 : M=A
30 : IF A=1 THEN GOTO 100
40 : IF INT(A/2)-A/2=0 THEN GOTO 70
50 : A=3*A+1 : M=A
60 : GOTO 80
70 : A=A/2
80 : C=C+1
90 : GOTO 30
100 : PRINT "ALTITUDE : ";M;"VOL : ";C
Bonjour, pas testé mais joli programme en tous cas ! Pour quelqu'un qui n'a pas de pocket, c'est pas mal :wink:
Dominique

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5286
Inscription : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Marge » 28 mars 2014 21:07

Testé, ça tourne sur 1500. Mais U(1310) renvoie 16 et 146, l'altitude max. devrait être 1310, non ?

Pareil pour 27 : 16, 112.

A revoir, je crois.
3 hommes, 3 demis, un 3a... Magnéto, Serge !

« Boris », c'est juste Maurice enrhumé.

Céline
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 183
Inscription : 23 mars 2014 14:11

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Céline » 28 mars 2014 21:18

Ah zut. Je savais que je serais embêtée par l'absence de fonction MAX. Je le fait tourner manuellement mais je ne vois pas ce qui cloche.
TI-30 Galaxy
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime

Avatar de l’utilisateur
bernouilli92
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4318
Inscription : 21 nov. 2012 14:03
Localisation : Ile de France

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par bernouilli92 » 28 mars 2014 21:33

Céline a écrit :Ah zut. Je savais que je serais embêtée par l'absence de fonction MAX. Je le fait tourner manuellement mais je ne vois pas ce qui cloche.
Il suffit de remplacer à la ligne 50, M=A par IF M<A THEN M=A

Par ailleurs, pour être strict, pour n=1, la temps de vol est 0, or le programme précédent donne 1.
HP, Casio, Sharp, Psion, quelques TI et divers autres

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

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par C.Ret » 28 mars 2014 22:38

Céline a écrit :Je vous propose d'écrire un programme qui prend u(0) et renvoie
- le temps de vol : plus petit indice n tel que u(n)=1
- l'altitude maximale : valeur maximale de la suite.
HP-28S/C et autres RPL :

Code : Tout sélectionner

« 1 0                                @ Initialise MAX et TOF
  WHILE ROT DUP 1 >                  @ Boucle jusqu'à obtenir 1
  REPEAT
    IF 2 / DUP FP THEN 6 * 1 + END   @ Calcule terme suivant de la suite
    ROT OVER MAX                     @ Remet à jour MAX
    ROT 1 +                          @ Incrémente TOF
  END
  DROP                               @ Laisse dans la pile MAX et TOF
»     
SHARP PC-1211 (et autres TANDY ou SHARP PC-1210/1211/1212 avec trois ou quatre pile d'aileurs !)

Code : Tout sélectionner

10:" " AREAD N:T=0:M=N
20:IF N=1 PRINT "MAX:";M;"TOF:";T : END
30:PAUSE N:T=T+1:N=N/2:IF N<>INT N LET N=6N+1:IF N>M LET M=N
40:GOTO 20

BASIC Microsoft

Code : Tout sélectionner

10 INPUT " N = ";N:T=0:M=N
20 DO WHILE N>1
30 :  T=T+1 : IF MOD(N,2) THEN N=3*N+1 : M=MAX(M,N) : ELSE N=N/2
50 LOOP
60 PRINT "MAX:";M,"TOF:";T : END
Dernière édition par C.Ret le 28 mars 2014 23:03, édité 1 fois.
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
bernouilli92
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4318
Inscription : 21 nov. 2012 14:03
Localisation : Ile de France

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par bernouilli92 » 28 mars 2014 22:52

@C.Ret : comme d'habitude, tu m'épates, 87,5 octets, soit 15 de moins que mon programme. Chapeau!

EDIT : par contre il ne donne pas la bonne altitude pour les valeurs comme 2, 4 ou 8.
C'est facilement corrigeable en remplaçant le 1 du tout début par DUP
HP, Casio, Sharp, Psion, quelques TI et divers autres

Avatar de l’utilisateur
babaorhum
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 451
Inscription : 13 janv. 2013 20:44
Localisation : Marseille-est

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par babaorhum » 28 mars 2014 23:31

Hello,
chouettes propositions, pleins d'dées, super !

pour faire différent, on peut remarquer que la conjecture de Syracuse se prète assez bien à un traitement en binaire ; une occasion de faire travailler ma HP-16C (et mes neurones, je ne la pratique pas beaucoup celle là !). donc, donc :
en binaire lorsqu'un nombre est divisible par 2, il se termine par un 0 (évident), en utilisant la fonction "SR" je provoque un décalage (shift) à droite et pousse le digit de droite dans la retenue (carry). Si la carry est nulle, le nombre est divisé par 2 (je viens de retirer le 0 à droite).
Sinon, il faut que je le muliplie par 3 puis lui ajouter 1, pour ce faire, en binaire, le plus simple est d'ajouter au nombre d'origine, lui même décalé une fois à gauche avec "SL" (ce qui revient à le multiplier par 2) ...

en complétant avec les tests de temps de vol et d'altitude, ca donne un truc comme ca :

Code : Tout sélectionner

CLR REG      (initialisation, j'efface les registres)
BIN                (bascule en binaire pour le calucl)
LBL 1            (boucle principale)
ISZ                (incrément du registre I, temps de vol)
1
X<>Y
x=y                (test de fin de boucle : atteinte du 1)
GTO 3
RCL 0
x<>y
x>y                (test de l'altitude max en registre 0)
STO 0
ENTER
SHOW DEC  (affichage fugitif du chiffre en traitement, en décimal)
SR                 (décalage à droite, pousse digit de droite dans la 'carry')
F? 4               (test de la 'carry' ; c'est le flag n°4 de la 16C)
GTO 2
GTO 1           (carry = 0 c'était un nombre pair)
LBL 2            (carry = 1 traitement nombre impair)
R Down                           
ENTER
SL                  (décalage à gauche = x2)
+                    (ajouté au nombre initial = x3)
1
+                    (+1)
GTO 1
LBL 3            (sortie du programme)
RCL I            (rappel temps de vol)
RCL 0           (rappel altitude max)
DEC             (passage en décimal)
RTN
utilisation :
En mode DEC (décimal), on lance le programme avec R/S, sortie temps de vol en y, altitude max en x.

Ca sent le traitement en assembleur non ?
Qui s'y colle ? :wink:
Dernière édition par babaorhum le 28 mars 2014 23:40, édité 1 fois.
BaBaoRhum
HP J728,200LX,1000CX,75C,71B, 48GX,42s,41CX,35s,32E,32Sii,28S,22s,21,16C,11C,12Cp
Sharp PC- E500,1600,1500,1350,1261,1245
Casio FX-502P,602p,850P,3900P,4000P
TI-74&92 ; Canon X-07 ; Panasonic HHC RL-H1400 ; TANDY EC-4026

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

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par C.Ret » 28 mars 2014 23:38

@bernouilli92

Pas sûr qu'il faille corriger, j'obtiens bien les temps de vols même pour les puissances de 2. Contrairement au programme BASIC, le MAX dans le prmg RPL est mis à jour à chaque itération et donc sa valeur initiale n'a pas d'importance.
Contrairement au cas de l'astuce du programme BASIC qui ne teste la validité du max. lors de valeurs impaires !

P.S.: J'ai une autre version RPL qui permet éventuellement de conserver les valeurs intermédiaires (il suffit d'insérer un DUP avant l'instruction LIST-> :

Code : Tout sélectionner

« {} 
  WHILE OVER 1 >
  REPEAT 
    OVER +                          @ Ajoute élément à la liste  
    OVER 3 * 1 +                    @ Cas élément impair
    ROT 2 /                         @ Cas élément pair
    LAST MOD ROT ROT IFTE           @ Test parité et choix du cas
  END
  LIST-> ->ARRY RNRM LAST SIZE +    @ Affiche { max tof }
»
A utiliser sur les HP48/50 pour tracer la courbe !
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
bernouilli92
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4318
Inscription : 21 nov. 2012 14:03
Localisation : Ile de France

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par bernouilli92 » 28 mars 2014 23:45

C.Ret a écrit :@bernouilli92

Pas sûr qu'il faille corriger, j'obtiens bien les temps de vols même pour les puissances de 2. Contrairement au programme BASIC, le MAX dans le prmg RPL est mis à jour à chaque itération et donc sa valeur initiale n'a pas d'importance.
C'est le max qui n'est pas bon, par exemple pour 8 en entrée, le max donné est 4.
Le max est calculé à chaque iteration mais après le calcul du terme suivant, d'où la nécessité d'initialiser sa valeur avec la valeur en entrée.
HP, Casio, Sharp, Psion, quelques TI et divers autres

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

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par C.Ret » 29 mars 2014 00:08

Ah! OK merci effectivement il y a un décallage et le max est faux !

Heureusement que je comprends vite quand on m'explique longtemps !

Donc, voici le programme correct grâce à bernouilli92

Code : Tout sélectionner

« DUP 0                              @ Initialise MAX et TOF
  WHILE ROT DUP 1 >                  @ Boucle jusqu'à obtenir 1
  REPEAT
    IF 2 / DUP FP THEN 6 * 1 + END   @ Calcule terme suivant de la suite
    ROT OVER MAX                     @ Remet à jour MAX
    ROT 1 +                          @ Incrémente TOF
  END
  DROP                               @ Laisse dans la pile MAX et TOF
»     
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
babaorhum
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 451
Inscription : 13 janv. 2013 20:44
Localisation : Marseille-est

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par babaorhum » 29 mars 2014 00:23

Bô !!!
BaBaoRhum
HP J728,200LX,1000CX,75C,71B, 48GX,42s,41CX,35s,32E,32Sii,28S,22s,21,16C,11C,12Cp
Sharp PC- E500,1600,1500,1350,1261,1245
Casio FX-502P,602p,850P,3900P,4000P
TI-74&92 ; Canon X-07 ; Panasonic HHC RL-H1400 ; TANDY EC-4026

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5286
Inscription : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Marge » 29 mars 2014 03:54

"WHILE ROT DUP 1"

C'est ça qui m'handicape dans le RPL... je comprends l'anglais mais rien n'y fait.
3 hommes, 3 demis, un 3a... Magnéto, Serge !

« Boris », c'est juste Maurice enrhumé.

Avatar de l’utilisateur
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3292
Inscription : 06 sept. 2011 14:57
Localisation : Normandie

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Hobiecat » 29 mars 2014 09:12

Marge a écrit :"WHILE ROT DUP 1"

C'est ça qui m'handicape dans le RPL... je comprends l'anglais mais rien n'y fait.
+1 !
La solution est élégante, mais heureusement qu'il y a les commentaires à côté !

Céline
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 183
Inscription : 23 mars 2014 14:11

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Céline » 29 mars 2014 09:39

Bravo à tous pour vos propositions.
Le traitement en binaire sur hp16c il fallait y penser.
Reste plus qu'à démontrer la conjecture maintenant.
C.Ret a écrit :SHARP PC-1211 (et autres TANDY ou SHARP PC-1210/1211/1212 avec trois ou quatre pile d'aileurs !)

Code : Tout sélectionner

10:" " AREAD N:T=0:M=N
20:IF N=1 PRINT "MAX:";M;"TOF:";T : END
30:PAUSE N:T=T+1:N=N/2:IF N<>INT N LET N=6N+1:IF N>M LET M=N
40:GOTO 20
En voyant ce programme il me semble que la syntaxe sur les sharp a l'air assez souple : pas besoin de THEN après IF par exemple.
Est-ce que deux instructions séparées par deux points après un THEN font partie du IF THEN ou seulement la première ?

Oh là là j'ai vraiment hâte d'avoir un pocket moi :roll:
TI-30 Galaxy
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime

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

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par C.Ret » 29 mars 2014 09:59

OUi Céline, c'est bien cela, le BASIC des SHARP possède quelques spécificités. D'aileurs c'était courant à l'époque, tous les BASIC avaient quelques variations et régles de syntaxe qui rendaient d'ailleurs parfois l'adaptation d'un programme assez compliqué d'une machine à l'autre !


En plus, dans un MPO, on utilise justement ce type de "comportement spécifique" pour gagner quelques octets et parfois une astuce ou deux.

Pour ce qui est du SHARP, iln'y a pas de clause ELSE dans les structures IF ... THEN ... et si la condition est fausse, le BASIC continu à la ligne suivante. Ce qui fait que à la suite d'un THEN (ou autre instruction placée après un IF) toutes les instructions sont exécutées. Y compris les autres clauses IF ... THEN

Ainsi, 10:IF A=1 IF B=2 PRINT A,B est équivalent à la version "microsoft" de 10:IF (A=1) AND (B=2) THEN PRINT A,B


Lors de mon précèdent post, j'ai oublié la version pour HP-41C et autre RPN avec gestion "évoluée" de la pile. Le programme n'utilise pas d'autres registres que ceux de la pile.

Code : Tout sélectionner

                        t:   z:   y:      x:                                 t:   z:   y:      x: 
                                                                                                  
001 LBL "SYRACUSE                          n         016 x==0 ?                          n even ? 
002 0                              n       0         017 GTO 00                                   
003 X<> Y                          0       n         018 Clx                t+1    m  n/2       0 
004 ENTER^                    0    n       n         019 6                  t+1    m  n/2       6 
005 ENTER^               0    n    n       n         020 *                  t+1  t+1    m      3n 
                                                     021 1                  t+1    m   3n       1 
006 LBL 00               t    m    n       ~         022 +                  t+1  t+1    m    3n+1 
007 Clx                  t    m    n       0         023 x>y ?                            n'>m' ? 
008 1                    t    m    n       1         024 STO Y                         m'         
009 x==y ?                            1==n ?         025 ENTER^             t+1   m'   n'      n' 
010 GTO 01                                           026 PSE                            Affiche n 
011 ST+ T              t+1    m    n       1         027 GTO 00                                   
012 ST+ X              t+1    m    n       2                                                      
013 /                  t+1  t+1    m     n/2         028 LBL 01               t    m    1       1 
014 ENTER^             t+1    m  n/2     n/2         029 RDN                                      
015 FRC                t+1    m  n/2       f         030 RDN                                      
                                                         .END.                          t       m 
A la fin de l'éxecution, le programme affiche MAX, il faut presser sur la touche [x<>y] pour lire le temps de vol TOF.
Dernière édition par C.Ret le 29 mars 2014 10:30, édité 2 fois.
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Répondre

Revenir vers « Tous les Pockets »