En pleine insomnie dans mon hôtel à Nevers (je suis sûr que vous m'enviez
), boum, je repense à ULAM (que je préfère à Syracuse, en hommage à ce mathématicien qui lors d'une réunion où il s'ennuyait, s'est mis à penser à une spirale qui nous amènera à ce sujet)...
Il y a deux choses qui manquent dans nos programmes :
1 : on optimise au niveau taille, alors que sur les poquettes (et quand j'étais étudiant en informatique), l'optimisation devrait d'abord se faire sur le temps d'exécution (et derrière le nombre de cycles d'horloge). Surtout quand on a du calcul itératif. Ce n'est qu'après et pour la beauté du geste qu'on cherche l'optimisation en taille de code. Or, je pense qu'on y est pas sur la rapidité.
2 : il manque un contrôle dans tout ça pour garantir la fiabilité du calcul (on ne maîtrise pas l'altitude) : on peut dépasser le nombre de chiffres significatifs des machines et fausser le résultat.
J'ai fait un petit programme sur mon émulateur Go71b :
Code : Tout sélectionner
10 s=0 @ input 'Nombre : ';n @ t=time
20 s=s+1 @ if mod(n,2)=0 then n=n/2 else n=n*3+1
30 if n>1 then 20
40 t=time-t @ print 'Vol : ';s;' Temps : ';t
Sur l'émulateur (en simulant approximativement la vitesse réelle de la HP71B), j'arrive pour N=77031 à 15,09 secondes (c'est en gros l'algorithme suivi par tous). J'ai l'impression que l'émulateur va un peu vite quand même
Or, quand on multiplie par 3n et qu'on ajoute 1, on arrive toujours sur un nombre pair (puisqu'on part alors d'un nombre impair), du coup je modifie la ligne 20 en :
On évite alors un contrôle de parité inutile : résultat 12,07 secondes (pas rien quand même !
).
Il faut faire attention également à regrouper un maximum d'instruction sur une ligne en Basic, puisqu'étant interprété, il faut justement faire un minimum appel à l'interpréteur (chaque saut de ligne se paie en millisecondes).
La recherche de rapidité nécessite aussi de connaître à fond les possibilités offertes par le langage résident (où justement on se rend compte à ce moment là de la puissance du basic embarqué). Comme par exemple ici, la possibilité d'avoir la fonction modulo (pour le calcul de reste de division) présente sur la 71B (les casio aussi je crois) alors que sur d'autres machines (comme les sharp
) c'est absent et il faut faire des calculs coûteux en ressources CPU.
Reste à trouver le meilleurs endroit pour mettre le contrôle de dépassement de capacité (qui va nous manger du temps). Normalement avant la multiplication (par exemple si on a une précision à 12 chiffres comme sur la 71B, il faut vérifier que n<333333333333 avant de faire n=3n+1), On se retrouve avec deux If then else imbriqués avec la limitation en taille de la ligne. Gasp, va falloir tester et répartir tout ça sur plusieurs lignes pour voir les meilleurs choix.
Avis aux amateurs !
(Edit : mon code en exemple est faux pour n=1, car je commence par faire le calcul avant de faire le test de l'égalité à 1. C'était pour l'exemple d'optimisation, et bon, l'insomnie est finie, puisqu'il faut que je parte au taf
, donc pas le temps de modifier tout ça pour le moment)
), c'est que je ne comprends pas la 4ème ligne - après l'introduction du 0 - : il manque une commande pour obtenir tous ces n, m et t, non ?
merci le boulot).
