Misez p'tit Optimisez n°93 : somme récursive des chiffres d'un entier (racine digitale)

[C.Ret]

[..]Un peu de lecture pour les curieux : https://www.geeksforgeeks.org/finding-s ... gle-digit/[..]

AH! Ces sites de programmeurs petits et jeunes ! Du C+#?+, JAVA, PHP, Python,... mais pas de RPN ou RPL je vais leur écrire pour rajouter un onglet :

Code : Tout sélectionner

01 LBL "DIGSUM
02  9  MOD  x=0?  LASTx
06 END

N.B.: Cette version ne fonctionne pas pour calculer la somme des chiffres de zéro. Mais qui veut calculer la somme d'un nombre qui n'a pas de chiffres ?

[..]
Exemple avec le calcul de factorielles. Bon il n’y a pas de variables locales mais on peut s’en passer.

Code : Tout sélectionner

10 INPUT "A=",A
 20 B = 1
 30 GOSUB 1000
 40 PRINT "......";B;
 50 END
 999 REM *** FACTORIELLE
 1000 IF A = 0 THEN RETURN
 1010 B = B * A
 1020 A = A - 1
 1030 GOSUB 1000
 1040 RETURN

Excellent, il s'agit typiquement qu'une récurrence de queue. La preuve absolue sont les deux dernières lignes 1030 GOSUB 1000 et 1040 RETURN qui devient en fait 1030 GOTO 1000 et cela marche même sur mon pauvre SHARP PC-1211 qui peut suivre cet algorithme en utilisant qu'un seul des ses quatre niveaux d'appels des sous-routines.

Sur SHARP PC-1211 le code suivant ne fonctionne que jusqu'à la factorielle 4 à cause de la limite du nombre d'appels GOSUB emboités:

Code : Tout sélectionner

1:"F" AREAD N:F=1:GOSUB 5:PRINT F:END

5:IF N LET F=F*N,N=N-1:GOSUB 5
6:RETURN

Ce code récursif peut cependant être modifié, car il s'agit bien d'une récurrence de queue : 5:...:GOSUB 5 6:RETURN devient 5:...:GOTO 5

Code : Tout sélectionner

1:"F" AREAD N:F=1:GOSUB 5:PRINT F:END

5:IF N LET F=F*N,N=N-1:GOTO 5
6:RETURN

Et là on peut calculer la factorielle que l'on veut, le SHARP ne fait qu'un seul appel de sous-programme GOSUB.

Ce qui fait , que je m'empresse d'en simplifier la structure. Rien ne sert d'utiliser un GOSUB pour un seul appel !

Code : Tout sélectionner

1:"F" AREAD N:F=1
5:IF N LET F=F*N,N=N-1:GOTO 5
6:PRINT F:END

Il s'agit donc d'un code récursif (récursion en queue) qui l'air de rien ressemble comme deux gouttes d'eau à un code itératif:

Code : Tout sélectionner

1:"F" AREAD N:F=1
5:IF N FOR I=1 TO N:F=F*I:NEXT I
6:PRINT F:END

Mais c'est normal, la fonction factorielle est une primitive récursive qui est donc aussi itérative de base.

L'algorithme déployé qui consiste à transformer la définition récursive de la fonction factorielle en une récursivité de queue à l'aide de deux variables (non nécessairement locales) a justement fait l'objet d'une vidéo (en anglais) Computerphile issue du département Computer Science at the University of Nottingham.
L'idée maitresse est d'utiliser une des variables comme un compteur et l'autre comme un accumulateur. L'exemple avec les nombres de Fibonacci montre qu'il faut parfois plus de variables pour transmettre plus d'arguments.

Illustré en RPL, l'idée pour la factorielle est de faire :

Code : Tout sélectionner

rFACT: « 1 goFACT »
goFACT: « IF  OVER  THEN  OVER * OVER SIGN NEG ROT + SWAP goFACT  END »

(j'aime bien le RPL c'est comme le FORTH, le BRAINFUCK ou l'APL, c'est immédiatement très lisible et intuitif )
c'est à dire en utilisant un RPL plus proche des langages algébriques:

Code : Tout sélectionner

'rFACT=goFACT(n,1)' DEF
'goFACT(n,f)=IFTE( n==0 , f , goFACT(n-SIGN(n),n*f) )' DEF

En utilisant la même stratégie, je propose le code RPL suivant en deux instructions rSDC (run Somme Des Chiffres) qui relance jusqu'à obtenir un résultat et goSDC qui opère le calcul récursivement:

Code : Tout sélectionner

rSDC: « IF  DUP 9 >  THEN  0 goSDC  END »
goSDC: « IF  OVER  THEN  SWAP 10 DUP2 / IP 4 ROLLD MOD + goSDC  ELSE  rSDC  END »

Oui, Marge a raison, c'est pas très clair, plus lisible est:

Code : Tout sélectionner

'rSDC(n)=IFTE( n>9 , goSDC(n,0) , n )' DEF
'goSDC(n,s)=IFTE( n>0 , goSDC(IP(n/10),s+(n MOD 10)) , rSDC(s) ) DEF

Mais bon, avec l'astuce de la preuve par neuf on a aussi plus directement

Code : Tout sélectionner

SDC: « DUP 9 MOD DUP 9 IFTE OVER IFTE »

qui marche aussi avec zéro comme argument.

MPO93 RPL retrospectively problematic logic.gif (17.79 Kio) Consulté 2673 fois

Une version pour nombres strictement positifs comme pour l'HP-41/42 serait

Code : Tout sélectionner

SDC: « 9 MOD DUP 9 IFTE »

ce qui doit bien les 14 ou 16 octets donc parle Bernouilli92.



Comme nous sommes dans un MPO, je m'empresse de donner pour TI-57 LCD un code bien plus court (mais ce code doit être immédiatement adaptable à une vraie TI-57 à leds):

Code : Tout sélectionner

--       St
56       00           C.t              // Met à zéro registre de test t
55       01            ÷
09       02            9
95       03            =
59       04      2nd  Frac
65       05            x
26       06      2nd  x=t?            // x nul ?
15       07           ON/C            // annule multiplication en cours
09       08            9
95       09            =              // Termine calcul en cours s'il existe toujours
57.00    10      2nd  FIX 0 
13       11           R/S

Je passe donc de 28 pas à une dizaine

Il est possible de gagner deux pas (ligne 00 et 10) en demandant à l'utilisateur de préparer sa calculatrice en tapant 2nd FIX 0 et 2nd C.T avant la première utilisation du code.
En postant ce code, je me rends compte qu'il y a moyen d'économiser encore un pas. Je vous laisse chercher comment.

[badaze]

@C.ret bravo !

Il y a du niveau sur ce forum !

PS : A la fac on avait eu un cours sur comment transformer un algo itératif en récursif et vice versa.

[Danny]

La récursivité terminale c’est la vie

[bernouilli92]

Ma solution pour hp48 était la suivante :

Code : Tout sélectionner

« 1 - 9 MOD 1 + »

mais elle ne fonctionne pas avec 0.

J'avais appris il y a très longtemps que pour vérifier si un nombre était divisible par 3, il fallait vérifier si la somme des chiffres l'était.

[Danny]

Eh oui, c’est l’astuce de la mort pour obtenir la racine digitale !

Si le nombre est divisible par 9, sa racine digitale est 9.
Sinon, elle vaut le reste du modulo 9.

Donc le code est super court, sur HP-41 ou 42 ça donne seulement :

Code : Tout sélectionner

9
MOD
X=0?
9 (ou LASTX)

Si on transposait ça directement en RPL, on perdrait de la place avec un IF THEN END, donc l’astuce de Bernouilli permet d’avoir un code aussi optimisé en utilisant juste la pile.


(et pas besoin de s’embêter avec zéro )

[C.Ret]

(et pas besoin de s’embêter avec zéro )

Ah! Je me disais aussi, qui peut bien avoir l'envie de sommer les chiffres d'un nombre qui n'en a pas .

Sinon, la structure IF ... THEN .... ELSE ... END gourmande du RPL peut être évitée avec un IFTE unique « 9 MOD DUP 9 IFTE » à comparer avec « 1 - 9 MOD 1 + » qui est plus direct et n'est pas beaucoup plus lourd en octet (sauf sur certaines machines RPL qui ont du mal avec la représentation interne typée des entiers).

[Danny]

Ah pas mal le IFTE !
J'y pense jamais à celui-là

[Gilles59]

Salut tout le monde... Ca fait un bail que je n'étais pas venu suite à divers problèmes (résolus!) et je vois que les passionnés sont toujours là ! Ca fait plaisir

Bon j'ai ressorti ma HP50g en NewRPL. Ma première solution récursive et bien lourde :

Code : Tout sélectionner

«
  -> n
  «
    IF 'n>9' THEN
     0
     0 n SIZE 1 - FOR s
       n s DUP DIGITS + 
     NEXT
     f
    END
  »
»
'f' STO

Remarque : DIGITS n'existe pas en RPL standard. Elle permet d'extraire un chiffre ou une suite de chiffres d'un nombre. Ca fait 144 octets
Bon mais la solution de Bernoulli/Danny/C.RET déchire tout :

Code : Tout sélectionner

« 9 MOD DUP 9 IFTE »

fait 28 octets en NewRPL. L'avantage du NewRPL c'est le multiprécision. Un simple 500 SETPREC et meme programme traitera les nombres de 500 chiffres...

EDIT : D'ailleurs pas besoin de SETPREC, En NewRPL on peut forcer des nombres longs (et expressions algébriques) entre quote :
'1234567895454646464646464464654644564646464645646645465487987987' 9 MOD DUP 9 IFTE EVAL
retourne
6

J'apprécie beaucoup ce fonctionnement en RPL, contrairement à la Prime avec son mode "bicéphale" (mode numérique et mode exact dissoociés)

[Danny]

Intéressant ce NewRPL

[Gilles59]

Intéressant ce NewRPL

Oui. Il est très complet maintenant. Pas de mode graphique encore mais:
-environ 100 fois plus rapide que du RPL sur un hdw hp50g, et même plus pour les traitements de liste par exemple ou les programmes récursifs. Ça tourne aussi vite qu’une hp prime (même plus vite parfois) alors que le Hdw de la 50g est bien en-dessous.
- la précision de calcul est paramètrable
- gestion de variables locales avec LSTO qui manquait cruellement au RPL
-beaucoup plus rapide encore avec l’émulateur
-plus de mémoire dispo , auto complétion, aide en ligne...

Par contre la nouvelle interface NewRPL est très efficace mais très radicale et assez contre-intuitive au début! Clairement il y a un effort à faire pour s’y retrouver. J’aurai préféré que l’ancienne Interface soit conservée.

En plus le langage va être porté sur d’autres plateformeS ;D Le support du graphisme est prévu.

[C.Ret]

[...]
Bon mais la solution de Bernoulli/Danny/C.RET déchire tout :

Code : Tout sélectionner

« 9 MOD DUP 9 IFTE »

Oui, utiliser la congruence à 9 était la solution de facilité que Danny sous-entend dès le post de lancement.

(...)Comme d'hab, essayez d'éviter de chercher sur les internets sinon vous allez vite trouver la méga astuce pour calculer ça super rapidement (...)Sommaire des MPO

C'est plus rapide , mais tellement moins rigolo à programmer qu'une vraie approche par récurrence.

Sinon concernant l'HP Prime, c'est vrai qu'elle est complètement schizophrène avec ses deux modes de fonctionnement cote à cote. Mais c'est pas sa faute, c'est le cahier des charges, Hewlett Packard ne voulait faire qu'une seule calculatrice et répondre à trop d'utilisateurs potentiels très différents.

Ce n'est pas pour rien qu'il y avait toujours eut des variations entre modèles, c'était pout répondre à un maximum de demandes (je pense à la série des HP Voyager). Mais aujourd'hui des contraintes contradictoires doivent être réunies dans un même et unique produit afin de réduire les coûts de service aux clients à zéro ! Quitte à avoir beaucoup beaucoup moins de clients !

Cela me fait bien plaisir de te re trouver sur le forum.

Mais je suis désolé, j'ai un code NewRPL plus court que le tien :

Code : Tout sélectionner

« 0  0 PICK3 SIZE 1 - FOR i    OVER i i DIGITS +    NEXT  IF DUP 9 > THEN g END » 
'g STO

Ce code laisse dans la pile les étapes de la récurrence:
1337 g affiche
3| 1337
2| 14
1| 5

EDIT: J'oubliais, la version UserRPL :

Code : Tout sélectionner

« STD  →STR
  0
   1 3 PICK SIZE FOR i
    OVER i i SUB STR→ + 
  NEXT
  IF DUP 9 > THEN ug END »
 'ug' STO

Qui elle aussi laisse l'historique dans la pile :

Code : Tout sélectionner

"1234567895454646464646464464654644564646464645646645465487987987" ug renvoie
4: "123456789545464646…
3:                "319"
2:                 "13"
1:                    4

Na! l'HP-28S sait aussi faire la maligne avec des grands nombres