Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

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
charognard
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4412
Enregistré le : 06 juin 2007 19:28
Localisation : Indre et loire
Contact :

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par charognard »

cgh a écrit :Sur HP41, on peut encore simplifier:

Code : Tout sélectionner

  01 LBL "MCC"
  02 LBL 00
  03 10
  04 -
  05 90
  06 X<>Y
  07 X>Y?
  08 RTN
  09 21
  10 +
  11 XEQ 00
  12 XEQ 00
  13 END
Etonnant comment ça peut fonctionner avec des valeurs entrainant plus de 8 niveau de pile gosub ???
Avatar du membre
charognard
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4412
Enregistré le : 06 juin 2007 19:28
Localisation : Indre et loire
Contact :

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par charognard »

Je viens de lire l'explication de zpalm. Etonnant que la 41 ne génère pas une erreur et enquille les XEQ hors pile !
-200 ne lui pose aucun problème
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2918
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par zpalm »

charognard a écrit :Etonnant comment ça peut fonctionner avec des valeurs entrainant plus de 8 niveau de pile gosub ???
Sur la HP-41 on peut avoir plus de 6 niveaux d’appels de sous-programmes, mais du dernier niveau on ne remontera que de 6. Le programme s’arrête avant d’être remonté au niveau d’appel initial et affiche la valeur courante. Ça marche car c’est toujours 91.
cgh
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2142
Enregistré le : 30 août 2011 12:23
Localisation : Vous êtes ici -> .

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par cgh »

charognard a écrit :Je viens de lire l'explication de zpalm. Etonnant que la 41 ne génère pas une erreur et enquille les XEQ hors pile !
-200 ne lui pose aucun problème
Les ingénieurs d'HP qui développaient coconut ont dû utiliser la fonction 91 de McCarthy pour tester :mrgreen:
Il y a ceux qui voient les choses telles qu'elles sont et se demandent pourquoi, et il y a ceux qui imaginent les choses telles qu'elles pourraient être et se disent... pourquoi pas? - George Bernard Shaw
J'adore parler de rien, c'est le seul domaine où j'ai de vagues connaissances ! - Oscar Wilde
Ce n'est pas parce que les choses sont difficiles que nous n'osons pas. C'est parce que nous n'osons pas que les choses sont difficiles. - Sénèque
Avatar du membre
pir2
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4642
Enregistré le : 31 oct. 2006 15:08
Localisation : 67310 Westhoffen
Contact :

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par pir2 »

cgh a écrit :
zpalm a écrit :Sur la HP-41 la pile de retour des sous-programmes a une profondeur de 6, ce qui veut dire que l’on ne peut revenir que 6 niveaux en arrière. Donc ça ne devrait pas marcher pour n <47!!

En fait on est sauvé car pour tout n <=90 la valeur est 91, donc lorsque l’on calcule par ex. M(5) on dépasse le nombre de niveaux autorisés, on ne revient donc pas au début des appels comme on peut le voir en passant en mode programme : le programme s’est arrêté sur le dernier RTN du programme. Mais la 41 affiche la bonne valeur : 91.
Il va falloir utiliser la programmation synthétique :idea: pour augmenter la pile de retour des sous-programmes. Comme quoi la présentation faite par gégé lors des pocketicaires s'avère utile :D
Intéressant, comment on fait pour augmenter la taille de cette pile?
Image
Image
cgh
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2142
Enregistré le : 30 août 2011 12:23
Localisation : Vous êtes ici -> .

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par cgh »

pir2 a écrit :Intéressant, comment on fait pour augmenter la taille de cette pile?
Le pointeur programme et les pointeurs de retour sont stockés dans les registres b et a (adresses 12 et 11 respectivement). Avec un manipulation astucieuse X<>, on peut les mémoriser dans des registres Rxx et donc les rappeler ultérieurement; on a ainsi une pile de retours "presque" infinie. On doit utiliser X<>, car STO et RCL "normalisent" le registre X, ce X<> ne fait pas!

Il y a un programme qui fait cela dans le PPC-ROM.

EDIT: Ce sont les fonctions LR et SR du PPC-ROM.

EDIT2: Un petit lien pour voir ce que c'est: Programmation Synthétique
On peut lire aussi Synthetic Programming par W.C.Wickes (la référence !).
Il y a ceux qui voient les choses telles qu'elles sont et se demandent pourquoi, et il y a ceux qui imaginent les choses telles qu'elles pourraient être et se disent... pourquoi pas? - George Bernard Shaw
J'adore parler de rien, c'est le seul domaine où j'ai de vagues connaissances ! - Oscar Wilde
Ce n'est pas parce que les choses sont difficiles que nous n'osons pas. C'est parce que nous n'osons pas que les choses sont difficiles. - Sénèque
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par Gilles59 »

C.Ret a écrit :
Gilles59 a écrit :RPL/50 (et 48 ?)

Code : Tout sélectionner

« → n 'IFTE(n>100 , n-10 , M(M(n+11)))' » 'M' STO
Testé sur HP50
C'est exactement la version que j'allais proposé pour HP28S.
C'est une simple traduction de la définition de la fonction.

Ce code fonctionne aussi sur HP28C.

Comme le souligne Charo, c'est trop facile avec des langage supportant les appels récursifs.


Par contre, si on demande la valeur de M(0), il faut à ma pauvre HP-28S plus de 13 secondes, si c'est simple à programmé, ce n'est pas optimisé par rapport à la vitesse.
Beaucoup plus rapide en 'logique pile' en effet est :

Code : Tout sélectionner

« DUP 100 > { 10 - } { 11 + M M } IFTE » 'M' STO
Variation plus 'traditionelle' :

Code : Tout sélectionner

«
 IF DUP 100 > THEN
  10 -
 ELSE
  11 + M M
 END
»
'M' STO
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par Gilles59 »

Version Casio 602P en 9 pas :

Code : Tout sélectionner

 
 MinF 10 M-F 91 x≥F X↔MF X↔MF
Euh, j'ai pas la 602 sous la main mais çà doit marcher lol
Bon ca serait plus simple si les tests avait un inverse :O Mais faut vous faire réflechir un peu ;)
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
billaj
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 383
Enregistré le : 09 avr. 2005 17:48
Localisation : Brest
Contact :

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par billaj »

zpalm a écrit :Sur la HP-41 la pile de retour des sous-programmes a une profondeur de 6, ce qui veut dire que l’on ne peut revenir que 6 niveaux en arrière. Donc ça ne devrait pas marcher pour n <45!!

En fait on est sauvé car pour tout n <=90 la valeur est 91, donc lorsque l’on calcule par ex. M(5) on dépasse le nombre de niveaux autorisés, on ne revient donc pas au début des appels comme on peut le voir en passant en mode programme : le programme s’est arrêté sur le dernier RTN du programme. Mais la 41 affiche la bonne valeur : 91.
Autrement dit : Récursivité terminale FTW ! :mrgreen:
Quand Chuck Norris joue à Nintendogs, il a automatiquement armes et munitions infinies.
Chuck Norris peut revenir en arrière dans Super Mario Land.
Chuck Norris utilise exclusiment des calculatrices Texas Instruments.
billaj
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 383
Enregistré le : 09 avr. 2005 17:48
Localisation : Brest
Contact :

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par billaj »

Et deux programmes pas optimisés pour Casio fx-6800G...pas encore testés...le verdict dans 30 minutes ! :D

Version récursive :

Code : Tout sélectionner

Ans>100=>Goto 1:
Ans+11:
Prog 0:
Prog 0:
Goto 2:
Lbl 1:
Ans-10:
Lbl 2
Version itérative :

Code : Tout sélectionner

1->C:
Lbl 0:
Ans>100=>Goto 1:
Ans+11:
C+2->C
Goto 2:
Lbl 1:
Ans-10:
Lbl 2:
Dsz C:Goto 0:
Ans:
edit : oups, ratage du Dsz...
edit 2 : ça marche :) ; enfin, la version récursive ne va pas bien loin. Je peux aussi enlever le Ans final sur la version itérative. Je suis en train de finir une version HP 25, je la porterai ptêtre tt à l'heure.
Modifié en dernier par billaj le 26 oct. 2011 20:21, modifié 2 fois.
Quand Chuck Norris joue à Nintendogs, il a automatiquement armes et munitions infinies.
Chuck Norris peut revenir en arrière dans Super Mario Land.
Chuck Norris utilise exclusiment des calculatrices Texas Instruments.
Avatar du membre
pir2
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4642
Enregistré le : 31 oct. 2006 15:08
Localisation : 67310 Westhoffen
Contact :

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par pir2 »

Si on commence à tricher ...

Code : Tout sélectionner

100
x<>Y
X<=Y?
101
10
-
Image
Image
Avatar du membre
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3626
Enregistré le : 06 sept. 2011 14:57
Localisation : Normandie

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par Hobiecat »

Il a été vite celui-là de misez p'tit !! J'arrive trop tard....
Ah si, il reste la 15C !!
C'est pas gagné à faire rentrer dans la 15C... 8O
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par Gilles59 »

pir2 a écrit :Si on commence à tricher ...

Code : Tout sélectionner

100
x<>Y
X<=Y?
101
10
-
:D Même idée que mon prog 602P au dessus.
C'est pas tricher, c'est réfléchir
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
charognard
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4412
Enregistré le : 06 juin 2007 19:28
Localisation : Indre et loire
Contact :

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par charognard »

en Basic par itérations nous pourvons encore gagner

Code : Tout sélectionner

1 R=1:INPUT N
2 IF R LET R=R+1-2*(N>100),N=N+11-21*(N>100):GOTO 2
3 PRINT N
je mets un compteur dedans pour voir

Code : Tout sélectionner

1 R=1,C=0:INPUT N
2 IF R LET R=R+1-2*(N>100),N=N+11-21*(N>100),C=C+1:GOTO 2
3 PRINT N,C

Pour 1 ça donne 201 itérations pour 99, cinq
Bref ça donne 2*(100-N)+3 itérations

Code : Tout sélectionner

100   	99	   98	   97	   96      .........
				
1:100	1: 99	1: 98	1: 97	1: 96
2:111	2:110	2:109	2:108	2:107
3:101	3:100	3: 99	3: 98	3: 97
4:91	 4:111	4:110	4:109	4:108
	     5:101	5:100	5: 99	5: 98
	     6:91	 6:111	6:110	6:109
		          7:101   7:100	7: 99
		          8:91	 8:111	8:110
			               9:101	9:100
			               10:91	10:111
				                    11:101
				                    12:91
Donc nous pouvons faire par une boucle FOR NEXT ça sera plus rapide

Code : Tout sélectionner

10 INPUT N:IF N>101 PRINT N-10
20 FOR A=1 TO 2*(100-N)+3:IF N>100 LET N=N-10:GOTO 40
30 N=N+11
40 NEXT A:PRINT N
En embarquant la condition nous gagnons encore du temps

Code : Tout sélectionner

10 INPUT N:IF N>101 PRINT N-10
20 FOR A=1 TO 2*(100-N)+3:N=N+11-21*(N>100):NEXT A:PRINT N
Aller en 1 ligne avec supression du premier IF inutile dans le cas SHARP

Code : Tout sélectionner

10 INPUT N:FOR A=1 TO 2*(100-N)+3:N=N+11-21*(N>100):NEXT A:PRINT N
Sur SHARP les instructions en boucle sont executés au moins une fois (testé ici sur 1251)

et pour les nombres décimaux, cette ruse

Code : Tout sélectionner

10 INPUT N:FOR A=-2*(100-N)-3 to -1:N=N+11-21*(N>100):NEXT A:PRINT N
Je développe pour 4 octets de moins

Code : Tout sélectionner

10 INPUT N:FOR A=-203+2*N TO -1:N=N+11-21*(N>100):NEXT A:PRINT N
ATTENTION : ce programme ne fonctionne pas sur tout ordi, le BASIC semble standard pourtant mais les boucles FOR:NEXT d'un Basic à l'autre on un comportement différent.
Ce code devrait fonctionner sur la série 12/13/14, sur 1500 ça depends certainement des versions.

Sur Sharp PC-1251, la mise en boucle permet de gagner environ 35% de temps par rapport à mon premier programme IF:GOTO

Pour N=1
Temps P1 :39s
Temps P2 :25s
Modifié en dernier par charognard le 02 nov. 2011 08:23, modifié 22 fois.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par C.Ret »

Gilles59 a écrit : :D Même idée que mon prog 602P au dessus.
C'est pas tricher, c'est réfléchir
Oui, mais cela limite aux cas de la définition originale où les n sont entiers. Et le code, s'il est court ne permet pas de traiter le cas de nombres décimaux :

Code : Tout sélectionner

      x     M(x)

     90.     91.
     90.1    90.1
     90.5    90.5
     90.9    90.9
     91.     91.
     91.2    90.2
    101.1    91.1
    102.     92.
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 »