Misez p'tit Optimisez n°54 : simplification de racines

[Céline]

Sommaire des MPO

Bonjour à tous,

vous connaissez la fx-92 Collège ? Entre autres extraordinaires fonctionnalités, elle simplifie les racines carrées :

Code : Tout sélectionner

sqrt(96)=4*sqrt(6)

Je vous propose de faire la même chose avec vos pockets ou calculatrices.
Pour que ça ait un sens, utilisez une machine qui ne le fait pas déjà.
Je posterai plus tard ce que j'ai fait en basic, en espérant que vous voudrez bien y jeter un oeil pour me dire comment l'améliorer.

Bonne fin de semaine.

[C.Ret]

Oh!

Est-ce qu'un programme qui dit que √25 = 5.√1 ou que √47=1.√47 peut convenir pour ce M.P.O. ?

[babaorhum]

premier jet en basic PC-1500 ...

Code : Tout sélectionner

1 "S" AREAD N : A=1
2 FOR I=2 TO INT (N/2):R=N/I/I: IF R = INT R THEN LET A=A*I
3 NEXT I : PRINT "√";N;" = ";A;"√";N/A/A

Pas super rapide mais ca marche je crois bien... Au suivant !

EDIT : cf msg de C.RET, ce pgm affiche effectivement √25 = 5√1 ...

[Céline]

Est-ce qu'un programme qui dit que √25 = 5.√1 ou que √47=1.√47 peut convenir pour ce M.P.O. ?

Oui parfaitement. Vous êtes libres de la sortie.

[Céline]

Code:
1 "S" AREAD N : A=1
2 FOR I=2 TO INT (N/2):R=N/I/I: IF R = INT R THEN LET A=A*I
3 NEXT I : PRINT "√";N;" = ";A;"√";N/A/A

Non, pour racine(96) il donne 8*racine(1,5).
Pour la boucle tu peux t'arrêter à racine(n), ça fait déjà gagner du temps.

Je propose le mien :

Code : Tout sélectionner

10 : "S" AREAD N
20 : E=1
30 : FOR X=2 TO RACINE(N)
40 : D=N/(X*X):T=D-INT D
50 : IF T=0 GOSUB 100
60 : IF T=0 GOTO 40
70 : NEXT X
80 : PRINT E;"RACINE";N
90 : END
100 : E=E*X:N=D
110 : RETURN

[babaorhum]

Argh !!

Tu as raison Céline mon équipe de béta testeur m'a fait remonter une fiche d'anomalie mais trop tard pour la diffusion - j'envoie une réclamation à l'équipe développeur tout de suite ... j'en profite pour tester ta solution (et OK pour le racine de n)

Merci de votre perspicacité - entschuldigen Sie ...

[C.Ret]

Ah! Rapide !

Mais je suis surpris ! Je m'attendais à un test d'arrêt en fonction de SQR(N) et non N/2 ??

D'où ma version (pour SHARP PC-1211):

Code : Tout sélectionner

1:"S" AREAD X : P=1:R=ABS X:I=2:N=3:S=1:K=0:C$=".√";IF X<0 LET C$="i√"
2:Q=R/II:IF Q=INT Q LET P=PI,R=Q:GOTO 2
3:IF Q>1 LET I=N, S=-S, K=K+(S<0), N=6K+S:GOTO 2
4:PRINT "√";X;"=";P;C$;R : END

Avec
X = valeur dont on affiche la racine
P = facteur quadratique
R = radical
C$= indicateur de valeur complexe

Q = quotien quadratique = R/I²
I = facteurs successifs testés jusqu'à ce que I²>R (et donc Q<1)
N = facteur premier (enfin presque) suivant
S,K = paramètres pour construire N

Comme le SHARP PC-1211 n'est pas rapide, je me limite autant que possible à tester des facteurs premiers !

Et en plus, mon PC-1211, contrairement au PC-1500, sait ce qu'est un nombre complexe et donc afficher proprement une racine négative !

Par exemple, pour √61685, seuls les facteurs 2, 3, 5, 7, 11, 13, 17, 19 et 23 sont testés et on obtient √61685=13.√365

[Céline]

C'est extraordinaire C.Ret, tu fais mieux que la fx-92 Collège, qui elle ne traite pas les nombres complexes !
Je croyais pourtant cette machine indépassable

[babaorhum]

Excellent C.Ret, j'adore !

J'ai une version 2 qui a l'air de mieux marcher ... mais qui reste cantonné au monde réel (c'est a dire qui plante si on rentre un nombre négatif )

Code : Tout sélectionner

1 "S" AREAD N : M= N : A=1 : FOR I=2 TO SQR N
2 R=M/I/I: IF R = INT R THEN LET A=A*I : M=R : GOTO 2
3 NEXT I : PRINT "√";N;" = ";A;"√";N/A/A

Au fait Céline, tu programmes avec Pockemul ? (j'ai cru comprendre que tu n'étais pas encore équipée ...).
Je n'ai pas encore testé ta version ...

[Céline]

Au fait Céline, tu programmes avec Pockemul ? (j'ai cru comprendre que tu n'étais pas encore équipée ...).

Non un collègue m'a prêté son pc-1500A. J'adore !

[babaorhum]

Non un collègue m'a prêté son pc-1500A. J'adore !

bien !!!
Le basic, c'est super rapide mais pas très optimisé - la preuve ici - les solutions en RPL/RPN, ca demande un peu plus de temps ... elles ne vont pas tarder ... je le sens ...

[C.Ret]

Rien de tel que de programmer sur une vraie bécane.

Même si je suis un grand fan du travail de Remy et que j'utilise très souvent Pockemul pour programmer et tester des machine que je n'ai jamais pu toucher pour de vrai

En plus, j'aime bien le code de Céline.
D'abords parce que c'est un programme qui fonctionne et qui est très clair. Il pourra être adapté à toute sorte de machines.
Ensuite parce qu'il utilise l'instruction AREAD pour prendre la valeur à partir de l'affichage ou du dernier calcul fait sur la machine, ce qui en fait bien plus qu'un programme, c'est une véritable fonction utilisateur.
J'aime bien ce principe du code de l'utilisateur qui enrichit la bibliothèque de fonctions (ou programmes) de la calculette.

Par contre, je n'ai qu'un seul petit reproche, il n'est pas, dans cette première version parfaitement M.P.O.isé !

N'y aurait-il pas moyen de le modifier pour qu'il fasse et produise exactement les mêmes résultats mais en effectuant un peu moins d'opérations et surtout en prenant moins d'octets ou de lignes de code dans la mémoire du PC ?


Par exemple, je vois que les lignes 100 et 110 font partie d'un sous-programme. Celui-ci ne peut-il pas tenir sur une seule ligne (ce qui diminue l'emprise mémoire).
Je supprimerais donc la ligne 110 en collant le RETURN à la fin de la ligne 100 :

Code : Tout sélectionner

100:E=E*X:N=D:RETURN

Malheureusement, ce sous-programme n'est appelé que par une seule partie du code (à la ligne 50). Est-ce nécessaire d'utiliser un sous-programme qui n'est pas partagé par plusieurs parties du code ? Nous ne sommes pas là en RPN ou il faut segmenter à cause des test/sauts limité à un seul pas.

Ne pourrait-on pas par exemple mettre le code du sous programme dans le programme directement ?

Mais je vois à l'instant que les lignes 50 et 60 commencent toutes les deux par le même test. Là aussi, on pourrait regrouper pour faire plus M.P.O.

Code : Tout sélectionner

50:IF T=0 GOSUB 100:GOTO 40

aura le même effet que les deux lignes 50 et 60 sans la répétition du test (plus rapide à l'exécution et surtout plus court en mémoire ) Il me semble que Céline avait posé une question à ce sujet. Mais personne n’avait pris la peine de lui répondre !

Comme nous avons constaté que le sous-programme n'a pas de raison d'exister, on peut encore raccourcir :

Code : Tout sélectionner

50:IF T=0 LET E=E*X,N=D:GOTO 40

Mais ne peut-on pas se débarrasser d'autre(s) ligne(s) inutile(s). Mais attention, sans pour autant supprimer des étapes ou des instructions.

Il est clair que les lignes où se fait un branchement ne doivent pas disparaitre, c'est à dire qu'il faut conserver la ligne 10 (à cause du label "S" entrée du programme), la ligne 40 (à cause du saut GOTO 40 de la ligne 50/60), la ligne 70 qui se trouve après un test (qui impose un saut de ligne quand il n'est pas satisfait) et la ligne 100 (si l'on avait conservé le sous-programme - mais je lui ai déjà réglé sons compte à celui-là).

Donc, d'après moi, les lignes 20, 30, 80 et 90 doivent pouvoir se caser ailleurs! C'est à dire dans les lignes "obligatoires".

Même souci d'économie pour les variables. Par exemple, la variable T est fort bien nommée. Il est clair que T signifie ici TEST. Elle n'est utilisée que pour cela d'ailleurs. Mais ce n'est peut-être pas nécessaire d'utiliser une variable juste pour mémoriser un résultat booléen. D'autant plus que j'ai déjà concaténé les deux lignes 50 et 60. Le TEST n'est donc plus effectué qu'une seule fois !

C'est la manie des M.P.O., il faut tout faire disparaitre, sous-programme univoque, variable temporaire à usage unique, ligne superflue, etc...

Bon, rassemblons les instructions sur les lignes "obligatoires", celles imposées par la logique des sauts et renvois de ligne :

Code : Tout sélectionner

10 : "S" AREAD N : E=1 : FOR X=2 TO √N
40 : D=N/X/X : IF D=INT D LET E=E*X : N=D : GOTO 40
70 : NEXT X : PRINT E;"√";N : END

Et pas mal. J'aime bien ce programme. Il est même bien plus court et bien plus MPO que le mien et presque aussi que celui de babaorhum mais avec l'énorme avantage qu'il fonctionne bien mieu (cf. ex de 96 !)

Par conte, on peut copier l'idée de babaorhum et n'utiliser qu'une seule variable accumulatrice des facteurs quadratiques et on obtient bien alors le même code !

Mais quand même, c'est votre algorithme qui me posent problème.

Pour calculer √1073741824, vous avez réellement besoin de compter et tester tous les entiers entre 2 et 32768 ?

De ne tester que 2 et 3 n'est-ce pas suffisant ?
Une boucle FOR TO ... NEXT dont les bornes sont fixées est-elle bien appropriée ?
L’arrêt de la recherche des facteurs n’est-elle pas influencée par le nombre et la qualité des facteurs déjà trouvé ?

D'ou cette dernière proposition :

Code : Tout sélectionner

1:INPUT X : P=1 : R=X : I=2 : DO : IF R MOD I*I THEN I=NEXTPRIME(I) : ELSE P=P*I : R=R/I/I 
2:LOOP UNTIL R<I*I : PRINT "√";X;"=";P;".√";R : END

Evidemment, il faut avoir une machine avec un BASIC MicroSoft. Je n'en connais pas qui tienne dans une poche !

A défaut, une calculette RPL :

Code : Tout sélectionner

                       4:    3:    2:    1:                     
                                          x
« 1 2                         x     1     2      @ Initialise P := 1 et i :=2 (avec r := x )
  WHILE                       r     p     i
     ROT                      p     i     r      @ Positionne R dans la pile
     OVER SQ           p      i     r     i²     @ Calcule i²
     DUP2 >                                      @ Boucle Tant que R>i²
  REPEAT                    
     IF DUP2 MOD                                 @  R et i² multiples ?
     THEN                                        @-> NON  (R MOD i²<>0)
        DROP ROT ROT          r     p     i      @         suprime i²
        NEXTPRIME             r     p    i'      @         incrémente i (ou i devient nombre premier suivant :)
     ELSE                                        @-> OUI  (R MOD i²==0)
        /                     p     i    r/i²    @         R := R/i²
        OVER 4 ROLL *         i  r/i²    i*p     @         P := P*i
        ROT                  r'     p'    i 
     END
  END
  DROP SWAP DROP                    p     r      @ suprime valeur résiduelle de la pile
  'a*√b'                      p     r   '~~~~'
     4 ROT EXSUB
     1 ROT EXSUB                                 @ et formate le résultat sous forme d'une expression algébrique 
»
                                        'P*√R' 
   

Bon, ce n’est qu’un premier jet. Je donne comme excercice de M.P.O.iser ce dernier code !

Les utilisateurs de HP28S devront fabriquer leur propre instruction NEXTPRIME (ou la remplacer par 1 + dans le code ci-dessus).

[Céline]

Merci C.Ret pour les conseils. Maintenant je sais qu'après THEN on peut passer plusieurs instructions du moment qu'elles sont sur la même ligne.

Pour calculer √1073741824, vous avez réellement besoin de compter et tester tous les entiers entre 2 et 32768

C'est bien la valeur limite du programme puisque sur pc-1500A l'instruction FOR ne va "que" jusqu'à 32767.
(Pas gentil ça de faire planter mon programme )

Les utilisateurs de HP28S devront fabriquer leur propre instruction NEXTPRIME (ou la remplacer par 1 + dans le code ci-dessus).

Cette solution permet de contourner la limitation des grands nombres. Maintenant au niveau du temps de traitement il faut trouver un sous-programme qui calcule le nombre premier suivant sans prendre plus de temps que la boucle de 2 à racine(n). En effet ça pourrait faire un autre M.P.O.

[Céline]

J'ai regardé attentivement cette partie de code

1:"S" AREAD X : P=1:R=ABS X:I=2:N=3:S=1:K=0:C$=".√";IF X<0 LET C$="i√"
2:Q=R/II:IF Q=INT Q LET P=PI,R=Q:GOTO 2
3:IF Q>1 LET I=N, S=-S, K=K+(S<0), N=6K+S:GOTO 2
4:PRINT "√";X;"=";P;C$;R : END

et je la trouve vraiment très élégante.
Certes ça ne donne pas que des nombres premiers mais ça divise par 3 la boucle de 1 à racine(n).
Je m'empresse de programmer ça sur le pc-1500A, que ne suis pas sûre de rendre à mon collègue tout compte fait...

Du coup mes considérations sur la programmation d'une fonction NEXTPRIME n'a plus lieu d'être.

Sur pc-1500A, et sans gestion des nombres négatifs, le code de C.Ret donne

Code : Tout sélectionner

10 : "S" AREAD X:P=1:I=2:N=3:S=1:K=0
20 : Q=X/(I*I):IF Q=INT Q LET P=P*I,X=Q:GOTO 20
30 : IF Q>1 LET I=N,S=-S,K=K+(S<0),N=6*K+S:GOTO 20
40 : PRINT P;"RACINE";X:END

[jxano]

Le code de C.Ret est élégant, mais trop subtil pour moi :

Code : Tout sélectionner

40 "S": INPUT "√ ? ";R:F=1,B=4,N=5
42 T=R/4: IF T= INT T LET F=2*F,R=T: GOTO 42
44 T=R/9: IF T= INT T LET F=3*F,R=T: GOTO 44
46 T=R/N/N: IF T= INT T LET F=N*F,R=T: GOTO 46
47 B=6-B,N=N+B: IF N*N<R GOTO 46
48 PRINT F;"√";R: END

Sur mon PC-1475, l'entrée reste sur la ligne du haut et le résultat s'affiche dessous.

Ma bascule B prend alternativement les valeurs 2 et 4. Il y a certainement cette idée chez C.Ret, mais je ne pige pas le reste.