Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

[Ben]

Ah! Une version assembleur! Je vais l'essayer ce soir

Vous avez remarqué, en tout cas pour les nombres à 4 chiffres, souvent, la suite se termine par 6174

EDIT: une petite stats qui ne sert à rien, mais dans 99% des cas, on trouve 6174! Plus exactement, on retrouve 8923 le chiffre 6174 sur les 9000

[zpalm]

Je viens de mettre à jour mon programme pour 41C: passage de 52 à 47 pas et ajout de commentaires.

[cgh]

Je viens de mettre à jour mon programme pour 41C: passage de 52 à 47 pas et ajout de commentaires.

Il est excellent ce petit programme !

[Hobiecat]

Il est excellent ce petit programme !

+1 !

Et je crois que c'est le premier (ou en tout cas un des premiers) MPO où l'assembleur est à l'honneur ! Ce serait intéressant aussi de voir la version optimisée, même si non relogeable.

[cgh]

Et je crois que c'est le premier (ou en tout cas un des premiers) MPO où l'assembleur est à l'honneur ! Ce serait intéressant aussi de voir la version optimisée, même si non relogeable.

Ce n'etait pas vraiment un MPO car il n'appartient pas a la rubrique, mais il y a deja eu des codes assembleurs comme pour ce challenge.

[zpalm]

Et je crois que c'est le premier (ou en tout cas un des premiers) MPO où l'assembleur est à l'honneur ! Ce serait intéressant aussi de voir la version optimisée, même si non relogeable.

Et aussi une version en microcode HP 41!

En attendant, voici une version WP 34S largement remaniée de mon programme pour 41C: grace à la puissance du jeu d'instructions de la WP 34S on passe de 47 à 29 pas et de 13 à 10 registres max utilisés. Seul le nombre de registres correspondant au nombre de chiffres du nombre en entrée est utilisé : par ex. pour un nombre de 4 chiffres les registres R00 à R03 sont utilisés, les autres ne sont pas modifiés.

Code : Tout sélectionner

01 LBL A
02 0              // Indice du premier registre
03 X<>Y
04 SDR 001        // Première boucle: extraction des chiffres
05 IP             // Nombre amputé du premier chiffre à droite
06 RCL L
07 FP             // Premier chiffre à droite au format 0.a
                  // Boucle de sauvegarde par ordre décroissant 
08 STO->Z         // Sauvegarde du chiffre courant dans le registre courant
09 INC Z          // Registre suivant
10 RDN            // On récupère le nombre amputé
11 X#0?           // S’il reste des chiffres à extraire
12 BACK 008       //  on boucle
                  // A la sortie de boucle on a 0 dans X, et le nombre de registres dans Y
13 x<>Y
14 SDR 002        // Compteur de registres pour R-SORT
15 R-SORT         // On trie les registres par valeur croissante
16 RCL L          // On récupère le nombre de registres
17 <>ZZXX         // X=Y=0, Z=T=nombre de registres
18 DEC T          // On décrémente T pour en faire un index du registre courant
                  // Boucle de génération des nombres c et d de la formule
                  //  Y va contenir d (le nombre avec les chiffres par ordre décroissant) 
                  //  X va contenir c (le nombre avec les chiffres par ordre croissant) au format 0.N
19 SDR 001        // On divise par 10 la valeur de c pour faire de la place pour le prochain chiffre : 0.0N
20 RCL+->T        // On ajoute à c le chiffre courant (par ordre décroissant) au format 0.a -> 0.aN
21 X<>Y           // On permute c et d
22 RCL+->T        // On ajoute à d le chiffre courant -> N.a
23 SDL 001        // On multiplie d par 10 -> Na
24 X<>Y           // On permute c et d
25 DSL T          // On passe au chiffre suivant
26 BACK 007
27 SDL->Z         // On décale à gauche 0.c du nombre de chiffres pour obtenir c
28 –              // On soustrait pour obtenir K(n)
29 END            // Le programme s’arrête avec le résultat dans X. Une pression sur A le relance 

Sur les 29 pas du programme, 14 utilisent des instructions de la WP 34S que l'on ne trouve pas sur la 41C.

[C.Ret]

Je viens de mettre à jour mon programme pour 41C: passage de 52 à 47 pas et ajout de commentaires.

Il est excellent ce petit programme !

Bof, je le trouve un poil un peu long et il utilise un peu trop de registres et surtout des modules ou des HP-41 bien chères. Ah! Non zut, je confonds avec le listing ci-dessus pour la WPS !

Je propose 45 pas (avec le END final inclus comme il se doit), n'utilisant les registres R00 à R11 (soit douze registres) et ne nécessitant aucun module particulier, y compris module mémoire, même si vous ne possédez qu'une très modeste HP-41C. (Il vous faudra éventuellement 4 piles LR1 - mais bon tout le monde sait qu'il en faut 4 et pas 3 comme pour un HP-28S)

MPO 85 HP-41C prgm.gif (126.46 Kio) Consulté 2574 fois

Pour lancer la première transformation, saisir le nombre à transformer puis presser [ XEQ ] [ Alpha ] [ M ][ P ][ O ][ ][ 8 ][ ][ 5 ]( Alpha ].
Les transformations suivantes sont obtenues simplement en pressant sur [ R/S ].

[cgh]

Et aussi une version en microcode HP 41!

Vi vi vi... J'y pense

[cgh]

Je propose 45 pas (avec le END final inclus comme il se doit), n'utilisant les registres R00 à R11 (soit douze registres) et ne nécessitant aucun module particulier, y compris module mémoire, même si vous ne possédez qu'une très modeste HP-41C. (Il vous faudra éventuellement 4 piles LR1 - mais bon tout le monde sait qu'il en faut 4 et pas 3 comme pour un HP-28S)

Dans ton programme, tu ne tries pas les chiffres mais tu comptes les occurences de ceux-ci et tu "recompose" les 2 nombres avec les chiffres en ordre decroissant et croissant. C'est ce que j'ai fait dans le programme assembleur pour PC-1500
Effectivement, cela s'avere plus simple, de plus, que je n'avais pas trop envie de me lancer dans un tri en "LH5801 in the text"

[C.Ret]

Tout à fait, c'est d'ailleurs la même stratégie qu'utilise ben dans son code pour VIC-20 et donc aussi le même principe dans la version C128 que j'ai présentée.

Le comptage des occurrences d'entités ordonnées et en réalité la base du tri par comptage.

Les programmes de zpalm utilisent un tri à bulle (ou insertion ??) dont l'implémentation n'est pas plus difficile qu'un comptage et donne l'énorme avantage de construire un tableau trié, ce qui facilite grandement le calcul du résultat.

[cgh]

Il est vraiment marrant et interessant ce MPO...
Petite question: Quelles sont les applications de l'algorithme de Kaprekar ?

[C.Ret]

Je ne connais pas d'application à cet algorithme.

EDIT: une petite stats qui ne sert à rien, mais dans 99% des cas, on trouve 6174! Plus exactement, on retrouve 8923 le chiffre 6174 sur les 9000

Ah! Ah! Et avec des nombres à trois chiffres, que disent les statistiques ?

[zpalm]

Bof, je le trouve un poil un peu long et il utilise un peu trop de registres et surtout des modules ou des HP-41 bien chères. Ah! Non zut, je confonds avec le listing ci-dessus pour la WPS !

Je propose 45 pas (avec le END final inclus comme il se doit), n'utilisant les registres R00 à R11 (soit douze registres) et ne nécessitant aucun module particulier, y compris module mémoire, même si vous ne possédez qu'une très modeste HP-41C.

Tu as bien raison, mon programme est trop long et utilise trop de registres. Un petit coup de MPOisation et voici une version allégée pour 41C de base: 44 pas et 10 registres (R00 à R09) maximum*.

Une meilleure utilisation de la pile et du registre L permet de se passer des registres 10, 11 et 12 de la version précédente et au passage d'économiser trois pas de programme. Comme sur la 34S le programme n’utilise que le nombre de registres correspondant au nombre de chiffres du nombre en entrée : pour un nombre de 4 chiffres seuls les registres R00 à R03 sont utilisés.

Code : Tout sélectionner

01 LBL "K"
02 ENTER
03 LOG
04 INT            // Nombre de chiffres du nombre en entrée -1
05 1 E-3
06 *              // Conversion en compteur de boucles
07 CLRG           // Efface les registres - à remplacer par CLRGX sur une 41CX*
09 X<>Y           

09 LBL 01         // Première boucle: extraction des chiffres
10 10
11 /
12 INT            // Nombre amputé du premier chiffre à droite
13 LASTx
14 FRC            // Premier chiffre à droite au format 0.a
15 RCL Z          // On récupère le compteur de boucles 
16 STO L          // On le stocke dans L pour la boucle suivante

17 LBL 02         // Boucle de sauvegarde par ordre décroissant dans les registres de 0 à 9
18 X<> IND L      // On permute le registre courant avec la valeur initiale du compteur de boucles 
19 X<=Y ?         // Si le chiffre courant est > au nombre dans le registre courant
20 X<>Y           //  on permute
21 X<> IND L      //  pour stocker dans le registre courant le plus grand des deux et récupérer le compteur de boucles
22 ISG L          // On passe au registre suivant
23 GTO 02         // Boucle autant de fois que le nombre initial a de chiffres

24 RCL Z          // On récupère le nombre amputé
25 X#0?           // S’il reste des chiffres à extraire
26 GTO 01         //  on boucle

27 X<>Y           // A la sortie de la boucle on a 0 dans X,Z,T et le compteur de boucles dans Y,	
28 *              //  on prépare la pile pour la boucle finale :
29 10             //  X=10, Y=0, Z=0, L=compteur de boucles
30 LBL 03         // Boucle de génération des nombres c et d de la formule
                  //  Y/Z va contenir d (le nombre avec les chiffres par ordre décroissant)
                  //  Z/T va contenir c (le nombre avec les chiffres par ordre croissant) au format 0.N 
31 ST/ Y          // On divise par 10 la valeur de c pour faire de la place pour le prochain chiffre : 0.0N
32 RCL IND L      // On récupère le chiffre courant (par ordre décroissant) au format 0.a
33 ST+ Z          // On l’ajoute à c -> N.a
34 ST+ T          //  et d -> 0.aN
35 RDN
36 ST* Z          // On multiplie d par 10 -> Na
37 ISG L          // On passe au chiffre suivant
38 GTO 03

39 LASTx          // A la fin de la boucle on a le nombre de chiffres dans la partie entière du compteur
40 INT
41 Y^X
42 *              // On multiplie .c par  10^nombre de chiffres pour obtenir c
43 –              // On soustrait c de d pour obtenir K(n)
44 END            // Le programme s’arrête avec le résultat dans X. Une pression sur Enter le relance

*Sur une 41C/CV de base l'instruction CLRG au pas 07 efface tous les registres, si l'on dispose d'une 41CX, il vaut mieux la remplacer par CLRGX pour n'effacer que les registres qui seront utilisés par le programme.

(Il vous faudra éventuellement 4 piles LR1 - mais bon tout le monde sait qu'il en faut 4 et pas 3 comme pour un HP-28S)

Pour l'alimentation en électricité de la 41, j'ai acheté ceci.

[C.Ret]

Joli !

J'aime bien deux choses :

• la façon dont les chiffres sont mis dans l'ordre avec les deux X<> IND L
• La façon de mettre au début ou à la fin de c et d en jouant sur le point décimal qui sert en fait de point d'insertion

J'aime, donc je pirate :

MPO 85 HP-41C prgm 3.9.gif (20.02 Kio) Consulté 2470 fois

Avec beaucoup de mal et en m'inspirant du travail de zpalm, j'arrive à un programme de catégorie A qui utilise entre 2 et 11 registres selon le nombre de chiffres qui lui peut varier entre 1 et 10.

Il n'utilise que 39 pas de programme et les fonctions ISG et DSE. La fonction LOG est utilisée au début de la seconde partie pour mettre 1 dans la pile et 10 dans le registre LastX:

Ne cherchez pas de GTO 03, le LBL 03 ne sert que de NOP pour le DSE qui, quelque soit la valeur, doit continuer par l'instruction 036 DSE 00

Il y a en fait trois boucles:

• la boucle Lbl 00 qui décortique chiffre par chiffre le nombre donné en argument (dans X: au lancement),
• la boucle Lbl 01 qui trie les chiffres dans les registres et
• la boucle Lbl 02 qui construit les nombres D et C contenant respectivement les chiffres dans l'ordre décroissant et croissant.

La transformation est effectuée par la soustraction finale D-C.

[Ben]

Cette après-midi, je me suis dit que la FX-602P pouvait aussi faire ce genre de petit calcul, voici le premier jet:

Code : Tout sélectionner

Min02					Sauf le monbre dans Mem02
1 Min06					Mem06 = 0 Coeff de multiplication par 10
20 MinF					MemF=20 Borne du tableau pour le tri (0 à 9 +10)
0 Min04 Min05				Mem04 nombre chiffres croissant Mem05 Chiffres décroissants
LBL1 MR02 / 10 = INT * 10 = Min00	Mem00 Travail, contient le dernier chiffre du nombre 
MR02 - MR00 + 10 = Min00		Tableau commence à la Mem10 (0=Mem10, 1=Mem11, ...)
1 IND M+00				Sert d'indexe pour ajouter 1 au tableau
MR02 / 10 = INT Min02			Enlève 1 chiffre au nombre
x=0 GOTO2 GOTO1
LBL2 10 Min00				Indexe du tableau
LBL3 IND MR00 x=0 GOTO4			Si la valeur du tableau =0 on passe
LBL5 MR04 * 10 + MR00 - 10 = Min04	Calcul la valeur du nombre en croissant
(MR00 - 10) * MR06 + MR05 = Min05	Calcul la valeur du nombre en décroissant
MR06 * 10 = Min06			Multiplie par 10 le Coeff
1 IND M-00				Soutrait 1 au tableau
IND MR00 x=0 GOTO4 GOTO5		Test si la valeur du tableau est à 0
LBL4 1 M+00 MR00 x=F GOTO6 GOTO3	Ajout 1 à l'indexe, jusqu'à 20
LBL6 MR05 - MR04 =			Affiche le résultat

101 Pas - 6 mémoires plus le tableau 10-19. Quand je vois que certains le font en 44 ou 45 pas, je me dis que j'ai encore pas mal de progrès à faire :-/