Turbo nombres premiers

[Ollivier]

Vérif jusqu'à 983040 : 77276+3 nbs 1ers... Ok...

[Ollivier]

Jusqu'à 1966080, on a 146602+3 nbs 1ers... Algo toujours ok...

[Ollivier]

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...

[Ollivier]

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...

[Ollivier]

Bon les gars, question simple : est-ce jusqu'à 125829120, on a 7154632 nombres premiers ?

[Ollivier]

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...)

[case]

39167 ms le plus long a été de comprendre comment on change le nombre de valeur testées

[Ollivier]

ahm...mzut ! Je vais un ajouter un petit commentaire !
En tout cas, merci pour le retour case !

[PAPIPP]

Bonjour Ollivier

voici mes résultats sur PB64bits et #p2=30 et 32

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

A+

[Ollivier]

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...

[manababel]

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

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")

[Ollivier]

@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).

[PAPIPP]

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

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")

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+

[Ollivier]

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).

[Ollivier]

Un grand merci à ArS qui a ouvert un espace de stockage d'images.Ici, une passiflore et les nombres premiers 3 et 5.