Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
Modérateur : Politburo
- dprtl
- Fonctionne à 1200 bauds
- Messages : 463
- Enregistré le : 27 janv. 2013 00:26
- Localisation : Strasbourg
- Contact :
Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
Je vous propose en ce lundi soir un nouveau problème, qui va faire appel à votre capacité à compiler quelques MPO précédents. En 2014, dans la gazette 2 une suite numérique de type "batrachion" était définie de la façon suivante :
U(n) = U(n - U(n-1)) + 1
avec U(1) = 1 ou 0
et U(2) = 1
La TI-89 permet par exemple d'en tracer une courbe représentative ci-dessous :
Sous le curseur graphique de la TI, on a par exemple U(254) = 22.
L'idée de ce MPO m'est venue en lisant quelques passages de la biographie de John von Neumann. Ici, le but sera de calculer une approximation numérique, ou bien la valeur exacte, de l'aire sous la courbe dans l'intervalle de 2 à 500. Si besoin, n'hésitez pas à vous inspirer du MPO 3 pour implémenter la méthode de Simpson. Cependant, je ne prétends pas que c'est la plus adaptée à ce cas un peu particulier. Ceux qui n'aiment pas trop programmer, pourront également comparer les performances des calculettes qui embarquent une fonction de calcul intégral en ROM.
Je vous propose pour le fun un classement des machines, avec ou sans programmation, en 4 catégories sociologiques décrites ci-dessous. Il s'agit de catégories définies selon mon estimation très personnelle, donc à débattre :
1) machines des Baby-boomers, apparues entre 1974 et 1984 (exemples : HP-65, Casio PB-700, HP-15C, Sharp PC-1500)
2) machines de la génération X, sorties entre 1985 et 1993 (exemples : Casio PB-1000, HP-48SX, Sharp PC-E500)
3) machines de la génération Y, entre 1994 et 2010 (exemples : Casio Graph 100, HP-50G, TI-89)
4) machines de la génération Z, entre 2011 et aujourd'hui (exemples : HP Prime, TI‑83 Premium CE, WP-34S)
La solution la plus élégante, la plus rapide, la plus précise, la plus compacte (c'est un MPO), tournant sur la machine la plus économe, sortira vainqueure dans chacune de ces catégories... si la victoire a la moindre importance !
Pour rendre le défi plus intéressant, les machines de la génération Z devront être capables de calculer l'aire sous la courbe dans l'intervalle de 500 à 50000.
-->Sommaire des MPO
U(n) = U(n - U(n-1)) + 1
avec U(1) = 1 ou 0
et U(2) = 1
La TI-89 permet par exemple d'en tracer une courbe représentative ci-dessous :
Sous le curseur graphique de la TI, on a par exemple U(254) = 22.
L'idée de ce MPO m'est venue en lisant quelques passages de la biographie de John von Neumann. Ici, le but sera de calculer une approximation numérique, ou bien la valeur exacte, de l'aire sous la courbe dans l'intervalle de 2 à 500. Si besoin, n'hésitez pas à vous inspirer du MPO 3 pour implémenter la méthode de Simpson. Cependant, je ne prétends pas que c'est la plus adaptée à ce cas un peu particulier. Ceux qui n'aiment pas trop programmer, pourront également comparer les performances des calculettes qui embarquent une fonction de calcul intégral en ROM.
Je vous propose pour le fun un classement des machines, avec ou sans programmation, en 4 catégories sociologiques décrites ci-dessous. Il s'agit de catégories définies selon mon estimation très personnelle, donc à débattre :
1) machines des Baby-boomers, apparues entre 1974 et 1984 (exemples : HP-65, Casio PB-700, HP-15C, Sharp PC-1500)
2) machines de la génération X, sorties entre 1985 et 1993 (exemples : Casio PB-1000, HP-48SX, Sharp PC-E500)
3) machines de la génération Y, entre 1994 et 2010 (exemples : Casio Graph 100, HP-50G, TI-89)
4) machines de la génération Z, entre 2011 et aujourd'hui (exemples : HP Prime, TI‑83 Premium CE, WP-34S)
La solution la plus élégante, la plus rapide, la plus précise, la plus compacte (c'est un MPO), tournant sur la machine la plus économe, sortira vainqueure dans chacune de ces catégories... si la victoire a la moindre importance !
Pour rendre le défi plus intéressant, les machines de la génération Z devront être capables de calculer l'aire sous la courbe dans l'intervalle de 500 à 50000.
-->Sommaire des MPO
Modifié en dernier par dprtl le 02 sept. 2018 14:06, modifié 3 fois.
- gege
- Fonctionne à 14400 bauds
- Messages : 7147
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
Bonjour,
Facile sur la Génération Z, ici la Prime :
Temps de traitement négligeable...
Mais pas du tout amusant !
C'est le moment de retourner dans le passé.
G.E.
Facile sur la Génération Z, ici la Prime :
Code : Tout sélectionner
EXPORT intbrat()
BEGIN
LOCAL i,v;
{0,1}►v;
FOR i FROM 3 TO 500 DO
v[i-v[i-1]]►v[i];
END;
RETURN ΣLIST(v);
END;
Mais pas du tout amusant !
C'est le moment de retourner dans le passé.
G.E.
- Marge
- Fonctionne à 14400 bauds
- Messages : 6186
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
Bonne idée, Daniel, que de donner matière à compilation d'astuces !
Je ne pourrai malheureusement pas y participer... c'eût été avec plaisir, mais d'autres défis programmatiques me donnent du fil à retordre.
Quant au débat : il n'y avait pas la Bof génération aprês celle du babyboom ? juste une réplique sans réel intérêt si l'on considère 74 comme une date primordiale pour l'apparition des bébés d'ordinateurs...
Bonnes réflexions à tous !
Je ne pourrai malheureusement pas y participer... c'eût été avec plaisir, mais d'autres défis programmatiques me donnent du fil à retordre.
Quant au débat : il n'y avait pas la Bof génération aprês celle du babyboom ? juste une réplique sans réel intérêt si l'on considère 74 comme une date primordiale pour l'apparition des bébés d'ordinateurs...
Bonnes réflexions à tous !
3 hommes, 3 demis, un 3a... Magnéto, Serge !
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
-
- Fonctionne à 1200 bauds
- Messages : 434
- Enregistré le : 05 juin 2014 22:23
- Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau
Re: Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
T'as pas oublié le +1 dans ta formule stylegege a écrit :Bonjour,
Facile sur la Génération Z, ici la Prime :Temps de traitement négligeable...Code : Tout sélectionner
EXPORT intbrat() BEGIN LOCAL i,v; {0,1}►v; FOR i FROM 3 TO 500 DO v[i-v[i-1]]►v[i]; END; RETURN ΣLIST(v); END;
Mais pas du tout amusant !
C'est le moment de retourner dans le passé.
G.E.
Code : Tout sélectionner
v[i-v[i-1]]+1►v[i];
Je vais tenter un une-ligne ce soir...
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
- dprtl
- Fonctionne à 1200 bauds
- Messages : 463
- Enregistré le : 27 janv. 2013 00:26
- Localisation : Strasbourg
- Contact :
Re: Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
En effet, dans mes générations de calculettes, j'ai fusionné la génération Bof avec la Babyboom, que je fais commencer dorénavant à 1974. C'est bien la date de la sortie de la HP 65, première programmable au monde (au lieu de 1975 initialement), et première calculette dans l'espace.Marge a écrit : Quant au débat : il n'y avait pas la Bof génération aprês celle du babyboom ? juste une réplique sans réel intérêt si l'on considère 74 comme une date primordiale pour l'apparition des bébés d'ordinateurs...
Modifié en dernier par dprtl le 06 déc. 2016 19:39, modifié 1 fois.
- dprtl
- Fonctionne à 1200 bauds
- Messages : 463
- Enregistré le : 27 janv. 2013 00:26
- Localisation : Strasbourg
- Contact :
Re: Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
Oui, trop facile ! Du coup, comme il n'y avait pas encore beaucoup de réponses, j'ai revu mon énoncé, en corsant un peu le problème pour la génération Z ; après avoir testé ton programme avec :gege a écrit :Bonjour,
Facile sur la Génération Z, ici la Prime :
Code : Tout sélectionner
FOR i FROM 3 TO 50000 DO
et avec :
Code : Tout sélectionner
FOR i FROM 500 TO 50000 DO
- gege
- Fonctionne à 14400 bauds
- Messages : 7147
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
@caloubugs : oui +1, oublié à la recopie.
@dprtl : il est méssant !!!
Bon je m'y remets...
G.E.
@dprtl : il est méssant !!!
Bon je m'y remets...
G.E.
-
- Fonctionne à 1200 bauds
- Messages : 434
- Enregistré le : 05 juin 2014 22:23
- Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau
Re: Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
Ça tenait tout juste en une ligne sur 71B :
Mais avec les nouvelles règles, dur.
Code : Tout sélectionner
10 DIM B(500) @ B(2)=1 @ S=2 @ FOR I=3 TO 500 @ B(I)=B(I-B(I-1))+1 @ S=S+B(I) @ NEXT I @ DISP S
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
- dprtl
- Fonctionne à 1200 bauds
- Messages : 463
- Enregistré le : 27 janv. 2013 00:26
- Localisation : Strasbourg
- Contact :
Re: Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
En fait, le HP-71b n'est pas concerné par la règle bonus, qui ne s'applique qu'à la génération Z. Et c'est bel et bien la longueur de ligne maximale pour ce Basic, à un caractère près ! Par contre, comme je n'ai qu'un seul module de 4 Ko, le programme plante lorsque I atteint la valeur 101.caloubugs a écrit :Ça tenait tout juste en une ligne sur 71B :Mais avec les nouvelles règles, dur.Code : Tout sélectionner
10 DIM B(500) @ B(2)=1 @ S=2 @ FOR I=3 TO 500 @ B(I)=B(I-B(I-1))+1 @ S=S+B(I) @ NEXT I @ DISP S
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2930
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
Je me suis plongé dans ma mpothèque et voici ce que j'obtiens pour les machines de la génération Z:
WP 34s en 15 pas.
On entre les valeurs de début et de fin, par exemple 2 ENTER 500, puis on appuie sur A et après quelques secondes on a le résultat: 10512.
Avec 500 et 50000, on obtient au bout de quelques minutes: 10530174.
Et sur HP Prime :
Il suffit de quelques secondes pour que MPO75(500,50000) retourne 10530174.
Mais je soupçonne que l'on puisse faire plus rapide avec une formule directe...
WP 34s en 15 pas.
Code : Tout sélectionner
001 LBL A
002 STO Z
003 STO- Z
004 RCL Y
005 DEC X
006 RCL+ X
007 SQRT
008 ROUNDI
009 STO+ T
010 RDN
011 INC Y
012 x>=? Y
013 BACK 009
014 x<>Z
015 RTN
Avec 500 et 50000, on obtient au bout de quelques minutes: 10530174.
Et sur HP Prime :
Code : Tout sélectionner
EXPORT MPO75(a,b)
BEGIN
LOCAL i,s;
FOR i FROM a-1 TO b-1 DO
s:=s+ROUND(√(2*i),0);
END;
END;
Mais je soupçonne que l'on puisse faire plus rapide avec une formule directe...
-
- Fonctionne à 1200 bauds
- Messages : 434
- Enregistré le : 05 juin 2014 22:23
- Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau
Re: Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
Merci pour la précision, je suis perdu avec les générations... Comme dans la vraie viedprtl a écrit : En fait, le HP-71b n'est pas concerné par la règle bonus, qui ne s'applique qu'à la génération Z. Et c'est bel et bien la longueur de ligne maximale pour ce Basic, à un caractère près ! Par contre, comme je n'ai qu'un seul module de 4 Ko, le programme plante lorsque I atteint la valeur 101.
Je n'ai pas prêté attention à la mémoire dispo, du fait que j'ai 3 modules de 32 ko d'installés (un luxe de riche quoi... )
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
Je m'y attendais, dès le début je suis à la recherche d'une solution paramétrique.
Et qui n'utilise pas de tableaux, donc 500 ou 5000 c'est pareil.
D'ailleurs, sur un SHARP PC 1211 , déjà 500 c'est de la science-fiction.
J'ai donc écrit un programme qui calcule l'aire sous la courbe du batrachiant en question entre deux termes Ua et Ub.
Dans sa forme la plus compacte, ce code de 110 pas tient en deux lignes (respectivement une ligne programme principal de 50 pas et son sous-programme de 60 pas) qui utilise les registres N, K, M, I et S pour afficher le résultat.
Il suffit d'entrer successivement les indices a et b et le pocket vous affiche immédiatement (moins de deux secondes - ce qui est immédiat sur ce trentenaire) l'aire sous la courbe.
(C'est pas parce qu'on est de 1981 que l'on ne peut pass faire comme les Z !!)
Je donnerai aussi, tant qu'à faire, le code permettant de calculer U(n) pour tout n, c'est un one-liner de BASIC (une ligne de 44 pas utilisant uniquement les registres N et K et un label DEF).
Mais j'attends un peu que les plus jeunes générateurs exposent les solutions sur les monstres actuels. Juste histoire qu'ils cherchent un peu et qu'ils ne soient pas influencés par la solution algorithmique pertinente issue de ma très très longue expérience.
Et qui n'utilise pas de tableaux, donc 500 ou 5000 c'est pareil.
D'ailleurs, sur un SHARP PC 1211 , déjà 500 c'est de la science-fiction.
J'ai donc écrit un programme qui calcule l'aire sous la courbe du batrachiant en question entre deux termes Ua et Ub.
Dans sa forme la plus compacte, ce code de 110 pas tient en deux lignes (respectivement une ligne programme principal de 50 pas et son sous-programme de 60 pas) qui utilise les registres N, K, M, I et S pour afficher le résultat.
Il suffit d'entrer successivement les indices a et b et le pocket vous affiche immédiatement (moins de deux secondes - ce qui est immédiat sur ce trentenaire) l'aire sous la courbe.
(C'est pas parce qu'on est de 1981 que l'on ne peut pass faire comme les Z !!)
Je donnerai aussi, tant qu'à faire, le code permettant de calculer U(n) pour tout n, c'est un one-liner de BASIC (une ligne de 44 pas utilisant uniquement les registres N et K et un label DEF).
Mais j'attends un peu que les plus jeunes générateurs exposent les solutions sur les monstres actuels. Juste histoire qu'ils cherchent un peu et qu'ils ne soient pas influencés par la solution algorithmique pertinente issue de ma très très longue expérience.
Modifié en dernier par C.Ret le 08 déc. 2016 06:01, modifié 4 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.
- gege
- Fonctionne à 14400 bauds
- Messages : 7147
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
Bonjour,
En bricolant une espèce de "super-tableau" à 100000 éléments, on trouve sur Prime en 38 secondes, mais c'est pas beau !
Je vais faire un essai sans stockage, récursif, ça va être lent...
Comment avez-vous démontré la formule avec racine de 2 ?
G.E.
En bricolant une espèce de "super-tableau" à 100000 éléments, on trouve sur Prime en 38 secondes, mais c'est pas beau !
Je vais faire un essai sans stockage, récursif, ça va être lent...
Comment avez-vous démontré la formule avec racine de 2 ?
G.E.
- dprtl
- Fonctionne à 1200 bauds
- Messages : 463
- Enregistré le : 27 janv. 2013 00:26
- Localisation : Strasbourg
- Contact :
Re: Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
Je crois que personne ne l'a démontrée mathématiquement ! L'intuition est venue probablement en observant la courbe graphique ? Le premier a avoir présenté une formule avec racine dans le MPO 51 était C.Ret, avec une première approximation (traduite de son code Basic) :gege a écrit : Comment avez-vous démontré la formule avec racine de 2 ?
U(i) = int(1.46061*sqrt(i))
Ensuite, il y a eu plusieurs autres tentatives pour ajuster cette formule, et j'avais fait l'observation suivante (non démontrée) :
Soit f(x) = (x^2 + x + 4)/2
Lorsque x prend des valeurs entières, f(0), f(1), f(2), f(3), etc. correspondent aux "sauts" de la suite U(i).
Pour arriver, après quelques simplifications formelles approximatives, à la formule suivante (vérifiée par calcul exhaustif) :
U(i) = round(sqrt(2*i-3))
Qui donne, un peu étonnamment, exactement les mêmes résultats que celle de Zpalm :
U(i) = round(sqrt(2*(i-1)))
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°75 : l'aire sous les Batrachions
38s sur prime contre moins d'une seconde sur PC-1211, j'ai peur que la méthode par récurrence attendue encore plus lente ne soit une catastrophe...
Je suggère une méthode arithmétique...
..j'ai d'ailleurs maintenant une formule algébrique non approximative,
Je peux d'ailleurs calculer que U(1 000 000 000 ) fait 44721, valeur atteinte par cette suite bastrachienne dès le terme U(999 961 562)
Mais bon j'ai un Baby de 1424 step qui fait BEEP...
Je suis inquiet, j'obtiens effectivement ces deux résultats, mais dans les deux secondes, temps inchangé quelque soient les bornes de l'intégration ?!
En fait, le calcul est le même quelque soit l'étendue de l'aire à rechercher. Je n'utilise aucune boucle de calcul.
Juste le fait que :
et
Ce qui m'évite bien des boucles et des boucles et des boucles ... de calculs (le PC-1211 n'est pas rapide alors j'évite de m'attarder
Je suggère une méthode arithmétique...
..j'ai d'ailleurs maintenant une formule algébrique non approximative,
Je peux d'ailleurs calculer que U(1 000 000 000 ) fait 44721, valeur atteinte par cette suite bastrachienne dès le terme U(999 961 562)
Mais bon j'ai un Baby de 1424 step qui fait BEEP...
zpalm a écrit :[...] On entre les valeurs de début et de fin, par exemple 2 ENTER 500, puis on appuie sur A et après quelques secondes on a le résultat: 10512.
Avec 500 et 50000, on obtient au bout de quelques minutes: 10530174.[...<)
Je suis inquiet, j'obtiens effectivement ces deux résultats, mais dans les deux secondes, temps inchangé quelque soient les bornes de l'intégration ?!
En fait, le calcul est le même quelque soit l'étendue de l'aire à rechercher. Je n'utilise aucune boucle de calcul.
Juste le fait que :
Code : Tout sélectionner
1 + 2 + 3 + ... + n = n.(n+1) / 2
Code : Tout sélectionner
1² + 2² + 3² + ... + n² = n.(n+1).(2n+1) / 6
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.