En ce qui concerne les applications pratiques, on connaît bien l'usage des nombres premiers en cryptographie. Quant aux nombres de Keith, dont personne n'est parvenu à prouver qu'ils existent en nombre infini (ou pas), ils ne font actuellement l'objet d'aucune utilisation industrielle en dehors des jeux mathématiques. Cela dit, comme souvent en informatique, "il n'y a de vraiment beau que ce qui ne peut servir à rien" (Théophile Gautier).
Alors, comment vérifier si un nombre 'n' est "de Keith" ou pas ? La méthode est la suivante :
1) on démarre le calcul du premier terme de la suite en faisant la somme des chiffres de 'n'
2) les termes suivants sont obtenus par récurrence, avec des additions dont le nombre d'opérandes est le même que la somme initiale. Pour calculer le terme suivant, on efface un opérande à gauche (le chiffre en rouge dans l'exemple ci-dessous) et on ajoute un opérande à droite qui correspond à la somme précédemment calculée (en bleu ci-dessous).
3) à chaque itération, on vérifie si 'n' apparaît dans la suite. Si c'est le cas, 'n' est un Keith. Par contre, tant qu'on n'a pas dépassé 'n', on poursuit le calcul au (2).
Pour fixer les idées, voici un exemple avec le nombre 197 qui comporte trois chiffres. Les additions successives seront donc à trois opérandes. Les valeurs de la suite sont calculées séquentiellement de la façon suivante :
197
1 + 9 + 7 = 17
9 + 7 + 17 = 33
7 + 17 + 33 = 57
17 + 33 + 57 = 107
33 + 57 + 107 = 197
On s'arrête là, car on vient de retomber sur 197 qui fait partie de la suite. C'est précisément la définition d'un nombre de Keith. Par conséquent, 197 est un nombre de Keith.
J'avais contribué sur ce thème dans le forum silicium avec une version en C61 Basic (Casio), et également avec une version en GFA Basic (Atari ST). Comme cela est requis dans l'énoncé de ce mini défi, mon programme ne se contente pas de vérifier si le nombre donné en entrée est un Keith ou pas ; il affiche le Keith immédiatement supérieur (ou égal).
Pour mémoire, voici la version en GFA Basic :
DIM n%(10)
DO
INPUT "N?",n1%
PRINT TIME$;" ";
DO
l%=INT(LOG10(n1%))+1
m%=n1%
s%=0
FOR i%=l% TO 1 STEP -1
n%(i%)=m% MOD 10
ADD s%,n%(i%)
DIV m%,10
NEXT i%
REPEAT
INC i%
IF i%>l%
i%=1
ENDIF
m%=SHL(s%,1)
SUB m%,n%(i%)
n%(i%)=s%
s%=m%
UNTIL s%>=n1%
EXIT IF s%=n1%
INC n1%
LOOP
PRINT s%;" est un Keith. ";TIME$
LOOP
Alors, si ce score de 4 secondes était bon pour un langage interprété du milieu des années 80, de quoi est réellement capable la WP-34S produite 25 ans plus tard au bas mot ? Son CPU ARM variablement cadencé entre 32 KHz et 40 MHz (mais pas souvent à fond) peut-il battre un Atari ST sur des additions entières ? Pour réaliser ce test, il va d'abord falloir s'arracher quelques cheveux pour écrire une version sur-mesure du même programme, optimisée, mais sans changer l'algorithme.
Bien qu'elle soit moins lisible, car moins bien structurée que la version GFA, du moins en apparence, je suis revenu à ma version en C61 Basic ci-dessous pour servir de référence. Par ailleurs, afin de pouvoir retrouver ses petits dans le programme en mode touche ("keystroke programming") de la WP-34S, les labels (LBL) porteront les même noms que les numéros de ligne du Basic (ex : 30, 40, 60). Voici donc le programme Basic initial :
10 DIM N(10)
20 INPUT"N?",N1
30 L=INT(LOG N1)+1:M=N1:S=0
40 FOR I=L TO 1 STEP-1
50 N(I)=M MOD10:S=S+N(I):M=INT(M/10):NEXT
60 I=I+1:IF I>L THEN I=1
70 M=2*S-N(I):N(I)=S:S=M:IF S<N1 THEN60
80 IF S=N1 THEN BEEP:PRINT S;"est un Keith":END
90 N1=N1+1:GOTO30
Pour l'utiliser, il suffit de taper le nombre N1 en base 10. Le programme commence par calculer le nombre de chiffres de N1 à la ligne 30 (variable L). Ensuite, à partir de la ligne 40 on décompose N1 en chiffres. Ils seront stockés dans le tableau N(I). On sort de cette première boucle avec la somme des chiffres déjà calculée dans S. Les choses se compliquent un peu après la ligne 60 : il s'agit du calcul des sommes S successives. A la ligne 70, M est une variable temporaire qui contient la nouvelle somme. On retrouvera les valeurs de la suite dans le tableau N(I). Mais il n'y a pas de longue addition avec L opérandes comme on pourrait s'y attendre. Pour optimiser le calcul, j'ai utilisé la formule suivante pour passer au terme suivant de la suite :
M = 2*S - N(I)
On peut représenter cette optimisation avec le schéma ci-dessous. La flèche rouge représente l'addition décrite dans la définition initiale, que je calcule différemment à partir des variables bleues :
 | |
|
Il est facile de prouver que cette optimisation est correcte. Par exemple, j'exprime ici les calculs par récurrence à partir d'un nombre dont les 3 chiffres sont respectivement nommés a, b et c :
a, b, c, (a + b + c), b + c + (a + b + c), etc.
Or :
b + c + (a + b + c) = 2 (a + b + c) - a
 |
| Recherche du nombre de Keith immédiatement supérieur pour WP-34S. |
Les registres utilisés, en plus de la pile, sont les suivants :
- R00 : variable nommée N1 dans le programme Basic
- R01 à R12 : tableau N(I)
- R13 : somme S
- R14 : index I
Rien que pour saisir à la main sans erreur ce court programme de 55 pas, comptez entre 10 et 20 minutes, en fonction de votre agilité, et de votre habitude de la machine. Ce que je trouve difficile, pour être rapide avec le clavier surchargé de la WP-34S, c'est qu'il faut mémoriser où sont les fonctions :
- soit en accès direct (par exemple [BASE10] pour basculer en mode entier 64 bits, c'est la touche [10] en jaune. Le symbole "différent", que j'ai noté comme en C au pas 053, c'est la touche bleue puis [1].)
- soit en accès par un menu déroulant (par exemple [DROP] dans le menu [P.FCN])
- soit en accès par une combinaison (par exemple [STO->] que l'on saisit avec la touche [STO] puis [->] en haut ; ou encore l'échange de X avec Z, touche [x<>Z], que l'on obtient avec la touche verte [x<>] puis [Z])
Très honnêtement, je ne crois pas qu'un lecteur de ce blog ne recopiera jamais ce programme, ni sur une vraie WP-34S, ni sur un émulateur. Néanmoins, si vous trouvez l'exercice fun, n'hésitez surtout pas à poster un petit commentaire ci-dessous !
Pour critiquer un peu l'usage de la machine, il faut bien avouer que le débug n'est pas enfantin sur WP-34S. Néanmoins, il est possible de faire tourner un programme en mode pas à pas, grâce aux flêches verticales sur la gauche. En outre, la touche [SHOW] (bleue) permet de visualiser à chaque étape le contenu de la pile, ainsi que les registres.
En guise de conclusion, les performances de la vraie calculatrice, avec des piles correctes (sinon le calcul plante), ça donne quoi ? Eh bien, avec 7000 en entrée il faut environ 24s à la WP-34S pour afficher le résultat (7385 est le Keith suivant). On peut remarquer sur ce test que le temps de calcul est approximativement dans la même seconde qu'on soit en mode SLOW ou en mode FAST. C'est donc juste six fois plus lent que le programme en GFA Basic.... et assez laborieux à saisir sur le clavier de la WP-34S ; malgré le fait qu'il y ait moins de touches à taper. Et je ne parle pas des phases d'optimisation, et de mise au point du programme, ardues sur WP-34S. Mais là, ça vient peut-être de moi ! Au final, malgré les souhaits de certains clients (les plus de 50 ans ?) on commence à comprendre pourquoi ce style de programmation en RPN est en perte de vitesse chez HP, au profit du Basic, comme sur la très récente HP Prime.
Dans la vidéo d'illustration ci-dessous, je fais les choses suivantes :
- j'affiche le niveau des piles (2,8 volts)
- je fais défiler le programme que j'ai publié ci-dessus
- je le teste avec les valeurs 100, 197+1, et 7000 :
Aucun commentaire:
Enregistrer un commentaire