Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Répondre
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Message par C.Ret »

Bonjour à toutes et à tous...

Vendredi dernier, zpalm a posté un lien vers quelques vidéo très bien faites qui illustrent différents sujets mathématiques. Bien que n'ayant pas eut beaucoup de temps ce week-end, je me suis bien amusé à me perdre un peu dans les sujets proposés. Ce qui m'a donné l'idée de ce petit MPO sans aucune prétention mais qui je l'espère sera le bien venu en es temps de dilettante estivale.


Dans l'une de ces vidéo (intitulée "Pi hiding in prime regularities" ENG), où il est question à la fois de la formule de Leiniz concernant PI, de décompositions des nombres en leurs facteurs premiers et de produits de nombres complexes conjugués, il est important à l'un des nombreux virages que prend la démonstration de déterminer le nombre de points de coordonnées entières se trouvant sur un cercle dont le rayon est égal à la racine carré d'une valeur entière.

Afin de vérifier le résultats et valeurs présentés dans cette vidéo, je vous propose de composer sur nos calculettes et pockets, anciens ou récents, un programme qui permette de déterminer le nombre de points de coordonnées entières appartenant au cercle de rayon √n (avec n entier positif ou nul) et ayant pour centre justement l'origine du repère des coordonnées. On supposera que le repère est orthonormé, mais je ne pense pas que cela ait une quelconque importance.

Le programme prendra en entrée la valeur entière n dont la racine correspond au rayon du cercle et donnera comme résultat le nombre de points de coordonnées entières (x,y) qui appartiennent à ce cercle ayant justement pour centre le centre du repère O(0,0).
S'il n'y a aucun point de coordonnées entière appartenant au cercle, le calculateur devra afficher 0.

mpo81_R1.png
mpo81_R1.png (3.22 Kio) Vu 6599 fois
mpo81_R2.png
mpo81_R2.png (3.52 Kio) Vu 6599 fois
mpo81_R3.png
mpo81_R3.png (3.57 Kio) Vu 6599 fois
mpo81_R4.png
mpo81_R4.png (3.78 Kio) Vu 6599 fois
mpo81_R5.png
mpo81_R5.png (4.05 Kio) Vu 6599 fois
Notons, que l'exercice ne demande pas de déterminer ou de préciser les coordonnées de ces points, ni de les afficher. L'idée est de comparer les codes et les performances des machines les plus anciennes, réaliser le code le plus astucieux, le plus courts et/ou le plus optimisé.
Chacun est donc libre d'utiliser l'algorithme et les astuces qui lui plaisent, surtout si cela tire parti des caractéristiques propres et spécifiques de son matériel.
mpo81_R7.png
mpo81_R7.png (3.82 Kio) Vu 6599 fois
mpo81_R25.png
mpo81_R25.png (4.31 Kio) Vu 6599 fois
mpo81_R161.png
mpo81_R161.png (4.58 Kio) Vu 6599 fois
mpo81_R325.png
mpo81_R325.png (6.1 Kio) Vu 6599 fois
Ce MPO n'est donc pas réservé aux calculatrices graphiques, bien au contraire.
Mention spéciale pour le premier code tournant sur Ti-57 ou HP-25 !

Les codes le plus courts resteront-ils les plus adaptés pour déterminer le nombre de points de coordonnées entières sur des cercles de rayon √n de plus en plus grand ?

Et pour un SHARP PC-1211, n est grand à partir de quelle valeur ?
Modifié en dernier par C.Ret le 12 mars 2020 18:01, modifié 3 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Message par Gilles59 »

Bonsoir c.ret,

Joli problème. Sauf erreur, cela revient à trouver le nombre de solutions de (racine carré de r)=a²+b², (r,a,b) € N^3
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Message par C.Ret »

Bonsoir Gilles.

Effectivement, c'est l'une des voies possibles. Mais ce n'est pas la seule, surtout sur les systèmes les plus récents qui ont l'avantage de pouvoir aussi utiliser d'autres astuces, comme la décomposition en produit de facteurs premiers, ou des décompositions en série,...

Chaque méthode a ses avantages et ses écueils. Celles utilisant le triangle de Pythagore a l'avantage de pouvoir fournir facilement les coordonnées des points. Celles utilisant les factorisations ne permettent pas de déterminer les coordonnées aussi directement, mais seront plus efficaces pour les grands cercles.

Tout cela promet de vifs débats, et surtout de forts différents algorithmes en fonction des millésimes des machines ou de la présence d'extension ou autre module sophistiqué, etc. ou simplement le fait de pouvoir réaliser les calculs directement sur des nombres complexes ou non.


héhé hé sans compter les quelques "gruges" que certains ne manqueront pas de proposer :) :P
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Message par Gilles59 »

HP50G mode exact :

Code : Tout sélectionner

«
  ⟶ n                           
  «
    0.                                        @ Le nombre de solutions
    1 `R⟶I(IP(√n))` FOR a                    @ Pour a allant de 1 à la partie entière de r
      IF `TYPE(√(n-a^2))==28.` THEN 1. + END  @ on calcule b, si entier et on ajoute une solution
    NEXT
    4 *                                       @ 4 quarts de cercles => x 4
  »
Modifié en dernier par Gilles59 le 17 juil. 2017 01:24, modifié 2 fois.
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Message par Gilles59 »

CASIO FX-602P en 21 pas

Code : Tout sélectionner

SAC
Min01 √ INT Min00
LBL0
 MR01 - MR00 x² = √ 
 FRAC x=0 XD
DSZ GOTO0
MR09 x 4 =
v325 retourne 24 en 3 sec
Fait la même chose que le programme RPL ci dessus (probablement inutilement compliqué, mais 100% fiable même avec de très grands nombres).
Nul besoin de mode exact pour des rayons 'raisonnables' , pas de pb d'arrondi à priori.
A mon avis, çà doit s'adapter tel quel sur une TI57. Utilise l'instruction XD (normalement pour les stats) pour incrémenter le registre MR09
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Message par C.Ret »

Pas mal.

En fait quand je parlais de n grand, je pensais n faisant quelques dizaines de milliers. c'est déjà beaucoup au vue de la vélocité des processeurs de 1976/1981.

En tout cas, nous sommes d'accord pour la version pythagorique en RPL, sans précaution particulière pour les 'très grands nombres' sur HP28S :

Code : Tout sélectionner

« → n                       //  Valeur entière du rayon R==√n 
   « 0                      //  Initie compteur de solution à zéro
     1  n √ FLOOR FOR a     //  Parcourt arrête a 
        n a SQ - √          //  Détermine b tel que  R²=a²+b² sachant que R²=n car R=√n héhé !! 
        FP NOT +            //  Test si b est entier et ajoute le résultat au compteur
     NEXT                   //  a suivant
     4 *                    //  Multiplie le compteur par 4 pour tenir compte des 4 secteurs du cercle
   »
»                           
'MPO81' STO

Usage:
1:      n    →      1:       p      

Par contre, sur HP50g, j'aurai entrevu une version utilisant l'algorithme de décomposition un peu comme sur l'HP-prime:

Code : Tout sélectionner

EXPORT MPO81(n)
BEGIN
 RETURN 4*ΣLIST(EXECON("(&1=1)-(&1=3)",idivis(n) MOD 4)); 
END;
On retrouve bien la multiplication par 4 pour les quetre secteurs du cercle, mais je vous laisse deviner ce que vient faire le modulo 4 et cet étrange soustraction entre les valeurs 1 et 3.

Pour vous aider, je donne la traduction de cet algorithme sur SHARP PC-1211 :

Code : Tout sélectionner

1 " " AREAD N:S=0:FOR I=1 TO N:K=N/I-4*INT (N/4I,S=S+(K=1)-(K=3:NEXT I:BEEP 1:PRINT N,4S:END
1361 Steps restant soit 63 octets utilisés (et 4 registres )
A oui, c'est un one-liner, à comparer avec son homologue pythagorique :

Code : Tout sélectionner

1 " " AREAD N:S=0:FOR A=1 TO √N:B=√(N-AA:S=S+(B=INT B:NEXT A:BEEP 1:PRINT N,4S:END
1371 Steps (53 octets 4 registres)
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Message par Gilles59 »

C.Ret a écrit : 17 juil. 2017 09:50 Par contre, sur HP50g, j'aurai entrevu une version utilisant l'algorithme de décomposition un peu comme sur l'HP-prime:

Code : Tout sélectionner

EXPORT MPO81(n)
BEGIN
 RETURN 4*ΣLIST(EXECON("(&1=1)-(&1=3)",idivis(n) MOD 4)); 
END;
OK! Par exemple :

Code : Tout sélectionner

 « DIVIS 4 MOD « → n '(n==1)-(n==3)' » DOLIST Sum 4 * »  
Bon maintenant il faut que je comprenne pourquoi ça marche ;D
PS :
J'utilise Sum de la lib GOFERLIST plutôt que ΣLIST qui ne fonctionne pas quand il y a un seul élément dans la liste (c'est la cas pour '1'). en plus Sum est plus rapide. Un peu plus court et un peu plus rapide:

Code : Tout sélectionner

 « DIVIS 4 MOD « DUP 1 SAME SWAP 3 SAME - » Map Sum 4 * »  
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Message par C.Ret »

Je me suis moi aussi posé le problème de la vitesse de détermination.
C'est un bon réflexe, surtout avant de vouloir utiliser son SHARP PC-1211

Voici un petit tableau qui donne les temps observés pour déterminer le nombre de points de coordonnées entières sur le cercle de rayon √n :

Code : Tout sélectionner

----  ----  -------------------------------------------
----  ----                  Algorithmes
  n:  Pts.  Force-Brute  Diviseurs  Pythagore  Facteurs
----  ----  -----------  ---------  ---------  --------
  1     4        5"           2"         3"         1"
  5     8       12"           5"         5"         7"
 25    12       44"          19"        13"         8"
 65    16     1'41"          47"        18"        15"
 75     0     1'39"          55"        20"         3"
161     0     3'29"        1'58"        27"         7"
325    24     7'45"        4'00"        41"        16"
----  ----  -----------  ---------  ---------  --------

Code : Tout sélectionner

Algorithme "Force brute"  (parcourt a et b totalement pour compter les cas r²=a²+b² soit n=a²+b²)
------------------------
1 " " AREAD N:R=INT √N,P=0:FOR A=-R TO R:FOR B=-R TO R:P=P+(N=AA+BB:NEXT B:NEXT A:BEEP 1:PRINT N,P:END
1361 Steps (63 octets & 5 registres)
Temps exécution quadratique: o(n²)

Code : Tout sélectionner

Algorithme "Diviseurs"   (détermine les diviseurs de n et utilise Khi(d) pour dénombrer les solutions)
----------------------
1 " " AREAD N:S=0:FOR I=1 TO N:K=N/I-4*INT (N/4I,S=S+(K=1)-(K=3:NEXT I:BEEP 1:PRINT N,4S:END
1361 Steps (63 octets & 4 registres)
Temps exécution proportionnel: o(n)

Code : Tout sélectionner

Algorithme "Pythagore"   (parcourt a uniquement sur [ 1 √n ], calcul b et compte les b entiers)
----------------------
1 " " AREAD N:S=0:FOR A=1 TO √N:B=√(N-AA:S=S+(B=INT B:NEXT A:BEEP 1:PRINT N,4S:END
1371 Steps (53 octets 4 registres)
Temps exécution puissance fractionnaire: o(√n)

Code : Tout sélectionner

Algorithme "Facteurs" (décompose n en facteurs premiers, somme les Khi(f^i), dénombre les solutions) 
---------------------
1 " " AREAD N:X=N,P=4,F=1
2 F=F+1,I=1,S=1 
3 Q=X/F:IF Q=INT Q LET X=Q,I=FI,K=I-4*INT .25I,S=S+(K=1)-(K=3:GOTO 3
4 P=PS:IF PX>P GOTO 2
5 BEEP 1:PRINT N,P:END
1308 Steps (116 octets - 7 registres)

Temps exécution proportionnel: o(p) avec p = nombre de points solution
(notamment lors de multiplicité par un facteurs 3,7,11,... à une puissance impaire)
Comme on s'y attendait, les codes les plus courts ne sont pas nécessairement les plus rapides.
Quoique comme l'avait fait remarquer gille59 dès son premier message, la méthode utilisant la relation de Pythagore est bien le meilleurs compromis entre simplicité et efficacité. Elle produit donc le meilleurs alliage { MPO / qualité / vitesse }.

Ma préférée reste tout de même la dernière, surtout sur les systèmes de calcul les moins rapides - Qui a dit lent hein ! "Vieux mais pas obsolète" (sic) - . En effet, la grande majorité des cercles de rayon √n ne passent par aucun point de coordonnées entières. Attendre de longues minutes pour voir s'afficher 0. alors que dès le début cela est prévisible est, à mon goût assez désagréable.

Evidemment, si votre CASIO ou HP-' dernier cri ne met que quelque milliseconde, cela va vous laisser indifférent et vous trouverez que je chipote.

Mais c'est bien là tout le drame actuel; comment devenons-nous de moins en moins rentables avec des équipements de plus en plus performants ?
On se le demande.



P.S. : J'oubliais de préciser la fonction Khi(n) qui pour tout entier n positif retourne -1,0 ou 1 selon le schéma suivant:

Code : Tout sélectionner

Pour tout n positif :
       ╭
       │ χ(3)=χ(7)=χ(11)= ... = χ(4k-1) = -1  
χ(n) = ┤ χ(0)=χ(2)=χ( 4)= ... = χ( 2k ) =  0 
       │ χ(1)=χ(5)=χ( 9)= ... = χ(4k+1) = +1
       ╰
Modifié en dernier par C.Ret le 19 juil. 2017 12:12, modifié 2 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Message par Gilles59 »

Gagne 1 pas et n'utilise plus les fonctions STAT sur FX-602P

En 20 pas :

Code : Tout sélectionner

SAC
Min01 √ INT Min00
LBL0
 MR01 - MR00 x² = √ 
 FRAC x=0 4 . M+09
DSZ GOTO0
MR09 
A noter la séquence " x=0 4 . " qui renvoie 4. si x=0 et 0. si x<>0
Ca permet d'ailleurs de faire un test x<>0 manquant sur la 602 avec la séquence "x=0 1 . x=0". Comme quoi je découvre entre des trucs sur la 602P 35 ans après.

Pour n=325, prends environ 3 sec sur 602P et moins d'une seconde sur 603P

PS : en vérifiant avec le timer intégré de la 603P : 0° 0' 0,8 " pour n=325, 4,76" pour n=10000, 15,03" et 24 solutions pour n=100'000, 47,65" pour 1'000'000
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Message par C.Ret »

Pour une fois que le SHARP PC-1211 peut rivaliser avec les CASIO Fx-600P !

J'ai complété mon tableau avec les temps pour n=1, 10, 100, 1 000, 10 000, 100 000 et 1 000 000
Evidemment, seul l'algorithme factoriel permet de tenir le délai. Les autres sont tellement lents, qu'il faudrait remplacer les piles en cours de route :'(

Mais c'est efficace surtout car les puissances de 10 sont faciles à décomposer.
J'ai donc indiqué dans le tableau le détail du calcul de P. Il se fait aux lignes 3 et 4. Les conditions de sortie (test de la ligne 4) sont reportées, car elles expliquent bien comment ce code abrège le calcul quand il n'y a pas de point solution.
2017-07-19-lpo-81-tab1.png
2017-07-19-lpo-81-tab1.png (43.04 Kio) Vu 5348 fois
Le lien entre cet algorithme et celui utilisant les diviseurs de n est donné par la décomposition du calcul de P en fonction de ces facteurs premiers et de leur multiplicité.

Par exemple pour n= 45

La décomposition en facteurs premiers donne :
n = 3² x 5
Le calcul de P s'effectuer donc selon la formule :
P = 4 * ( Khi(3^0) + Khi(3^1) + Khi(3^2) ) * ( Khi(5^0) + Khi(5^1) )
Soit
P =4 * ( Khi(1) + Khi(3) + Khi(9) ) * ( Khi(1) + Khi(5) )
Que l'on peut développer :
P =4 * ( Khi(1)*Khi(1) + Khi(1)*Khi(3) + khi(1)*Khi(5) + Khi(1)*Khi(9) + Khi(3)*(khi(5) + Khi(9)* Khi(5) )


L'anecdote veut que la fonction khi ait l'intéressante propriété d'être multiplicative:
Ainsi, pour tout entier i et j on a : khi(i)*khi(j)=khi(i*j) on a donc :

P =4 * ( Khi(1) + Khi(3) + Khi(5) + Khi(9) + Khi(15) + Khi(45) )

On retrouve bien là, la liste des diviseurs de 45 dont on fait la somme des valeurs de khi.
L'algorithme factoriel et donc équivalent à celui utilisant les diviseurs avec l'avantage que la factorisation met en évidence les cas où, comme pour F=3, il n'y a pas de solution.

Dans les deux cas : P = 4 * ( 1 - 1 + 1 + 1 - 1 + 1 ) = 4 * 2 = 8 et P = 4 * ( 1 - 1 + 1 ) * ( 1 + 1 ) = 4 * 1 * 2 = 8
mpo81_R45.png
mpo81_R45.png (4.43 Kio) Vu 6598 fois
Mais comme le signalait Gilles, il reste encore à comprendre pourquoi Khi et les diviseurs de la racine du rayon donne le nombre de points de coordonnées entières sur le cercle !!

Mais que cela ne nous empêche pas de trouver un code pour les autres machines (HP Canon Texas ... )
Modifié en dernier par C.Ret le 15 déc. 2020 20:40, modifié 4 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Message par Gilles59 »

C.Ret a écrit : 19 juil. 2017 17:35
Image
TRès bien ! Ma 50G mets 1,17 sec pour 1'000'000 avec le programme posté plus haut. Le meilleur score du PC1211 est remarquable.
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Message par zpalm »

Voici l'algorithme de Pythagore sur WP 34S en 17 pas et un registre local:

Code : Tout sélectionner

01 LBL A
02 LocR 001
03 FILL
04 SQRT 
05 IP 
06 ENTER
07 <>YZYZ
08 x^2
09 -
10 SQRT
11 INT?
12 INC .00
13 DSZ Y
14 BACK 007
15 4
16 RCL* .00
17 END
Pour 1E6 il retourne 28 en 7s.

J'ai aussi essayé l'algorithme avec les diviseurs. Le programme est plus long (27 pas et un registre local) mais plus rapide que Pythagore. En effet il n'est pas nécessaire de tester tous les nombres jusqu'à n, comme pour Pythagore on peut se limiter à √n.

Code : Tout sélectionner

01 LBL B
02 LocR 001
03 FILL
04 SQRT
05 IP
06 <>XYXY
07 /
08 FP?
09 SKIP 004
10 x#? Y
11 XEQ 00
12 <>YYZT 
13 XEQ 00
14 RDN
15 DSZ X
16 BACK 010
17 4
18 RCL* .00
19 RTN 
20 LBL 00
21 4
22 MOD
23 2
24 STO- Y
25 RMDR
26 STO-.00 
27 END
Pour 1E6 il retourne 28 en 2s.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Message par C.Ret »

pas mal !
Du coup avec 22 pas sur HP-41C, mon code est loin d'être ridicule (Algorithme Pythagore):

Code : Tout sélectionner

                  T    Z      Y    X       L                      T    Z    Y      X       L
001 LBL "MPO81    :    :      :    n            013 RDN           a    n    p   n-a²
002 ENTER^        :    :      n    n            014 SQRT          a    n    p      b    n-a²
003 SQRT          :    :      n   √n       n    015 FRC           a    n    p   .bbb       b
004 INT           :    :      n    r      √n    016 x=0? SIGN     a    n    p 1⌂.bbb     0⌂b
005 x<>y          :    :      r    n            018 INT           a    n    p    1⌂0  1⌂.bbb
006 0             :    r      n    0            019 +             a    a    n      p     1⌂0
007 LBL 00        :    a      n    p            020 DSE Z GTO 00  :    a    n      p
008 RCL Y         a    n      p    n            022 4             0    n    p      4
009 R↑            n    p      n    a            023 *             0    0    n     4p       4
010 X↑2           n    p      n   a²       a    024 END           0    0    n     4p
011 ST- Y         n    p   n-a²   a²            
012 X<> L         n    p   n-a²    a                                        n     4p
28 est obtenue après environ 5'30" pour 1 E 06
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Message par Gilles59 »

Une version TI-95 PROCALC

Code : Tout sélectionner

STO B SQR INT STO A
0 STO Z STO C
LBL 00
 RCL B - RCL A x^2 = SQR FRC
 IF= Z 4. ST+ C 
DSZ A GTL 00
RCL C 
C'est assez décevant coté vitesse... ~ Casio fx602P et 3 fois moins rapide qu'une 603P, même après un ASM qui améliore la vitesse des GOTO
Dommage également qu'on ne puisse pas faire un test IF=0 sans passer par un registre.

NB : Voir aussi l'article de Gégé et le prog TI95 dans la Gazette n°10, p117-118
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°81 : Coordonnées entières sur un cercle de rayon √n

Message par Gilles59 »

Version NewRPL pour HP50g (copie de celle de CRET)

Code : Tout sélectionner

« 'n' LSTO               //  Valeur entière du rayon R==√n . LSTO pour Local STO en NewRPL
  0                      //  Initie compteur de solution à zéro
  1  n √ FLOOR FOR a     //  Parcourt arrête a 
     n a SQ - √          //  Détermine b tel que  R²=a²+b² sachant que R²=n car R=√n héhé !! 
     FP NOT +            //  Test si b est entier et ajoute le résultat au compteur
  NEXT                   //  a suivant
  4 *                    //  Multiplie le compteur par 4 pour tenir compte des 4 secteurs du cercle
»                           
'MPO81' STO
Les temps de réponse sont quasi instantané pour les 'petits' nombres.

1000000 retourne 28 en 0,8"
1e7 retourne 32 en 1,3"
1e8 retourne 36 en 3" (68" en user rpl)
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Répondre

Retourner vers « Tous les Pockets »