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

charognard a écrit :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
J'adore !!
Excellent.

Pfiouu il a déchaîné tout le monde ce "Misez p'tit, Optimisez" !
Miam... encore :slime:
G.E.

EDIT : J'ai l'impression que M(x) vaut :
-- x > 100 => M(x) = x - 10
-- x <= 100 et entier => M(x) = 91
-- x <= 100 et non entier => M(x) = 90 + Frac(x)
C'est beaucoup plus rapide mais moins concis à programmer.

Tiens au passage la solution sur TI suivante ne marche pas... pourquoi ?? héhé

Code : Tout sélectionner

Define maccarthy(n)
Func
Return when(n>100,n-10,maccarthy(maccarthy(n+11)))
EndFunc
Le gagnant emporte un véritable cintre en fil de fer de collection !!
Modifié en dernier par gege le 27 oct. 2011 01:27, modifié 3 fois.
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 »

Un code qui semble marcher pour HP 25 (pas pu tester à fond, l'émulo se traîne anormalement sur ma machine et ma vraie 25 n'est plus programmable)

Code : Tout sélectionner

01 1
02 STO 1
03 R-
04 1
05 0
06 1   (oui, j'ai foiré l'ordre des conditions et la flemme de remettre ça en ordre à 1h du mat...donc 101 pour simuler un <=100 2 lignes plus bas)
07 x<->y
08 x<y?
09 GTO 14
10 1
11 0
12 -
13 GTO 20
14 1
15 1
16 +
17 2
18 STO + 1
19 R-
20 1
21 STO - 1
22 R-
23 RCL 1
24 X!=0?
25 GTO 03
26 R-
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
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 »

gege a écrit :Tiens au passage la solution sur TI suivante ne marche pas... pourquoi ?? héhé
La réponse est dans la question : "TI" ! :mrgreen:
:arrow:
Avatar du membre
badaze
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 8384
Enregistré le : 12 févr. 2007 18:36
Localisation : Pas très loin de Lyon
Contact :

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

Message par badaze »

gege a écrit :
charognard a écrit :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
J'adore !!
Excellent.

Pfiouu il a déchaîné tout le monde ce "Misez p'tit, Optimisez" !
Miam... encore :slime:
G.E.

EDIT : J'ai l'impression que M(x) vaut :
-- x > 100 => M(x) = x - 10
-- x <= 100 et entier => M(x) = 91
-- x <= 100 et non entier => M(x) = 90 + Frac(x)
C'est beaucoup plus rapide mais moins concis à programmer.

Tiens au passage la solution sur TI suivante ne marche pas... pourquoi ?? héhé

Code : Tout sélectionner

Define maccarthy(n)
Func
Return when(n>100,n-10,maccarthy(maccarthy(n+11)))
EndFunc
Le gagnant emporte un véritable cintre en fil de fer de collection !!
Absence de variable locale ?
Tout est bon dans le pocket.
Moi j'aime tout.... Casio, HP, Sharp, TI et les autres sauf que les TI semblent ne pas m'aimer :(
http://www.emmella.fr
Mes Casio - HP - Sharp - TI
Homme invisible.
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 »

gege a écrit :
charognard a écrit :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
J'adore !!
Excellent.

Pfiouu il a déchaîné tout le monde ce "Misez p'tit, Optimisez" !
Miam... encore :slime:
G.E.

EDIT : J'ai l'impression que M(x) vaut :
-- x > 100 => M(x) = x - 10
-- x <= 100 et entier => M(x) = 91
-- x <= 100 et non entier => M(x) = 90 + Frac(x)
C'est beaucoup plus rapide mais moins concis à programmer.

Tiens au passage la solution sur TI suivante ne marche pas... pourquoi ?? héhé

Code : Tout sélectionner

Define maccarthy(n)
Func
Return when(n>100,n-10,maccarthy(maccarthy(n+11)))
EndFunc
Le gagnant emporte un véritable cintre en fil de fer de collection !!
simple sur TI74 la recursivité tu ne l'a pas, une fonction ne peut s'auto appeller


merde grillé, et par 2 fois en plus.
au reveil je n'ai pas synthétisé de suite la réponse d'hobicat ;)

gégé examine bien et essai mon dernier code avec FOR:NEXT uniquement sur les SHARP cités car j'utilise une des propriétés de leur FOR:NEXT.

Image
A la lecture de ce code

Code : Tout sélectionner

10 INPUT N:FOR A=1 TO 203-2*INT N:N=N+11-21*(N>100):NEXT A:PRINT N
Nous serions amené à penser que la première condition n'est pas remplie et pourtant si.
Plus qu'une astuce de programmation, c'est une réflexion sur un choix de machine.
Suivant l'OP ce programme donnera des résultats différents. (Ex. sur Casio ça ne fonctionne pas .... j'ai pris Casio au hazard bien sur)

l'idée me semble t'il. n'était pas de faire un programme qui retourne 91 mais un programme light qui passe par toutes les étapes du calculs (Faire le chemin, plutot que d'etre present à l'arivée).
Quans je dis light, c'est tant au niveau du code que des ressources utilisées.
La récursivité a un coup enorme en ressources (les pointeurs de pile + les variables locales sont à mémoriser. Pour 1 c'est plus de 400 octets à ajouter), ce qui la disqualifie.
Il faut donc garder un modèle parcourant le même nombre d'étapes et donnant un résultat juste.

Je ne parle même pas des nombres négatifs qui au dessus d'une certaine valeur absolue feront un stack overflow en récursivité sur les quelques pockets ayant une pile supérieure.
et il n'y en a pas des masses dans les machines que j'ai, regardez mon tableau colonne 16 (Tiens le X07 avec son DEFFN .... à tester, même si je sais qu'il n'y a pas de variables locales)
Image
Modifié en dernier par charognard le 27 oct. 2011 08:30, modifié 3 fois.
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 »

Hobiecat a écrit :
gege a écrit :Tiens au passage la solution sur TI suivante ne marche pas... pourquoi ?? héhé
La réponse est dans la question : "TI" ! :mrgreen:
:arrow:
Ne dis pas de mal des auteurs de la ROM du HP71B, s'il te plaît !!! (voir fil sur les version dudit)
charognard a écrit :simple sur TI74 la recursivité tu ne l'a pas, une fonction ne peut s'auto appeller
Certes, mais je pensais à la TI89.
Je regarderai tes commentaires quand mon cerveau aura démarré (vers 10h).

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

billaj a écrit :[...](oui, j'ai foiré l'ordre des conditions et la flemme de remettre ça en ordre à 1h du mat...donc 101 pour simuler un <=100 2 lignes plus bas)[...]
Tiens, c'est marrant, j'allai aussi poster une version pour HP-15c ou autre classique, mais en essayant je me suis rendu compte que j'ai moi aussi m....r le sens du test. Et donc toutes les astuces ont été mises à mal. Il était tard, j'ai renoncé à poster un truc bancal.
charognard a écrit :L’idée, me semble t'il, n'était pas de faire un programme qui retourne 91 mais un programme light qui passe par toutes les étapes du calcul (Faire le chemin, plutôt que d'être présent à l'arrivée).
gege a écrit :EDIT : J'ai l'impression que M(x) vaut :
-- x > 100 => M(x) = x - 10
-- x <= 100 et entier => M(x) = 91
-- x <= 100 et non entier => M(x) = 90 + Frac(x)
C'est beaucoup plus rapide mais moins concis à programmer.
Voilà donc deux thèses opposées. L’une suggérant de suivre le chemin et donc de programmer plus ou moins directement la récursivité de la fonction 91 de McCarthy, l’autre faisant l’analyse des résultats de cette fonction et suggérant de programmer une fonction non récursive qui cependant donne les mêmes résultats.

A mon humble avis, les deux se valent, et je suis curieux de suivre les avancés des auteurs des différents codes de ce fils pour voir l’évolution des deux ou trois techniques qui seront utilisées.
Si je résume bien, il y donc pour le moment cinq chemins possibles (le cinquième n’étant pas recommandable) :
  1. La programmation de la récursivité brute et directe : évidemment réservée aux machines qui le supportent, quitte à perdre du temps d’exécution ou utiliser une pile d’appels monstrueuse par rapport au résultat qui n’est, en fait, qu’un nombre,
  2. La programmation de la récursivité indirectement : en utilisant un registre servant de compteur d’appels pour pallier aux capacités de la machine. Soit par un registre, soit par une boucle FOR/TO/STEP//NEXT astucieuse.
  3. L’analyse des résultats : dans le cas de la fonction 91 de McCarthy, cette approche est justifiée car pour les entiers en particulier l’analyse est simple, la fonction renvoie toujours la même valeur jusqu’au seuil critique de 101 à partir d’où la réponse est une fonction affine simple.
  4. L’analyse des résultats avec extrapolations aux décimaux et négatifs : afin de calculer sans récurrence la réponse mais en tenant compte des cas hors ‘entiers positifs’, c'est-à-dire nombre décimaux, nombres négatifs, etc…
  5. La méthode non recommandable des HP-41 : qui par un chemin erroné et sans afficher le moindre message d’alerte ou d’erreur affiche une réponse qui n’est juste que fortuitement pour les entiers positifs.
Hormis la dernière méthode qui n’est pas recommandable (aaah ! les HP-41 quel escroquerie !) , tous ces chemins ont leurs avantages et leurs inconvénients :
  • Les deux dernières demandent à réaliser l’analyse de la fonction, de ne pas oublier certains cas particulier et cela va conduire à un algorithme peut-être plus complexe, mais qui aura l’avantage de ne pas à avoir suivre le chemin de la récursivité.
  • Les deux premières sont plus simples en terme d’analyse et de compréhension de la fonction, mais demandent de bien maitriser l'effort. Sauf pour les systèmes RPL où les capacités mémoire énormes et le principe de fonctionnement permettent de ne pas avoir à réfléchir à cela, tout du moins pour manipuler des nombres, même négatifs jusqu'à quelques dizaines de milliers. Mais il y aura une limite ou même une HP50g fera un ‘Stack Overflow - Memory Low error !
Paradoxalement, le choix du chemin pour miser petit et optimiser n’est pas évident et dépend énormément des capacités de la machine. Même pour les Pocket SHARP, il faut faire attention, charo explique bien que l’astuce du FOR :NEXT ne fonctionnera pas sur tous les modèles.

Les capacités modestes mais géniales des HP classiques vont contraindre les auteurs à des algorithmes plus sophistiqués. Ils seront différents, mais peut-être plus standards et implémentables sur un plus grand nombre de machines sans trop de modifications.


Décidément, ce sujet ne manque pas d’intérêt. Et je suis curieux de voir les stratégies que chacun va élaborer, puis de voir l’optimisation se faire dans chacun des cas de figure.



A la réflexion, je crois que l’on touche là du doigt la raison de cette fonction 91, J. McCarthy avait le géni de mettre en évidence tous les aspects des sciences de la programmation à partir d’exemples simples. Et j’imagine que comme nous, ces élèves et disciples ont aussi planché et transpiré sur les problèmes que ce grand professeur nous soumet.
Modifié en dernier par C.Ret le 21 janv. 2023 18:33, 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.
pascal_meheut
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 307
Enregistré le : 25 sept. 2008 06:40

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

Message par pascal_meheut »

Par respect envers cet immense Monsieur et puisqu'on est quand même sur le forum pocket, j'ai fait tourner le code sur une AI-1000.

Ca donne ca que j'ai codé avec COND et pas IF pour faire dans la nostalgie jusqu'au bout :
Image

Et bien sur, ca se calcule à la vitesse d'une AI-1000........

Image

RIP.
Pas mal de HP de la 55 à la 48, 97.... Casio 702p, 890P, AI-1000 et PB-2000C, WP34s dont j'écris les émulateurs et la version iOS
Je cherche les modules Pascal et Prolog pour la PB-2000C
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 »

Oaaah ! 8) Sympa le AI-1000 programmable en LISP. Ca c'est une découverte pour moi... J'avais entendu parler du 2000C qui se programme en C, mais jamais d'un pocket en LISP (hormis les RPL HP).
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
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 »

pascal_meheut a écrit :Et bien sur, ca se calcule à la vitesse d'une AI-1000........
C'est à dire ?
Je fais partie de ceux qui n'ont jamais vu de près cette bête ! :wink:
pascal_meheut
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 307
Enregistré le : 25 sept. 2008 06:40

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

Message par pascal_meheut »

Oui, l'AI-1000 est la même qu'une PB-2000C, même boitier, écran, piles, etc mais elle se programme en LISP. Elle est assez rare parce que jamais commercialisé en dehors du Japon et pas vendue à des centaines de milliers d'exemplaires (de mémoire).

Coté vitesse, c'est là aussi comme une PB-2000C : lent. (M91 20) se calcule en 8 sec et le programme HP-41C donné sur la 1ère page tourne en 14 sec chez moi. On est donc pas du coté des foudres de guerre.
Pas mal de HP de la 55 à la 48, 97.... Casio 702p, 890P, AI-1000 et PB-2000C, WP34s dont j'écris les émulateurs et la version iOS
Je cherche les modules Pascal et Prolog pour la PB-2000C
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 »

Une version en FORTH (testée sous pfe). Pour ceux qui possèdent le module FORTH pour HP-71B.

Code : Tout sélectionner

: m91
dup 101 < if 11 + recurse recurse else 10 - then
;
Voilà les résultats:

Code : Tout sélectionner

10 m91 . 91 ok
-200 m91 . 91 ok
-20000 m91 . 91 ok
10.3 m91 . 91 ok
700 m91 . 690 ok
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
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 »

cgh a écrit :Une version en FORTH (testée sous pfe). Pour ceux qui possèdent le module FORTH pour HP-71B.

Code : Tout sélectionner

: m91
dup 101 < if 11 + recurse recurse else 10 - then
;
J'adore vraiment ces fils misez p'tit : que de découvertes de bidouilles de programmation, de particularités de machines ou comme ici, de subtilités de langages !
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 »

cgh a écrit :Une version en FORTH (testée sous pfe). Pour ceux qui possèdent le module FORTH pour HP-71B.

Code : Tout sélectionner

: m91
dup 101 < if 11 + recurse recurse else 10 - then
;
C'est fou comme le FORTH ressemble à du RPL ! Mais c'est historique, l'équipe qui a développé les HP-28C/S était en fait issue de celle qui a développé les HP-71/75. Et le FORTH a vite était leur language de prédilection, car bien adapté à la structure du processeur Saturn.

Par contre, il y a des points bien pratiques en FORTH, comme cette instruction 'recurse', qui, si j'interprète bien permet de rappeler la function en cours de définition sans avoir à la nommer.
En RPL, on peut utiliser le même code à condition de nommer nominativement la fonction par m91, et ne plus changer son nom par la suite. C'est curieux, car le nom de la commande ne sera jamais donné dans lors de la définition en RPL, uniquement lors de la mémorisation:

Code : Tout sélectionner

« IF DUP 101 < THEN 11 + m91 m91 ELSE 10 - END » 'm91' STO
Ah! Oui j'avais oublié, en RPL la structure IF THEN ELSE END ressemble plus à celle du BASIC en encadrant les instructions, alors que la logique du FORTH quand à la position des IF THEN et autre ELSE m'échappe un peu.
cgh a écrit : Voilà les résultats:

Code : Tout sélectionner

10 m91 . 91 ok
-200 m91 . 91 ok
-20000 m91 . 91 ok
10.3 m91 . 91 ok
700 m91 . 690 ok
Ben , c'est OK à condition de considérer uniquement la définition originale, à savoir celle où n est entier (et éventuellement négatif).
Si on prend la définition étendu à l'ensemble des nombres réels alors, il y a certains OK qui sautent !
Modifié en dernier par C.Ret le 21 janv. 2023 18:39, modifié 3 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 »

C.Ret a écrit :Par contre, il y a des points bien pratiques en FORTH, comme cette instruction 'recurse', qui, si j'interprète bien permet de rappeler la function en cours de définition sans avoir à la nommer.
En RPL, on peut utiliser le même code à condition de nommer nominativemetn la fonction par m91, et ne plus changer son nom par la suite. C'est currieux, car le nom de la commande ne sera jamais donné dans lors de la définition en RPL, uniquement lors de la mémorisation:

Code : Tout sélectionner

 « IF DUP 102 < THEN 11 + m91 m91 ELSE 10 - END » 'm91' STO
En fait, tu peux utiliser des variables locales. J'ai fourni le code de cela en page 1. L'avantage est que le nom de la fonction globale peut être changé, sans impacter le code. Mais cela se paie: c'est plus gros !

EDIT : Nan, j'ai dit une bêtise :oops:. Mon code est faux. J'avais nommé la fonction globale 'm91' sous x48. Si le nom, change mon programme plante :(
Va falloir que je relise la documentation de la HP48 !!!!
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 »