Turbo nombres premiers
Re: Turbo nombres premiers
Vérif jusqu'à 983040 : 77276+3 nbs 1ers... Ok...
Re: Turbo nombres premiers
Jusqu'à 1966080, on a 146602+3 nbs 1ers... Algo toujours ok...
Re: Turbo nombres premiers
Jusqu'à 3932160, il y a bien 278734+3 nbs 1ers... Algo encore et toujours impeccable... Je ne sais pas sur quel site en ligne j'ai été me br... la nouille pour vérifier mes statistiques, mais, en tout cas, la seule conclusion actuelle que j'en tire, c'est que je me suis ch... dessus pour absolument rien : mon algo semble perfect.
Si quelqu'un peut faire une vérif et m'indiquer un "ok" que je reprenne mon processus d'optimisation, je lui en serai reconnaissant...
Si quelqu'un peut faire une vérif et m'indiquer un "ok" que je reprenne mon processus d'optimisation, je lui en serai reconnaissant...
Re: Turbo nombres premiers
Jusqu'à 31457280, il y a bien 1942384 nombres premiers...
J'aurais dû enregistrer l'adresse de ce site pour aller leur pourrir la tête...
J'aurais dû enregistrer l'adresse de ce site pour aller leur pourrir la tête...
Re: Turbo nombres premiers
Bon les gars, question simple : est-ce jusqu'à 125829120, on a 7154632 nombres premiers ?
Re: Turbo nombres premiers
Bon... C'est pas grave, admettons que jusqu'à 4 026 531 840, il y ait 191 161 159 nombres premiers, quelqu'un peut-il me dire combien de temps mon algo met sur sa bécane? (moi, j'ai 48 secondes, un peu long...)
Re: Turbo nombres premiers
39167 ms le plus long a été de comprendre comment on change le nombre de valeur testées
Re: Turbo nombres premiers
ahm...mzut ! Je vais un ajouter un petit commentaire !
En tout cas, merci pour le retour case !
En tout cas, merci pour le retour case !
Re: Turbo nombres premiers
Bonjour Ollivier
voici mes résultats sur PB64bits et #p2=30 et 32
voici mes résultats sur PB64bits et #p2=30 et 32
A+Avec PB64bits
49112 ms avec #P2=30
191161156 nbs 1ers NB testés= 4026531840
223593 ms avec #P2=32
717315985 nbs 1ers NB testés= 16106127360
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Re: Turbo nombres premiers
J'ai juste voulu tester en retraduisant en pureBasic la partie ASM, et j'ai été surpris par un phénomène qui me semble étrange : le coeur x64 est lent !! Comparé à tout le système de transfert autour, en tout cas...
Re: Turbo nombres premiers
voici une petite optimisation , en asm , la commande DIV calcul aussi le modulo
RAX = division
RDX = modulo
version avec division + modulo en PB
179446 ms
717315985 nbs 1ers
version avec division en asm
103060 ms
717315985 nbs 1ers
RAX = division
RDX = modulo
version avec division + modulo en PB
179446 ms
717315985 nbs 1ers
version avec division en asm
103060 ms
717315985 nbs 1ers
Code : Tout sélectionner
#P2 = 32 ; on passe de 2^24 à 2^25 pour garder notre durée...
#sMax = 1 << (#P2 - 3) - 1
Macro sGet(K0, M0)
((s(K0) >> M0) & 1)
EndMacro
Macro sSet(K0, M0)
s(K0) | (1 << M0)
EndMacro
Define.I i, modu ; <--- les minuscules sont importantes en ASM
Define.I sqrMax = Sqr((#sMax + 1) * 30)
Dim s.a(#sMax) ; le crible...
s(0) = 1 ; réglage du 1 comme composite...
Dim M.I(7) ; ce tableau ne sera plus nécessaire...
M(0) = 1 ; cette liste non plus...
M(1) = 7
M(2) = 11
M(3) = 13
M(4) = 17
M(5) = 19
M(6) = 23
M(7) = 29
Dim gap.I(7)
gap(0) = 6
gap(1) = 4
gap(2) = 2
gap(3) = 4
gap(4) = 2
gap(5) = 4
gap(6) = 6
gap(7) = 2
K = 0
i0 = 1
t0 = ElapsedMilliseconds()
Repeat
K30 = 30 * K
N = K30 + M(i0)
If sGet(K, i0) = 0
N2 = N * N
If N2 >= (#sMax + 1) * 30
Break
EndIf
i1 = i0
Repeat
;K_30 = N2 / 30
;modu = N2 % 30
!xor rdx,rdx
!mov rax,[v_N2]
!mov rcx,30
!div rcx
!mov [v_K_30],rax
! mov rcx,rdx; [v_modu]
! mov rax, $1C0181500C804000 ; <--- la liste est compactée ici
! shl rcx, 1
! shr rax, cl
! and rax, 7
! mov [v_i], rax
sSet(K_30, I)
N2 + N * gap(i1)
i1 + 1
i1 & 7
Until N2 >= (#sMax + 1) * 30
EndIf
i0 + 1
If i0 > 7
i0 = 0
K + 1
EndIf
Until N > sqrMax
t1 = ElapsedMilliseconds()
Delay(1)
For I = 0 To #sMax
For J = 0 To 7
If s(I) >> J & 1 = 0
P + 1
EndIf
Next
Next
; On affiche quantités et durée de notre algo
MessageRequester(Str((#sMax + 1) * 30) + " nb testés", Str(t1 - t0) + " ms" + Chr(10) + Str(P) + " nbs 1ers")
Re: Turbo nombres premiers
@Papipp
salut Papipp,
merci pour ces deux retours, ça semble trop lent, à ce stade, pour rester au modulo p-fact(5)... Je vais tenter plus loin, étant donné que tu avais trouvé une formulation générale qui va plus loin. Et puis j'avais trouvé, il y a quelques années des modulos plus grands, mais manuellement, donc, le chemin existe. Car le p-fact(5) même compacté dans un seul registre dans le cpu, met du temps pour être extrait à chaque nombre...
Il y a aussi un autre chemin, mais celui-là est bien "serré" : cribler en fonction de ce qui est testé : actuellement, on teste et crible indépendamment, soit en "brut" (E+N) soit en modulo (E+M(i) ). Il reste ce chemin délicat où l'on crible en fonction de ce qui est trouvé. C'est un chemin difficile, car il faut mémoriser plusieurs critère par nombre premier (2 à 3) : le nombre premier, son départ N, son départ N*N, et son stade N*N+x qui dépend de ce que l'on trouve après N. Et cette méthode rend impossible le threading...
@manababel
J'avais pourtant testé cette division, et elle ne me faisait pas gagner grand chose ! J'ai donc mal testé. Je te remercie pour cette optimisation que tu risques de revoir systématiquement, à moins de réussir à supprimer la division (ça coûte en mémoire, a priori, dans ce cas).
salut Papipp,
merci pour ces deux retours, ça semble trop lent, à ce stade, pour rester au modulo p-fact(5)... Je vais tenter plus loin, étant donné que tu avais trouvé une formulation générale qui va plus loin. Et puis j'avais trouvé, il y a quelques années des modulos plus grands, mais manuellement, donc, le chemin existe. Car le p-fact(5) même compacté dans un seul registre dans le cpu, met du temps pour être extrait à chaque nombre...
Il y a aussi un autre chemin, mais celui-là est bien "serré" : cribler en fonction de ce qui est testé : actuellement, on teste et crible indépendamment, soit en "brut" (E+N) soit en modulo (E+M(i) ). Il reste ce chemin délicat où l'on crible en fonction de ce qui est trouvé. C'est un chemin difficile, car il faut mémoriser plusieurs critère par nombre premier (2 à 3) : le nombre premier, son départ N, son départ N*N, et son stade N*N+x qui dépend de ce que l'on trouve après N. Et cette méthode rend impossible le threading...
@manababel
J'avais pourtant testé cette division, et elle ne me faisait pas gagner grand chose ! J'ai donc mal testé. Je te remercie pour cette optimisation que tu risques de revoir systématiquement, à moins de réussir à supprimer la division (ça coûte en mémoire, a priori, dans ce cas).
Re: Turbo nombres premiers
Bon jour à tous
Y-a-t-il une limite au crible d’Ératosthène ?
Théoriquement non. Mais toutes nos machines sont limitées en mémoire ainsi avec 8 Mo de mémoire centrale il est difficile de dépasser un nombre de 2ˆ32=4 294 967 296 car 2ˆ33=8 589 934 592 > 8Go
Avec une petite modif pour aller à la limite des 2ˆ35 Le prg d’Ollivier peut traiter 8 fois plus de nb que les autres prg de ce forum avec 8 Go de mémoire. Normalement on peut attendre 8 fois ou 2ˆ3 plus de nb avec une mémoire de 8GO
Je rappelle qu’entre 0 et 2ˆ32 il y a autant de nombres qu’entre 2ˆ32 et 2ˆ33 ainsi qu'entre 0 à 2ˆ33 et 2ˆ33 à 2ˆ34 etc...
Voici le prg d’ollivier avec correction de manababel modifié pour atteindre 2ˆ35 avec 8Go de mémoire
Je me pose et vous pose cette question. Le crible d’Ératosthène peut-il atteindre des nb premiers au de-là de 2ˆ50 voire jusqu’à 2ˆ64 -1 comme celui que j’avais réalisé et qui n' utilise pas le crible d’Ératosthène ?
A+
Y-a-t-il une limite au crible d’Ératosthène ?
Théoriquement non. Mais toutes nos machines sont limitées en mémoire ainsi avec 8 Mo de mémoire centrale il est difficile de dépasser un nombre de 2ˆ32=4 294 967 296 car 2ˆ33=8 589 934 592 > 8Go
Avec une petite modif pour aller à la limite des 2ˆ35 Le prg d’Ollivier peut traiter 8 fois plus de nb que les autres prg de ce forum avec 8 Go de mémoire. Normalement on peut attendre 8 fois ou 2ˆ3 plus de nb avec une mémoire de 8GO
Je rappelle qu’entre 0 et 2ˆ32 il y a autant de nombres qu’entre 2ˆ32 et 2ˆ33 ainsi qu'entre 0 à 2ˆ33 et 2ˆ33 à 2ˆ34 etc...
Voici le prg d’ollivier avec correction de manababel modifié pour atteindre 2ˆ35 avec 8Go de mémoire
Code : Tout sélectionner
#P2 = 33 ; on passe de 2^24 à 2^25 pour garder notre durée...
sMax.q = 1 << (#P2 - 3) - 1
Macro sGet(K0, M0)
((s(K0) >> M0) & 1)
EndMacro
Macro sSet(K0, M0)
s(K0) | (1 << M0)
EndMacro
Define.I i, modu ; <--- les minuscules sont importantes en ASM
Define.I sqrMax = Sqr((sMax + 1) * 30)
Dim s.a(sMax) ; le crible...
s(0) = 1 ; réglage du 1 comme composite...
Dim M.I(7) ; ce tableau ne sera plus nécessaire...
M(0) = 1 ; cette liste non plus...
M(1) = 7
M(2) = 11
M(3) = 13
M(4) = 17
M(5) = 19
M(6) = 23
M(7) = 29
Dim gap.I(7)
gap(0) = 6
gap(1) = 4
gap(2) = 2
gap(3) = 4
gap(4) = 2
gap(5) = 4
gap(6) = 6
gap(7) = 2
K = 0
i0 = 1
t0 = ElapsedMilliseconds()
Repeat
K30 = 30 * K
N.q = K30 + M(i0)
If sGet(K, i0) = 0
N2.q = N * N
If N2 >= (sMax + 1) * 30
Break
EndIf
i1 = i0
Repeat
;K_30 = N2 / 30
;modu = N2 % 30
!xor rdx,rdx
!mov rax,[v_N2]
!mov rcx,30
!div rcx
!mov [v_K_30],rax
! mov rcx,rdx; [v_modu]
! mov rax, $1C0181500C804000 ; <--- la liste est compactée ici
! shl rcx, 1
! shr rax, cl
! and rax, 7
! mov [v_i], rax
sSet(K_30, I)
N2 + N * gap(i1)
i1 + 1
i1 & 7
Until N2 >= (sMax + 1) * 30
EndIf
i0 + 1
If i0 > 7
i0 = 0
K + 1
EndIf
Until N > sqrMax
t1 = ElapsedMilliseconds()
Delay(1)
For I = 0 To sMax
For J = 0 To 7
If s(I) >> J & 1 = 0
P + 1
EndIf
Next
Next
OpenConsole()
PrintN( Str(t1 - t0) + " ms avec #P2="+Str(#p2)+" sMax="+Str(sMax)+ Chr(10) + Str(P) + " nbs 1ers NB testés= "+Str((sMax+1) * 30))
PrintN("c'est fini")
Input()
CloseConsole()
Delay(500)
; et on affiche quantité et durée de notre algo dont on peut apparemment assortir de la palme du boulet d'or, tellement je n'ai méga rien optimisé... Technologiquement...
MessageRequester(Str((sMax + 1) / 8 * 30) + " nb testés", Str(t1 - t0) + " ms" + Chr(10) + Str(P) + " nbs 1ers sMax= "+Str(sMax* 30))
; On affiche quantités et durée de notre algo
; MessageRequester(Str((sMax + 1) * 30) + " nb testés", Str(t1 - t0) + " ms" + Chr(10) + Str(P) + " nbs 1ers")
A+
Dernière modification par PAPIPP le mer. 21/juil./2021 15:39, modifié 1 fois.
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Re: Turbo nombres premiers
Non. Même, en étendant de la p-factorielle(5) à la p-factorielle(23), on a des pages de 5 méga représentant chacune 100 millions de nombres, et avec par exemple 4 teraoctets de stockage, on peut stocker un total de 2^48 nombres et leurs états premiers ou pas.
2^48 c'est environ 128 mille milliards.
Donc, même mathématiquement, 2^50 c'est 4 fois trop pour 4 teraoctets.
Pour une fin d'application mathématique, on peut avoir une précision absolue dans les calculs rapides jusqu'à 9 chiffres, sans trop saturer la mémoire vive (pages de 5 méga).
2^48 c'est environ 128 mille milliards.
Donc, même mathématiquement, 2^50 c'est 4 fois trop pour 4 teraoctets.
Pour une fin d'application mathématique, on peut avoir une précision absolue dans les calculs rapides jusqu'à 9 chiffres, sans trop saturer la mémoire vive (pages de 5 méga).
Re: Turbo nombres premiers
Un grand merci à ArS qui a ouvert un espace de stockage d'images.Ici, une passiflore et les nombres premiers 3 et 5.