bernouilli92 a écrit :La formule utilisant la récurrence sur hp 28 est la plus élégante mais aussi la moins rapide.
Testée sur hp48sx, voici les temps de réponse :
U(10) : 1.4 secondes
U(20) : 23 secondes
U(30) : 235 secondes
Comptez le double de temps sur un HP-28S/C !
C'est le problème avec cette façon de programmer, simple , concise, élégante, directement recopiée de la page de cours ou du tableau noir (j'ai souvent utiliser cette façon de faire pendant mes longues études).
Dans certains cas on profite même des capacités analytiques et du calcul formel de la machine (très utile à défaut de réel CAS)
Mais le souci majeur est que les calculs sont longs car très très très nombreux.
Pour calculer U(30), il faut évaluer U(29) et U(23) qui eux-mêmes nécessitent d'une part d'évaluer U(28) et U(22) ainsi que U(22) et U(17) ... Et par exemple U(22) est bel et bien évalué deux fois de façons indépendantes. Et donc à chaque pas on multiplie par quatre le nombre d'évaluations...
Quand on réfléchit, on se rend compte que cela est possible grâce à la pharaonique capacité mémoire de ces calculettes et qu'elles calculent vite en fait. Mais beaucoup ...
Pour remédier à cela, le plus commun est d'utiliser la mémoïsation; on sauvegarde au fur et à mesure des calculs les termes de la suite dans une liste en stockée en mémoire (un vecteur dans notre cas car plus économique justement)
Il y a donc deux objets dans le menu USER, la fonction U calculant les termes de la suite u(n) et le tableau de donnée UDAT qui contient les valeurs u(n) déjà rencontrée.
Code : Tout sélectionner
[ 0 1 ] 'UDAT' STO @ Initialise le vecteur de mémoïsation
« -> n @ Prend l'indice
« IFERR
UDAT n GET @ Tente de retrouver sa valeur dans le vecteur mémoïsé
THEN
DROP2 @ En cas d'échec efface de la pile les deux arguments
n n 1 - U - U 1 + @ Calcule u(n)=u(n-u(n-1))+1 par récurrence
@ Cette étape modifie éventuellement le contenu de UDAT
UDAT {n} RDM @ Redimensionne le vecteur de mémoïsation
{ n } 3 PICK PUT @ Mémoïse la nouvelle valeur
'UDAT' STO @ Et sauvegarde dans UDAT
END
»
»
'U' STO
C'est bien plus rapide sauf lors du premier calcul (par exemple si l'on demande tout de suite U(3000).
Autre écueil, il faut s'attendre à un dépassement de capacité mémoire. Le nombre de valeur ne pouvant pas être infinie.
Temps Initiaux* sur un HP-28S:
U(10) 4s U(20) 8s U(30) 16s U(100) 1min 37s U(300) ~5min
Mais U(300) n'est calculé qu'en 5min40s après avoir calculé U(100)
et U(310) est calculé en 7s après avoir calculé U(300).
* en remettant UDAT à sa valeur initiale [ 0 1 ]
Les temps de calcul de tout u(n) avec n inférieur ou égal au plus grand nombre mémorisé sont tous identiques et largement inférieur à 0,3 s
P.S.: Le DROP2 n'est nécessaire que si le mode LASTARG est actif. Dans le cas contraire il faut s'en passer.
J'suis pas prêt de calculer U(5051) ou U(5052) avec cette méthode.
M'reste à chercher une formule ou une méthode brute...