Misez p'tit, Optimisez - N°51 (Gazette N°2-Les batrachions)

[ledudu]

Bonjour C.Ret, ta formule est intéressante mais c'est effectivement une approximation qui ne donne pas le bon résultat dans tous les cas:
u5051=100 OK
u5052 = 100 ce devrait être 101

Moi j'ai ça (en programmant la suite par récurrence sur excel):

• 5048 100
  5049 100
  5050 100
  5051 101
  5052 101
  5053 101
  5054 101

J'ai aussi une formule directe qui donne la même chose sans test...

Avec cette formule, j'obtiens :
U999.961.560 = 44720
U999.961.561 = 44721
U999.961.562 = 44721
U999.999.999 = 44721

On a un décalage de 1 sur le changement de valeur.

[zpalm]

On a un décalage de 1 sur le changement de valeur.

Au début de la suite j'ai:

• 01 1
  02 1
  03 2
  04 2
  05 3
  06 3
  07 3
  08 4
  09 4
  10 4
  11 4
  12 5
  13 5

[ledudu]

U(1)=1
U(2)=U(2-U1)+1=U(1)+1=2

[zpalm]

U(1)=1
U(2)=U(2-U1)+1=U(1)+1=2

Ça explique le décalage.
La définition de la suite donnée par gege dans la Gazette:

• un = un-un-1 + 1 avec u1=1 et u2=1

Si on prend u1=0 comme dans le programme pour PB-700, ça ne change rien au reste de la suite.

[ledudu]

Ma foi tu as raison. C'est bien l'énnoncé de gégé.

En revanche, gégé,pourquoi fixer la veleur de U2 alors qu'elle se calcule avec U1 ?
Ce qui me gène, c'est que du coup la série est moins belle au début.
Avec U1=2 on a 1 22 333 4444 55555 ... C'est bô, non ? Pourquoi commencer par 11.

[dprtl]

Eurêka ! J'ai trouvé la formule. En fait, ça n'était pas très compliqué avec l'information que j'avais fournie précédemment. Il me manquait juste un peu de temps pour calculer la réciproque (et je ne sais pas si un CAS aurait su le faire pour moi ?). Le code prend finalement 22 caractères et [IN], puis [CALC], sur Casio FX-850P (par exemple).

Pour ne pas dévoiler trop la formule, voici le programme codé, en 5 pas, pour ma calculette la plus ancienne, une HP-25 :

Code : Tout sélectionner

00
01 02
02 61
03 03
04 41
05 14 02

Le sixième pas est un "GTO 00", c'est le programme par défaut.

Usage :
1) passer en mode FIX 0 (il s'agit d'un mode dans lequel le résultat est arrondi à l'entier le plus proche)
2) 999961561 [ENTER]
3) [R/S]

=> le résultat 44720 s'affiche très rapidement.

[ledudu]

Euréka ! J'ai trouvé la formule.

28 ans déjà...

[zpalm]

J'adore les MPOs !! Quand on croit être arrivé au bout des optimisations quelqu'un arrive avec une nouvelle idée et on s'aperçoit qu'on peut encore simplifier.

@dprtl: ta formule m'a donné une idée et maintenant ma version sur WP 34S tient en 6 pas en comptant le LBL de début et le RTN de fin, soit 4 instructions de calcul. Le résultat est un nombre entier (pas besoin de jouer avec le format d'affichage). Et cerise sur le gâteau les registres Y, Z et T sont préservés.

[C.Ret]

Moi aussi, mais ce dernier me pose pas mal de soucis.

j'ai enfin réussit à mettre tous mes pocket d'accord; ils calculent maintenant tous les termes de la suite au moins jusqu'à U(999961561) = 44720 et U(999961562) = 44721 !

J'aime bien moi qussi ces M.P.O., mais beaucoup moins de "rammmmmmmmmmmmmmmer autant" !!

J'aimerais bien connaitre le fondement théorique de tout cela et comment d'une formule par récurrence on arrive à une fonction algébrique simple (comme la racine carrée par exemple )

[ledudu]

De mon côté, je suis parti de l'observation de la série 1 22 333 4444, et j'ai considéré la somme des n premiers entiers qui vaut n(n+1)/2.
Si un chiffre p s'écrit exactement n(n+1)2 alors u(p)=n. Comme ci-dessus u(10)=4 et 4X5/2=10.
Pour un chiffre p, si on cherche à comparer p à un nombre de la forme n(n+1)/2, on peut penser étudier racine(2p) qui ne doit pas être très loin de ce n quand il existe.
J'ai comparé racine(2p) à u(p) sur les 20 premiers p. Il n'y a strictement égalité que de en temps mais c'est toujours assez proche. De là, l'idée de int(racine (2p))qui ne marche pas et finalement de int(racine(2p)+0,5) qui tombe pile poil.
J'espère qu'il n'est pas trop tôt pour dévoiler mon cheminement. Une démarche par tâtonnement donc.

Il m'intéresse de voir un résultat démontré et non intuité comme dans mon cas.

[dprtl]

De là, l'idée de int(racine (2p))qui ne marche pas et finalement de int(racine(2p)+0,5) qui tombe pile poil.

Je ne sais pas faire la démonstration de ma formule, car j'ai également simplifié grosso-modo une expression fausse (!). Par contre, par calcul exhaustif (ou presque), je sais que ma formule donne un résultat correct à partir de U2, et au moins jusqu'à U999.999.999. Ce n'est pas le cas de int(racine(2p)+0,5) !

[ledudu]

Flute, c'est pas fini alors...

[zpalm]

Grace au MPO 75 je me suis penché dans mes archives et je me suis apercu que je n'avais pas posté ma solution à celui-ci. La voici donc telle que je l'avais rédigée alors.

Tout d'abord comme ledudu j'ai regardé le comportement de la suite ce qui m'a permis de trouver un algorithme de calcul évitant les boucles et les délais de la récursion.
En effet à partir de u3, la suite se compose de la série des entiers n >1 répétés n fois: 11 22 333 4444 55555 666666 7777777 ...
On en déduit que si ux = n alors x-1 se trouve dans l'intervalle ](n-1)n/2, n(n+1)/2], soit: ](n²-n)/2, (n²+n)/2]
n²/2 étant au milieu de cet intervalle alors INT(SQRT(2x)) est égal soit à n soit à n-1 suivant la position de x par rapport n²/2.

On arrive à l'algorithme suivant permettant de calculer ux:

• n=INT(SQRT(2x))
• si n(n+1)/2 < x-1 alors n=n+1 (le test peut aussi se faire sur <= x-2)
• ux = n

L'avantage de cet algorithme c'est qu'il donne un résultat exact pour ux quelque soit x dans la limite des entiers supportés par la machine que l'on utilise, ce qui permet de valider des formules approchées.

Ma solution en 15 pas sur WP 34S:

Code : Tout sélectionner

01 LBL A          09 RCL* Y
02 DEC X          10 2
03 RCL X          11 /
04 RCL+ X         12 x<? Z
05 SQRT           13 INC Y
06 IP             14 RDN
07 RCL X          15 RTN
08 INC X

En 21 pas sur HP 41C:

Code : Tout sélectionner

01 LBL"BR         11 RCL Y          21 RTN
02 RCL X          12 *
03 2              13 2
04 ST- Z          14 /
05 *              15 RCL Z
06 SQRT           16 x<y?
07 INT            17 GTO 01
08 RCL X          18 ISG Z
09 1              19 LBL 01
10 +              20 RCL Z

En 63 pas sur Casio Pro FX-1:

Code : Tout sélectionner

001 ENT 1 :
004 2 = ? x K 2 ? + K 1 0 10^x - K 1 0 10^x :
022 3 = 2 + K 1 x 2 / K 2 + K 1 :
037 IF 3 = 1 : 2 : 3 : 3 :
048 ST# 2 : 2 = 2 + K 1 :
058 ST# 3 : ANS 2 :

Ensuite, C.Ret a proposé une formule approchée qui malheureusement ne donne pas toujours le bon résultat, mais il m'a donné l'idée de reprendre le calcul en cherchant une formule approchée plus simple que l'algorithme précédent.
En repartant de l'intervalle défini ci-dessus, si ux = n alors
(n²-n)/2 < x-1 donc n² < 2(x-1) + n donc n étant entier on a n = INT(SQRT(2(x-1) + n))
que l'on peut approximer par INT(SQRT(2(x-1) + INT(SQRT(2(x-1)))))
On peut vérifier que cette approximation donne de très bon résultats jusqu'à de très grandes valeurs de x (999.999.999) voire plus sur la 34S, au delà en fonction des machines on se heurte aux erreurs d'arrondi sur le calcul des racines carrées.

Ce qui donne en 12 pas sur HP 41C:

Code : Tout sélectionner

01 LBL"BR         07 SQRT
02 1              08 INT
03 -              09 +
04 2              10 SQRT
05 *              11 INT
06 ENTER          12 RTN

Enfin dprtl a eu l'idée d'utiliser l'arrondi de l'affichage en FIX 0 qui évite le test de l'algorithme initial, ce qui m'a donné l'idée de ce programme sur WP 34S en 6 pas:

Code : Tout sélectionner

01 LBL A
02 DEC X
03 RCL+ X
04 SQRT
05 ROUNDI
06 RTN

Je crois que seule la WP 34S dispose l'instruction ROUNDI: arrondi à l'entier le plus proche.

[C.Ret]

Depuis les recherches mues par le MPO 75, j'utilise le même algorithme :

Code : Tout sélectionner

1 " " AREAD N : K=INT (√(8N-7)/2-.5 : PRINT N,K+(KK+K+2<2N) : END

J'utilise ci-dessus k1 = √(8N-7)/2-.5 qui est la racine positive du binôme k²+k+2 = 2n provenant de l'équation 1+ (k(k+1))/2 = n.
En effet, on recherche k tel que U(n) = k ou U(n)=k+1 sachant que n = 1 +2 + 3 + ... + k ou n = 1 + 2 + 3 + ... + k + k+1 .
En effet dans la série de U(n), il ne peut y avoir plus de k fois k. Ce qui signifie, que le U(n) maximum qui vaut k et obtenu pour l'indice maximal m tel que m = 1 + 2 + 3 + ... k c'est à dire m =1+(k.(k+1)/2 .

Je recherche donc dans un premier temps la valeur k solution de k²+k+2=2n qui a deux racine k1 = √(8N+1)/2-.5 et k2 = -√(8N+1)/2-.5
Seule la racine positive convient. Je l'utilise pour calculer m = 1 +(k(k+1)/2) et vérifier que n ne dépasse pas cette limite ce qui indique que U(n) = 1+k

Ce qui est remarquable, c'est que la formule utilisée par Zpalm utilise la racine carrée de 2n. C'est une approximation qui permet d'obtenir le même résultat avec un code plus court
Cela provient du fait que lors de la recherche de k, on peut utiliser aussi le polynôme k²+2k+2 = 2n qui a pour racine positive k = √(8n)/2-1 = √(2n)-1
Le résultat de cette méthode est identique, car dans la somme 1+ 2 + 2 + 3 + 3 +3 + ... + k + k il peut y avoir plusieurs fois la valeur k. rechercher une approximation de k à l'aide de k²+k+2=2n ou k²+2k+2=2n est donc quasiment équivalent.

Code : Tout sélectionner

1 " " AREAD N : K=INT √2N-1 : PRINT N,K+(KK+K+2<2N) : END