La Question (Délicate) d'un Dimanche après-midi bien instable

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

Avatar du membre
Over_score
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 167
Enregistré le : 26 mars 2019 14:55
Localisation : Pas loin de Smartville

Re: La Question (Délicate) d'un Dimanche après-midi bien instable

Message par Over_score »

Schraf a écrit : 09 mai 2022 16:48Si je ne me trompe pas, il faudra insérer 30817 entre la 7e et 8e position avec une instabilité de 0.9375.
Je l'ai fait plus ou moins à la main et je trouve qu'il faut l'insérer entre la 8e et la 9e position avec une instabilité de 0.9556
Comme c'est du travail manuel, je me trompe certainement…
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: La Question (Délicate) d'un Dimanche après-midi bien instable

Message par Schraf »

@Over_score : 👏 Le programme sur ma Ti-83 Plus (1999) me dit également 0.955... en environ 45 secondes.
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: La Question (Délicate) d'un Dimanche après-midi bien instable

Message par C.Ret »

[
Schraf a écrit : 09 mai 2022 16:48Si je ne me trompe pas, il faudra insérer 30817 entre la 7e et 8e position avec une instabilité de 0.9375.
Malheureusement, ce n'est pas la réponse attendue; tu devrais faire comme nous et n'utiliser que des instruments vintages et te méfier de ce que l'on trouve sur le net ou que l'on voit sur YouTube ! :wink:
Over_score a écrit : 09 mai 2022 16:58Je l'ai fait plus ou moins à la main et je trouve qu'il faut l'insérer entre la 8e et la 9e position avec une instabilité de 0.9556
Comme c'est du travail manuel, je me trompe certainement…
Non, je ne pense pas, j'utilise pour ma part un petit code de quatre ligne en BASIC sur on HP-71B et aussi, pour illustrer, un "éclateur de nombre entiers" sur mon Commodore 8 bits dont voici une capture d'écran qui montre que Over-score a trouvé le bon résultat :
QDD 08 mai 2022 Machine à tester la stabilité des nombres 30817.png
QDD 08 mai 2022 Machine à tester la stabilité des nombres 30817.png (11.92 Kio) Vu 3023 fois
On place le nombre à tester au centre de l'écran, bien callé à gauche.
Puis des tirettes placées sous le nombre à tester permettent de changer les chiffres un à un et de le sonder.
Un indicateur coloré a été déposé sur chaque bandelette qui réagit à la primalité ce qui permet d'enregistrer ce qui ce passe.
L'ordinateur comptabilise les c et les p et calcule l'indice de stabilité ou d'instabilité en fonction des cas.

Schraf a écrit : 09 mai 2022 18:29@Over_score : 👏 Le programme sur ma Ti-83 Plus (1999) me dit également 0.955... en environ 50 secondes.
Voilà du bon matériel, mes gamins utilisent toujours leur Ti-83 avec laquelle ils ont passé leur Baccalauréat.

Pour ce même nombre, mon HP-71B mets environ 7 secondes.

Code : Tout sélectionner

10 DESTROY ALL @ DELAY 0 @ INPUT N @ N$=STR$(N) @ T=80-13*SGN(PRIM(N))
20 FOR I=1 TO LEN(N$) @ FOR J=48 TO 57 @ X=VAL(N$[1,I-1]&CHR$(J)&N$[I+1]) @ IF N=X THEN 40
30 IF X<2 THEN C=C+1 ELSE IF PRIM(X) THEN C=C+1 ELSE P=P+1 @ DISP X
40 NEXT J @ NEXT I @ DISP USING "K,XB,K'c',K'p',DD.5D";N,T,C,P,C/(C+P) @ BEEP
[RUN]
? 30817_[END LINE]
31817
30517
30817 P43c2p .95556 "biiip"
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.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: La Question (Délicate) d'un Dimanche après-midi bien instable

Message par Schraf »

@C.Ret : Merci, je vais me méfier pour Youtube 😤 !

Un programme pour la TI-83 (qui n'a ni modulo, ni test de primalité), sans explication pour laisser tout le monde chercher...

Code : Tout sélectionner

PROGRAM:PREM
Ans→V
√(V→W
0→B:2→J
While J≤W and not(B
If 0=fPart(V/J
1→B
J+2→J
If J=4
3→J
End

PROGRAM:INST
Input X
seq(int(10fPart(X/10^(I+1))),I,int(log(X)),0,­1→L₁
dim(L₁→N
0→C:0→T
For(I,1,dim(L₁
For(K,0,9
If K≠L₁(I
Then
L₁→L₃:K→L₃(I
sum(seq(10^(N-C)L₃(C),C,1,N,1
prgmPREM
If B
1+C→C
1+T→T
End
End
End
Disp C
Disp T-C
Disp C/T

Prgm
?30817
          43
           2
 .9555555556
	 Done
Et pour la Ti-89 (testé sur la Titanium) :

Code : Tout sélectionner

inst(x)
Prgm
string(x)→x
0→p:0→t
For k,1,dim(x)
For i,0,9
If string(i)≠mid(x,k,1) Then
mid(x,1,k-1)&string(i)&mid(x,k+1)→s
If isPrime(expr(s)) Then
1+p→p
EndIf
1+t→t
EndIf
EndFor
EndFor
Disp t-p,p,approx(1-p/t)
EndPrgm

inst(30817)
43
2
.955556
Avatar du membre
Over_score
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 167
Enregistré le : 26 mars 2019 14:55
Localisation : Pas loin de Smartville

Re: La Question (Délicate) d'un Dimanche après-midi bien instable

Message par Over_score »

Sur Sharp PC-1500A (de 1982) en 42 secondes pour 30817
6 minutes et 11 secondes pour 2379007
Je n'ose même pas imaginer la durée pour 2666752421 : mon test de primalité est définitivement trop lent !
Les lignes 500 et au-delà sont pour le test de primalité.

Code : Tout sélectionner

10 INPUT "Nombre a tester:";M:N=M:GOSUB 500:O=C:H=0
20 B=1:FOR P=0TO INT LOG M:B=B*10
30 E=M-INT ((M-INT (M/B)*B)/B*10)*B/10:I=E
50 IF I<>MLET N=I:GOSUB 500:H=H+C
60 I=I+B/10:IF I<E+BTHEN 50
70 NEXT P
75 PRINT 9*P-H;H
80 IF OTHEN PRINT "Instab=";((9*P)-H)/(9*P):END
85 PRINT "Instab=";H/(9*P):END

500 R=INT SQR N:D=0:C=0

510 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
511 IF D>RTHEN RETURN
512 D=D+1:IF INT (N/D)*D=NLET C=1:RETURN
513 IF D>RTHEN RETURN
514 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
515 IF D>RTHEN RETURN
516 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
517 IF D>RTHEN RETURN
518 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
519 IF D>RTHEN RETURN

600 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
601 IF D>RTHEN RETURN
602 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
603 IF D>RTHEN RETURN
604 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
605 IF D>RTHEN RETURN
606 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
607 IF D>RTHEN RETURN

610 D=D+6:IF INT (N/D)*D=NLET C=1:RETURN
611 IF D>RTHEN RETURN
612 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
613 IF D>RTHEN RETURN
614 D=D+6:IF INT (N/D)*D=NLET C=1:RETURN
615 IF D>RTHEN RETURN
616 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
617 IF D>RTHEN RETURN

620 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
621 IF D>RTHEN RETURN
622 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
623 IF D>RTHEN RETURN
624 D=D+6:IF INT (N/D)*D=NLET C=1:RETURN
625 IF D>RTHEN RETURN
626 D=D+6:IF INT (N/D)*D=NLET C=1:RETURN
627 IF D>RTHEN RETURN

630 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
631 IF D>RTHEN RETURN
632 D=D+6:IF INT (N/D)*D=NLET C=1:RETURN
633 IF D>RTHEN RETURN
634 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
635 IF D>RTHEN RETURN
636 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
637 IF D>RTHEN RETURN

640 D=D+6:IF INT (N/D)*D=NLET C=1:RETURN
641 IF D>RTHEN RETURN
642 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
643 IF D>RTHEN RETURN
644 D=D+6:IF INT (N/D)*D=NLET C=1:RETURN
645 IF D>RTHEN RETURN
646 D=D+8:IF INT (N/D)*D=NLET C=1:RETURN
647 IF D>RTHEN RETURN

650 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
651 IF D>RTHEN RETURN
652 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
653 IF D>RTHEN RETURN
654 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
655 IF D>RTHEN RETURN
656 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
657 IF D>RTHEN RETURN

660 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
661 IF D>RTHEN RETURN
662 D=D+8:IF INT (N/D)*D=NLET C=1:RETURN
663 IF D>RTHEN RETURN
664 D=D+6:IF INT (N/D)*D=NLET C=1:RETURN
665 IF D>RTHEN RETURN
666 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
667 IF D>RTHEN RETURN

670 D=D+6:IF INT (N/D)*D=NLET C=1:RETURN
671 IF D>RTHEN RETURN
672 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
673 IF D>RTHEN RETURN
674 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
675 IF D>RTHEN RETURN
676 D=D+6:IF INT (N/D)*D=NLET C=1:RETURN
677 IF D>RTHEN RETURN

680 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
681 IF D>RTHEN RETURN
682 D=D+6:IF INT (N/D)*D=NLET C=1:RETURN
683 IF D>RTHEN RETURN
684 D=D+6:IF INT (N/D)*D=NLET C=1:RETURN
685 IF D>RTHEN RETURN
686 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
687 IF D>RTHEN RETURN

690 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
691 IF D>RTHEN RETURN
692 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
693 IF D>RTHEN RETURN
694 D=D+6:IF INT (N/D)*D=NLET C=1:RETURN
695 IF D>RTHEN RETURN
696 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
697 IF D>RTHEN RETURN

700 D=D+6:IF INT (N/D)*D=NLET C=1:RETURN
701 IF D>RTHEN RETURN
702 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
703 IF D>RTHEN RETURN
704 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
705 IF D>RTHEN RETURN
706 D=D+4:IF INT (N/D)*D=NLET C=1:RETURN
707 IF D>RTHEN RETURN

710 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
711 IF D>RTHEN RETURN
712 D=D+10:IF INT (N/D)*D=NLET C=1:RETURN
713 IF D>RTHEN RETURN
714 D=D+2:IF INT (N/D)*D=NLET C=1:RETURN
715 IF D>RTHEN RETURN
716 D=D+10:IF INT (N/D)*D=NLET C=1:RETURN
717 IF D>RTHEN RETURN

800 GOTO 600
Edit : modif pour encore accélérer un peu le programme
Modifié en dernier par Over_score le 10 mai 2022 14:34, modifié 4 fois.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2918
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: La Question (Délicate) d'un Dimanche après-midi bien instable

Message par zpalm »

Voici un programme sur HP-41CX (ou C/CV avec fonctions étendues) plus module Sandbox (dans un Clonix-D).

Pour N=30817 il retourne en 45" :
C= 43
P= 2
S= 0,9556

Fonctions utilisées de la HP 41CX ou du module X functions:
ANUM : Alpha number. Find first digit string in Alpha reg.

Fonctions du module Sandbox utilisées:

Code : Tout sélectionner

Function Name  Description            Input                Output                        Author          Source
AINT           Alpha Integer Part     Number in X          Appends Integer part          Frits Ferwerda  ML ROM
DECX           Decrement X            Number in X          Number-1 in X                 Ross Cooling    PPCJ V12 N12 p21
ASUB           Alpha Substitute       Y: position; X:Char  Places char in position       Zengrange       ZENROM Manual
PRIME?         Is X Prime?            Number in X          No: Divisor in X - Yes: none  Jason Delooze   PPCJ V11 N7 p30
X>=0?          X>=0?                  Like X<0?            Skips a line if false         Ángel Martin    SANDBOX Project
Le programme en 43 pas et 3 registres (R00-R02):

Code : Tout sélectionner

001 LBL "QDD"
002 STO 00     // R00:  N
003 LOG
004 INT
005 0
006 STO 01     // Pi=0
007 STO 02     // Ci=0
008 X<>Y       // nombre de digits de N
009 LBL 01     // boucle pour chaque digit de N
010 RCL 00
011 CLA
012 AINT       // "N" dans Alpha
013 X<>Y
014 48.057     // Compteur de boucles	
015 LBL 02     // Boucle de 0 à 9 (ASCII 48 à 57)
016 ASUB       // Remplace le digit y de "N" par x
017 RCL 00     // N
018 ANUM       // Valeur numérique du nombre en Alpha    
019 -
020 X=0?       // Si égal à N on ne le compte pas
021 GTO 03
022 X<> L
023 X=0?
024 GTO 03
025 PRIME?     // Nombre premier?
026 ISG 01     // Pi+=1
027 ISG 02     // Ci+=1
028 LBL 03
029 RDN
030 ISG X	
031 GTO 02     // Prochaine Valeur du digit courant
032 RDN
033 DECX
034 X>=0?
035 GTO 01     // Passe au digit de N suivant
036 RCL 02    
037 R/S        // Affiche Ci
038 RCL 01
039 R/S        // Affiche Pi
040 RCL 02
041 +
042 /          // Calcule Si
043 END        // Fin du programme, affiche Si
EDIT: petite modification du programme ci-dessus, j’ai gagné 2 pas, 2 registres et 14".
Deuxième modification pour gérer correctement les nombres inférieurs à 10, 1 pas de gagné, 2 pas de perdus.
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: La Question (Délicate) d'un Dimanche après-midi bien instable

Message par C.Ret »

Over_score a écrit : 09 mai 2022 23:09 Sur Sharp PC-1500A (de 1982) en 49 secondes pour 30817
Les lignes 90 et au-delà sont pour le test de primalité.
A oui! Il y a pas mal de ligne au-delà de 90. c'est une bonne idée d'utiliser un séquence de facteur pseudo-premier pour cet exercice car les nombres intéressant à tester vont vite être assez grand.

L'incrémentation du diviseur D à priori évite de tester les multiples de 2,3,5 et 7. N'apparait dans cette séquence que les multiples de 11 (et tous les facteurs premiers supérieurs). Belle économie.

Mais? Il n'y a pas de structure de données DATA / READ / RESTORE sur un PC-1500 ? Parce que si c'est le cas, il y a moyen de faire une petite économie de répétitions ?
En tout cas, bel effort!!
zpalm a écrit : 09 mai 2022 23:14 Voici un programme sur HP-41CX (ou C/CV avec fonctions étendues) plus module Sandbox (dans un Clonix-D).

Pour N=30817 il retourne en 45" :
C= 43
P= 2
S= 0,9556

[...]

Code : Tout sélectionner

Function Name  Description            Input                Output                        Author          Source
AINT           Alpha Integer Part     Number in X          Appends Integer part          Frits Ferwerda  ML ROM
DECX           Decrement X            Number in X          Number-1 in X                 Ross Cooling    PPCJ V12 N12 p21
ASUB           Alpha Substitute       Y: position; X:Char  Places char in position       Zengrange       ZENROM Manual
PRIME?         Is X Prime?            Number in X          No: Divisor in X - Yes: none  Jason Delooze   PPCJ V11 N7 p30
X>=0?          X>=0?                  Like X<0?            Skips a line if false         Ángel Martin    SANDBOX Project
[...]
Le programme en 43 pas et 3 registres (R00-R02):

Code : Tout sélectionner

001 LBL "QDD"
[...]
023 X=0?
024 GTO 03
025 PRIME?     // Nombre premier?
026 ISG 01     // Pi+=1
027 ISG 02     // Ci+=1
[...][/quote]

j'étudie ce programme avec beaucoup d'intérêt, hier encore, je cherchais (en vain) quel module utiliser pour disposer d'une fonction PRIME?

J'imagine que le test x=0? avant l'appel de l'instruction PRIME? est necessaire car, comme la fonction PRIM() du modul JPC ROM du HP-71B, l'appel avec un argument égal à zéro pose problème.

Par contre, j'adore l'astuce que constitue l'enchainement PRIME? ISG 01 ISG 02 !! Du grand art, comme toujours :)
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.
Avatar du membre
Over_score
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 167
Enregistré le : 26 mars 2019 14:55
Localisation : Pas loin de Smartville

Re: La Question (Délicate) d'un Dimanche après-midi bien instable

Message par Over_score »

C.Ret a écrit : 10 mai 2022 13:07Mais? Il n'y a pas de structure de données DATA / READ / RESTORE sur un PC-1500 ? Parce que si c'est le cas, il y a moyen de faire une petite économie de répétitions ?
En tout cas, bel effort!!
Oui, il y a bien DATA, READ et RESTORE. Le programme est bel et bien beaucoup plus court, mais également plus lent !
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: La Question (Délicate) d'un Dimanche après-midi bien instable

Message par C.Ret »

Over_score a écrit : 10 mai 2022 14:03Oui, il y a bien DATA, READ et RESTORE READ. Le programme est bel et bien beaucoup plus court, mais également plus lent !
Ah, oui, maintenant je me rappelle, j'ai fait la même constatation sur mon PC-1360. La lecture des DATA consomme du temps, j'avais aussi utilisé une version avec plein de ...D=4:GOSUB 500:D=2:GOSUB 500:D=4:GOSUB ... Les appels trop nombreux consomment aussi du temps et nuisent à l'efficacité globale.


Et en fait, avec l'éditeur des SHARP, il est facile de multiplier les lignes quasi-identique en ne midifiant que le numéro de ligne et la valeur du terme ajouté.
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.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2918
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: La Question (Délicate) d'un Dimanche après-midi bien instable

Message par zpalm »

C.Ret a écrit : 10 mai 2022 13:07 j'étudie ce programme avec beaucoup d'intérêt, hier encore, je cherchais (en vain) quel module utiliser pour disposer d'une fonction PRIME?
La HP-41 Function Database est un bon outil pour retrouver une fonction dans un module.
Le module Sandbox est une mine d'or de petites fonctions en MCode, idéal en particulier pour les MPOs. Pour cette QDD la fonction ASUB est parfaite.
C.Ret a écrit : 10 mai 2022 13:07J'imagine que le test x=0? avant l'appel de l'instruction PRIME? est necessaire car, comme la fonction PRIM() du modul JPC ROM du HP-71B, l'appel avec un argument égal à zéro pose problème.
Exactement, j'ai suis tombé sur ce problème en testant des nombres inférieurs à 10.
C.Ret a écrit : 10 mai 2022 13:07Par contre, j'adore l'astuce que constitue l'enchainement PRIME? ISG 01 ISG 02 !! Du grand art, comme toujours :)
:) Le label qui suit a également son importance dans l’enchaînement de la séquence.

Il est possible de gagner trois pas en utilisant CLRG pour initialiser les registres R01 et R02, mais c'est un peu violent... et comme c'est en dehors des boucles on ne gagne rien en temps d’exécution.
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: La Question (Délicate) d'un Dimanche après-midi bien instable

Message par C.Ret »

Over_score a écrit : 09 mai 2022 23:09 Edit : modif pour encore accélérer un peu le programme
J'ai moi aussi modifié mon code pour SHARP PC-1360:
Je passe sur le listing avec les DATA, pour 30817, il met environ 1'32"
J'ai donc modifié en profondeur en m'inspirant du code d'Over_Score, j'arrive pour 30817 en-dessous de la minute (juste 0'58") :D

Pour 2379007, mon SHARP PC-1360 met maintenant 8'35" (c'est pas mal pour un PC-SHARP reconnu pour être peu véloce).

Code : Tout sélectionner

50:INPUT "N=";N:NN$= STR$ N,C=0,T=0: WAIT 0
52:FOR I=1 TO LEN NN$: FOR J=48 TO 57 :P= VAL ( LEFT$ (NN$,I-1)& CHR$ J& MID$ (NN$,I+1,9))
54:IF P<>N GOSUB 70:T=T+1,C=C+ SGN F: IF F=0 PRINT P;
56:NEXT J:NEXT I: P=N: GOSUB 70: PRINT
58:PRINT NN$;"("; STR$ F;")";C;T-C: PRINT C/T: BEEP 1:END

70:F=2,Q=P/F: IF Q= INT Q RETURN
72:F=3,Q=P/F: IF Q= INT Q RETURN
74:F=5,Q=P/F: IF Q= INT Q RETURN
76:F=7,Q=P/F: IF Q= INT Q RETURN
78:F=11,Q=P/F: IF Q= INT Q RETURN
79:IF F>Q LET F=0: RETURN
80:F=2+F,Q=P/F: IF Q= INT Q RETURN
82:F=4+F,Q=P/F: IF Q= INT Q RETURN
84:F=2+F,Q=P/F: IF Q= INT Q RETURN
86:F=4+F,Q=P/F: IF Q= INT Q RETURN
88:F=6+F,Q=P/F: IF Q= INT Q RETURN
90:F=2+F,Q=P/F: IF Q= INT Q RETURN
92:F=6+F,Q=P/F: IF Q= INT Q RETURN
94:F=4+F,Q=P/F: IF Q= INT Q RETURN
96:F=2+F,Q=P/F: IF Q= INT Q RETURN
98:F=4+F,Q=P/F: IF Q= INT Q RETURN
100:F=6+F,Q=P/F: IF Q= INT Q RETURN
102:F=6+F,Q=P/F: IF Q= INT Q RETURN
103:IF F>Q LET F=0: RETURN
104:F=2+F,Q=P/F: IF Q= INT Q RETURN
106:F=6+F,Q=P/F: IF Q= INT Q RETURN
108:F=4+F,Q=P/F: IF Q= INT Q RETURN
110:F=2+F,Q=P/F: IF Q= INT Q RETURN
112:F=6+F,Q=P/F: IF Q= INT Q RETURN
114:F=4+F,Q=P/F: IF Q= INT Q RETURN
116:F=6+F,Q=P/F: IF Q= INT Q RETURN
118:F=8+F,Q=P/F: IF Q= INT Q RETURN
120:F=4+F,Q=P/F: IF Q= INT Q RETURN
122:F=2+F,Q=P/F: IF Q= INT Q RETURN
124:F=4+F,Q=P/F: IF Q= INT Q RETURN
126:F=2+F,Q=P/F: IF Q= INT Q RETURN
127:IF F>Q LET F=0: RETURN
128:F=4+F,Q=P/F: IF Q= INT Q RETURN
130:F=8+F,Q=P/F: IF Q= INT Q RETURN
132:F=6+F,Q=P/F: IF Q= INT Q RETURN
134:F=4+F,Q=P/F: IF Q= INT Q RETURN
136:F=6+F,Q=P/F: IF Q= INT Q RETURN
138:F=2+F,Q=P/F: IF Q= INT Q RETURN
140:F=4+F,Q=P/F: IF Q= INT Q RETURN
142:F=6+F,Q=P/F: IF Q= INT Q RETURN
144:F=2+F,Q=P/F: IF Q= INT Q RETURN
146:F=6+F,Q=P/F: IF Q= INT Q RETURN
148:F=6+F,Q=P/F: IF Q= INT Q RETURN
150:F=4+F,Q=P/F: IF Q= INT Q RETURN
151:IF F>Q LET F=0: RETURN
152:F=2+F,Q=P/F: IF Q= INT Q RETURN
154:F=4+F,Q=P/F: IF Q= INT Q RETURN
156:F=6+F,Q=P/F: IF Q= INT Q RETURN
158:F=2+F,Q=P/F: IF Q= INT Q RETURN
160:F=6+F,Q=P/F: IF Q= INT Q RETURN
162:F=4+F,Q=P/F: IF Q= INT Q RETURN
164:F=2+F,Q=P/F: IF Q= INT Q RETURN
166:F=4+F,Q=P/F: IF Q= INT Q RETURN
168:F=2+F,Q=P/F: IF Q= INT Q RETURN
170:F=10+F,Q=P/F: IF Q= INT Q RETURN
172:F=2+F,Q=P/F: IF Q= INT Q RETURN
174:F=10+F,Q=P/F: IF Q= INT Q RETURN
176:GOTO 79
Je poursuis le principe utilisé par Over_Score qui consiste à limiter dans la boucle de test des facteurs les opérations. Pour cela, je limite les affectations et surtout le nombre de divisions. Je préfère ainsi utiliser une variable de plus, au prix d'une affectation, mais afin de limiter le coût du test (il n'y a pas de fonction FRAC sur ce SHARP).
Second perfectionnement, le test de sortie n'est fait que de temps en temps. L'idée est que la petite douzaine de tests de divisibilité fait en trop coutera moins de temps que de faire le test de sortie à chaque fois. Le test de sortie est uniquement exécuté aux lignes 79, 103, 127 et 151. Aucun calcul n'est fait, comme Q=P/F, vérifier que F>Q revient à vérifier que F²>P c'est à dire F>√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.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: La Question (Délicate) d'un Dimanche après-midi bien instable

Message par Schraf »

Une autre idée pour le test de primalité serait d'utiliser le théorème de Fermat. A part pour pour quelques exceptions (Nombres de Carmichael par exemple qui ne sont pas premiers mais qui passent ce test), ça permettrait (peut-être) d'avoir des temps d'exécutions plus rapides.

Ils en parlent à de nombreuses reprises dans la revue l'OP avec des programmes en BASIC + HP 41 + Ti 57:

PC 1211 & PB 100 - Ordinateur de poche 22 - Page 021 (1984-04).jpg
PC 1211 & PB 100 - Ordinateur de poche 23 - Page 027 (1984-05).jpg
HP 41 - Ordinateur de poche 01 - Page 054 (1981-04).jpg
Ti 57 - Ordinateur de poche 17 - Page 067 (1983-10).jpg
PC 1211 & FX-702 POrdinateur de poche 20 - Page 053 (1984-01).jpg
Avatar du membre
Over_score
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 167
Enregistré le : 26 mars 2019 14:55
Localisation : Pas loin de Smartville

Re: La Question (Délicate) d'un Dimanche après-midi bien instable

Message par Over_score »

Code : Tout sélectionner

Q=P/F: IF Q= INT Q
Ce type de construction pose un problème ! Imagine P=9876543211 et F=2
Q = P/F = 9876543211/2 = 4938271606 et pas 4938271605.5 (en tout cas, c'est comme ça sur PC-1500A) et dans ce cas Q=INT(Q) ce qui est faux.

C'est pour cela que j'ai utilisé

Code : Tout sélectionner

IF INT (P/F)*F=P
Avatar du membre
Over_score
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 167
Enregistré le : 26 mars 2019 14:55
Localisation : Pas loin de Smartville

Re: La Question (Délicate) d'un Dimanche après-midi bien instable

Message par Over_score »

Schraf a écrit : 10 mai 2022 20:10 Une autre idée pour le test de primalité serait d'utiliser le théorème de Fermat. A part pour pour quelques exceptions (Nombres de Carmichael par exemple qui ne sont pas premiers mais qui passent ce test), ça permettrait (peut-être) d'avoir des temps d'exécutions plus rapides.

Ils en parlent à de nombreuses reprises dans la revue l'OP avec des programmes en BASIC + HP 41 + Ti 57:
J'ai tenté d'implémenter le test de primalité de Miller-Rabin : https://en.wikipedia.org/wiki/Miller%E2 ... s_of_bases. Ça marche, mais c'est encore pire en termes de temps d'exécution. Je pense que les nombres à tester sont (beaucoup) trop petits pour que cet algo soit "rentable".
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: La Question (Délicate) d'un Dimanche après-midi bien instable

Message par C.Ret »

Over_score a écrit : 10 mai 2022 20:11Ce type de construction pose un problème ! Imagine P=9876543211 et F=2
Q = P/F = 9876543211/2 = 4938271606 et pas 4938271605.5 (en tout cas, c'est comme ça sur PC-1500A) et dans ce cas Q=INT(Q) ce qui est faux.

C'est pour cela que j'ai utilisé

Code : Tout sélectionner

IF INT (P/F)*F=P
C'est effectivement une très bonne idée, je viens de m'en rendre compte, mon PC-1360 résout 2666752421 en 35 secondes; d'après lui 2666752421 est un multiple de deux !?! :mrgreen:

Aïe Aîe, je vais laisser mon code comme cela, le programme est plus léger et le gain de temps est appréciable pour la majorité des cas que j'étudie. Il me faut simplement ne pas l'utiliser pour des nombres de plus de neuf chiffres.

Schraf a écrit : 10 mai 2022 20:10 Une autre idée pour le test de primalité serait d'utiliser le théorème de Fermat. A part pour pour quelques exceptions (Nombres de Carmichael par exemple qui ne sont pas premiers mais qui passent ce test), ça permettrait (peut-être) d'avoir des temps d'exécutions plus rapides.

Ils en parlent à de nombreuses reprises dans la revue l'OP avec des programmes en BASIC + HP 41 + Ti 57:
Une autre source d'info est une autre Question Très simple d'un Dimanche après-midi.
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.
Répondre

Retourner vers « Tous les Pockets »