Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)
Modérateur : Politburo
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)
Comme vous, je viens d’apprendre la disparition, à l’âge honorable de 84 ans, d’un des pionniers de l’informatique. Le professeur émérite John McCarthy a joué un rôle important dans le développement de l’informatique et en particulier dans le développement des langages de programmation et des intelligences artificielles.
J’avais préparé un petit exercice à vous soumettre pour ce week-end sur un sujet très diffèrent, mais ayant des applications quotidiennes.
Mais je préfère en changer pour celui-ci qui sera donc en quelque sorte un hommage rendu à ce pionner de l’IA, de l’optimisation et de la programmation.
En effet, il concerne une fonction souvent utilisée par le Pr. John McCarthy pour éprouver les langages de programmation ou la puissance de leur implémentation.
Cette fonction est appelée Fonction 91 de McCarthy . Elle est définie pour tout nombre n comme suit :
Comme à notre habitude, je vous invite à nous proposer vos solutions de programmation pour tout Pocket, Calculatrice ou petit systèmes.
Les règles sont identiques à celles des Misez p’tit précèdent. Le nombre n est sur le niveau supérieur (x: ou 1: de la pile, ou saisi par l’utilisateur à l’invite (INPUT, PROMPT ou AREAD , …). Le code le plus court, le plus astucieux ou le plus véloce, qui affichera ou imprimera les bons résultats pour tout n gagnera notre aimable enthousiasme.
Petite exception pour ce n°10, les codes en LISP et donc les systèmes (même éventuellement des non-Pockets) seront exceptionnellement acceptés. Et j'imagine que vous comprenez bien pourquoi.
J’avais préparé un petit exercice à vous soumettre pour ce week-end sur un sujet très diffèrent, mais ayant des applications quotidiennes.
Mais je préfère en changer pour celui-ci qui sera donc en quelque sorte un hommage rendu à ce pionner de l’IA, de l’optimisation et de la programmation.
En effet, il concerne une fonction souvent utilisée par le Pr. John McCarthy pour éprouver les langages de programmation ou la puissance de leur implémentation.
Cette fonction est appelée Fonction 91 de McCarthy . Elle est définie pour tout nombre n comme suit :
Comme à notre habitude, je vous invite à nous proposer vos solutions de programmation pour tout Pocket, Calculatrice ou petit systèmes.
Les règles sont identiques à celles des Misez p’tit précèdent. Le nombre n est sur le niveau supérieur (x: ou 1: de la pile, ou saisi par l’utilisateur à l’invite (INPUT, PROMPT ou AREAD , …). Le code le plus court, le plus astucieux ou le plus véloce, qui affichera ou imprimera les bons résultats pour tout n gagnera notre aimable enthousiasme.
Petite exception pour ce n°10, les codes en LISP et donc les systèmes (même éventuellement des non-Pockets) seront exceptionnellement acceptés. Et j'imagine que vous comprenez bien pourquoi.
Modifié en dernier par C.Ret le 19 janv. 2023 18:05, modifié 1 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.
-
- 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)
Sacré bonhomme. Quand on compare la date de création du FORTAN, du LISP et du COBOL, on se rend compte qu'il y en avait un sacrément en avance. Pas le plus facile à maîtriser hélas.
Je rassemble mes souvenirs de l'ENSICAEN avec un peu d'aide trouvée >ici< pour écrire ces quelques lignes :
Mais avec un langage si puissant, c'est vraiment trop facile.
Je rassemble mes souvenirs de l'ENSICAEN avec un peu d'aide trouvée >ici< pour écrire ces quelques lignes :
Code : Tout sélectionner
(DEFUN mccarthy (n)
(IF (> n 100)
(- n 10)
(mccarthy (mccarthy (+ n 11)))
)
)
>(mccarthy -1)
91
>(mccarthy 0)
91
>(mccarthy 7)
91
>(mccarthy 1958)
91
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.
Chuck Norris peut revenir en arrière dans Super Mario Land.
Chuck Norris utilise exclusiment des calculatrices Texas Instruments.
- pir2
- Fonctionne à 9600 bauds
- Messages : 4647
- Enregistré le : 31 oct. 2006 15:08
- Localisation : 67310 Westhoffen
- Contact :
Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)
91
mccarthy 1958 devrait donner 1948, non?billaj a écrit :Sacré bonhomme. Quand on compare la date de création du FORTAN, du LISP et du COBOL, on se rend compte qu'il y en avait un sacrément en avance. Pas le plus facile à maîtriser hélas.
Je rassemble mes souvenirs de l'ENSICAEN avec un peu d'aide trouvée ici pour écrire ces quelques lignes :Mais avec un langage si puissant, c'est vraiment trop facile.Code : Tout sélectionner
(DEFUN mccarthy (n) (IF (> n 100) (- n 10) (mccarthy (mccarthy (+ n 11))) ) ) >(mccarthy -1) 91 >(mccarthy 0) 91 >(mccarthy 7) 91 >(mccarthy 1958) 91
- pir2
- Fonctionne à 9600 bauds
- Messages : 4647
- Enregistré le : 31 oct. 2006 15:08
- Localisation : 67310 Westhoffen
- Contact :
Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)
Code : Tout sélectionner
LBL"MCC
XEQ 00
STOP
LBL 00
100
x<>y
x>y?
GTO 01
11
+
XEQ 00
XEQ 00
RTN
LBL 01
10
-
RTN
- gege
- Fonctionne à 14400 bauds
- Messages : 7148
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)
Bof,
Je n'ai pas ma TI89 mais un truc du genre suivant devrait le faire :A mon sens ceci ne dépend pas du langage, mais de la seule faculté d'appeller des fonctions avec passage de paramètres par valeur.
Lisp est clairement un tour de force, mais c'est un peu un tour de force théorique confiné au laboratoire (à idées).
YMMV
G.E.
EDIT : j'aime bien la solution HP41 !!
Je n'ai pas ma TI89 mais un truc du genre suivant devrait le faire :
Code : Tout sélectionner
Define maccarthy(n)
Func
If n>100 Then
Return n-10
Else
Return maccarthy(maccarthy(n+11))
EndIf
EndFunc
Lisp est clairement un tour de force, mais c'est un peu un tour de force théorique confiné au laboratoire (à idées).
YMMV
G.E.
EDIT : j'aime bien la solution HP41 !!
-
- Fonctionne à 2400 bauds
- Messages : 2143
- Enregistré le : 30 août 2011 12:23
- Localisation : Vous êtes ici -> .
Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)
Ma version sur HP48sx :
EDIT: Utilisation de translate = 2
Code : Tout sélectionner
«
« DUP 100 >
« 10 -
»
« 11 + m91 EVAL
m91 EVAL
» IFTE
» \-> m91
« m91 EVAL
»
»
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
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
Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)
RPL/50 (et 48 ?)
Testé sur HP50
Code : Tout sélectionner
« → n 'IFTE(n>100 , n-10 , M(M(n+11)))' » '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
-
- Fonctionne à 2400 bauds
- Messages : 2143
- Enregistré le : 30 août 2011 12:23
- Localisation : Vous êtes ici -> .
Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)
Cela fonctionne sur HP48SX (enfin sous x48).Gilles59 a écrit :RPL/50 (et 48 ?)
Testé sur HP50Code : Tout sélectionner
« → n 'IFTE(n>100 , n-10 , M(M(n+11)))' » 'M' STO
J'ai des progrès à faire en programmation RPL, moi...
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
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
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2936
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)
Joli programme pour HP-41!pir2 a écrit :C'est pas optimisé, et heureusement que la pile des sous-programmes tient sur les 10 itérations max en dessous de 100.Code : Tout sélectionner
LBL"MCC XEQ 00 STOP LBL 00 100 x<>y x>y? GTO 01 11 + XEQ 00 XEQ 00 RTN LBL 01 10 - RTN
Avec une optimisation on peut supprimer le LBL 01 et gagner 4 octets, ça donne:
Code : Tout sélectionner
01 LBL"MCC
02 XEQ 00 (3)
03 STOP (1)
04 LBL 00 (1)
05 10 (2)
06 - (1)
07 90 (2)
08 x<>y (1)
09 x>y? (1)
10 RTN (1)
11 21 (2)
12 + (1)
13 XEQ 00 (3)
14 XEQ 00 (3)
15 RTN (1)
23 octets
- XEQ numérique: 3 octets
- LBL (00 à 14): 1 octet
- GTO (00 à 14): 2 octets
- Suppression du GTO 01: 2 octets
- Suppression du LBL 01: 1 octet
- Remplacement de 100 par 90: 1 octet
-
- 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)
Euhh...oui, bien sûr...je m'emporte avec mes traces bidon (le programme marche et donne bien 1948, hein)pir2 a écrit :mccarthy 1958 devrait donner 1948, non?
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.
Chuck Norris peut revenir en arrière dans Super Mario Land.
Chuck Norris utilise exclusiment des calculatrices Texas Instruments.
-
- Fonctionne à 2400 bauds
- Messages : 2143
- Enregistré le : 30 août 2011 12:23
- Localisation : Vous êtes ici -> .
Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)
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
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
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
- charognard
- 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)
Trop simple en recursif en C
donc je propose en basic tout con
donc je propose en basic tout con
Code : Tout sélectionner
10 INPUT N:R=1
20 IF R<1 THEN PRINT N
30 R=R+1-2*(N>100),N=N+11-21*(N>100):GOTO 20
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2936
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)
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.
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.
Modifié en dernier par zpalm le 26 oct. 2011 13:57, modifié 1 fois.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)
C'est exactement la version que j'allai proposer pour HP28S.Gilles59 a écrit :RPL/50 (et 48 ?)
Testé sur HP50Code : Tout sélectionner
« → n 'IFTE(n>100 , n-10 , M(M(n+11)))' » 'M' STO
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 langages 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 à programmer, ce n'est pas optimisé par rapport à la vitesse.
Une chance, avec les valeurs entre 0 et 100, les codes proposés pour la HP-41 n'impliquent pas un nombre d'appels récursifs exessifs. J'attends de voir l'adaptation RPN pour les HP classiques (HP-15c, HP-25, HP-97 etc...)
En principe, la fonction originale M(n) n'a été définie que pour n entier et positif. Mais, rien ne nous interdit d'éprouver nos implementations avec des nombres négatifs ou des nombres décimaux. En fait, tout nombre que l'utilisateur pourrait saisir sur sa calculatrice !
Et dans ce cas, certains codes vont tomber en panne , ou comme celui proposé ci-dessus pour HP28/48/49/50, prendre un temps très très long !
J'attends donc une version RPN non récursive qui pourra fonctionner sur les HP classiques dont la pile d'appel des GSB n'est pas élastique.
En BASIC, j'avais préparé quelque chose qui ressemble au code de Charo, mais sans l'astuce du '(N>100)', avec une boucle 'tant que'
Quelques valeur de n qui seront à tester :
20111024, 234, 102, 101, 100, 99, 98, 56, 45, 25.6, 10, 0, -5, -200
et les résultats respectifs attendus :
20111014, 224, 92, 91, 91, 91, 91, 91, 91, 91, 90.6, 91, 91, 91, 91
Il faut que la bonne valeur soit renvoyée, mais aussi que cela se fasse en un temps acceptable !
Modifié en dernier par C.Ret le 21 janv. 2023 18:17, modifié 1 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.
-
- Fonctionne à 2400 bauds
- Messages : 2143
- Enregistré le : 30 août 2011 12:23
- Localisation : Vous êtes ici -> .
Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)
Il va falloir utiliser la programmation synthétique pour augmenter la pile de retour des sous-programmes. Comme quoi la présentation faite par gégé lors des pocketicaires s'avère utilezpalm 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 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
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