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

Répondre
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

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

Message par C.Ret »

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

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

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 :

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
Mais avec un langage si puissant, c'est vraiment trop facile.
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 »

91
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 :

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
Mais avec un langage si puissant, c'est vraiment trop facile.
mccarthy 1958 devrait donner 1948, non?
Image
Image
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 »

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
C'est pas optimisé, et heureusement que la pile des sous-programmes tient sur les 10 itérations max en dessous de 100.
Image
Image
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: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par gege »

Bof,
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
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 !!
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 »

Ma version sur HP48sx :

Code : Tout sélectionner

«
  « DUP 100 >
    « 10 -
    »
    « 11 + m91 EVAL
m91 EVAL
    » IFTE
  » \-> m91
  « m91 EVAL
  »
»
EDIT: Utilisation de translate = 2
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 »

RPL/50 (et 48 ?)

Code : Tout sélectionner

« → n 'IFTE(n>100 , n-10 , M(M(n+11)))' » 'M' STO
Testé sur HP50
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
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 »

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
Cela fonctionne sur HP48SX (enfin sous x48).

J'ai des progrès à faire en programmation RPL, moi... :roll:
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
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 »

pir2 a écrit :

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
C'est pas optimisé, et heureusement que la pile des sous-programmes tient sur les 10 itérations max en dessous de 100.
Joli programme pour HP-41!

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
J'ai vérifié dans la doc de la 41C:
  • XEQ numérique: 3 octets
  • LBL (00 à 14): 1 octet
  • GTO (00 à 14): 2 octets
Les 4 octets gagnés viennent de:
  • Suppression du GTO 01: 2 octets
  • Suppression du LBL 01: 1 octet
  • Remplacement de 100 par 90: 1 octet
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 »

pir2 a écrit :mccarthy 1958 devrait donner 1948, non?
Euhh...oui, bien sûr...je m'emporte avec mes traces bidon (le programme marche et donne bien 1948, hein) :oops:
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.
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 »

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

Trop simple en recursif en C
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
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 »

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.
Modifié en dernier par zpalm le 26 oct. 2011 13:57, modifié 1 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 :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'allai proposer 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 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.
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 »

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
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
Répondre

Retourner vers « Tous les Pockets »