Misez p'tit Optimisez n°75 : l'aire sous les Batrachions

[dprtl]

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

[gege]

Bonjour,
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;

Temps de traitement négligeable...
Mais pas du tout amusant !
C'est le moment de retourner dans le passé.
G.E.

[Marge]

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 !

[caloubugs]

Bonjour,
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;

Temps de traitement négligeable...
Mais pas du tout amusant !
C'est le moment de retourner dans le passé.
G.E.

T'as pas oublié le +1 dans ta formule style

Code : Tout sélectionner

v[i-v[i-1]]+1►v[i];

?

Je vais tenter un une-ligne ce soir...

[dprtl]

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

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.

[dprtl]

Bonjour,
Facile sur la Génération Z, ici la Prime :

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 :

Code : Tout sélectionner

FOR i FROM 3 TO 50000 DO

... ça se gâte.

et avec :

Code : Tout sélectionner

FOR i FROM 500 TO 50000 DO

... ça se gâte encore plus

[gege]

@caloubugs : oui +1, oublié à la recopie.

@dprtl : il est méssant !!!
Bon je m'y remets...
G.E.

[caloubugs]

Ça tenait tout juste en une ligne sur 71B :

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

Mais avec les nouvelles règles, dur.

[dprtl]

Ça tenait tout juste en une ligne sur 71B :

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

Mais avec les nouvelles règles, dur.

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.

[zpalm]

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.

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

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 :

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;

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

[caloubugs]

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.

Merci pour la précision, je suis perdu avec les générations... Comme dans la vraie vie

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

[C.Ret]

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.

[gege]

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.

[dprtl]

Comment avez-vous démontré la formule avec racine de 2 ?

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

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]

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

[...] 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  

et

Code : Tout sélectionner

1² + 2² + 3² + ... + n² = n.(n+1).(2n+1) / 6

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