Turbo nombres premiers

[graph100]

bon je crois que j'ai compris la différence entre mon proc et les I5
Raah, je suis furax, j'ai acheté mon pc en septembre 2009, et il se fait déjà larguer

[djes]

C'est vrai qu'on pourrait déjà bien optimiser tout ça en utilisant les registres, le SSE, etc. Mais je suis sûr que ç'a déjà été fait, et même que certains algos utilisent les cartes graphiques pour ça, des super calculateurs, des réseaux etc. Autant dire que face à des équipes de chercheurs, on n'a aucune chance :/

[Chris]

Moi j'ai juste une question : A quoi, ça sert cette affaire?

Mais c'est juste une question, hein.
Parce que perso, je suis pas vraiment matheux, les "nombres premiers", je suis comme tout le monde je connais le terme, mais j'ai jamais été vraiment foutu de savoir ce que c'était exactement et ça ne m'a pas empêché de dormir pour autant.

[graph100]

bah les nombres premiers ca sert dans des recherches matheuses, ou dans les fonctions random, ou quand tu veux chercher des nombres premiers ^^

C'est juste des nombres qui n'ont pas de diviseurs à part 1 et eux mêmes

[Frenchy Pilou]

ça sert surtout aux banquiers ou aux services secrets pour les utiliser dans d'inviolables petits codes de confidentialités
pour les cartes bancaires par exemple

[djes]

Oui, sans vouloir refaire wikipedia, les nombres premiers servent beaucoup dans le cryptage ; on se base sur la difficulté à déterminer si un nombre est premier ou pas, qu'on démultiplie en faisant des opérations entre eux. D'où le défi sympa de trouver LE nouvel algo qui tue
Je ne suis pas matheux non plus, mais il y a dans ce domaine beaucoup de choses à découvrir, avec à la clé de belles applications

[DjPoke]

J'espère que l'on ne m'en voudra pas, je déterre ce post, car j'ai trouvé mieux.

Pour 1000001 nombres, je met 118ms avec le code précédent en ASM, et seulement 67ms avec le miens. (qui pourrait aussi être optimisé en ASM...)
(Processeur : i7-4790 3.60 Ghtz, PB x64)

Code : Tout sélectionner

;
; Crible premier, version 1.0
;
; par retro-bruno
; 07/2020
; 

;
; conseils d'usage :
; générez l'executable, et lancez-le à part,
; pas depuis PB, à cause, je pense, du debugger,
; qui le ralentis.
;

OpenConsole()

; vérification et stockage de primalité d'une liste de nombres
;
; ATTENTION : le programme peut devenir gourmand en mémoire.
; si l'on calcule jusqu'au nombre 1 milliard, on utilise presque 1Go !
PrintN("Nombre maximum à calculer :")
n.q = Val(Input())

Dim p.b(n)

PrintN("Afficher la position toutes les secondes ? (o/ )")
ch$ = LCase(Input())


; ==============================================
If ch$ = "o"
  t.q = ElapsedMilliseconds()
EndIf
; ==============================================

; vérification finale
t0.q = ElapsedMilliseconds()

For i.q = 2 To n
  
  y.q = i + i
  
  While y <= n
  
    p(y) = 1
    
    y + i
    
  Wend
  
  ; ==============================================
  If ch$ = "o"
    If ElapsedMilliseconds() - t >= 1000
      PrintN(Str(i))
      t = ElapsedMilliseconds()
    EndIf
  EndIf
  ; ==============================================
  
Next

; affichage du temps total
PrintN("")
PrintN(Str(ElapsedMilliseconds() - t0) + "ms !")

; interrogation d'un nombre
Repeat
  
  PrintN("Nombre :")
  
  a.q = Val(Input())
  
  If a = 0
    Break
  EndIf
  
  If a > 1 And a <= n
    If p(a) = 0
      PrintN("Premier")
    Else
      If Mod(a, 2) = 0
        PrintN("Pair")
      Else
        PrintN("Impair")
      EndIf
    EndIf
  ElseIf a = 1
    PrintN("Impair")
  Else
    PrintN("Erreur")
  EndIf
  
ForEver

CloseConsole()

End

[Naheulf]

J’espère que l’on ne m’en voudra pas, je déterre ce post, car j’ai trouvé mieux.

Si, car ton code est en fait plus lent que les deux précédents.

Les deux codes précédents calculent les nombres premiers jusqu’à 15 485 864 (soit les 1 000 001 premiers nombres premiers). Or pour ton temps tu ne calcules que les nombres premiers jusqu’à 1 000 001 (soit les 78 500 premiers nombres premiers).

Voici les temps que j’obtiens pour les nombres jusqu’à 15 485 864 :
Code de graph100 : 519 ms
Code de starwolf : 235 ms
Code de DjPoke : 4 132 ms

Et pour les nombres jusqu’à 1 000 001 :
Code de graph100 : 25 ms
Code de starwolf : 9 ms
Code de DjPoke : 154 ms

Temps obtenus sur mon ordi équipé d'un Intel Core i3-4005U.

[DjPoke]

Ah, ok...

[Naheulf]

Whaaa ! Rapide la réponse !

En fait, ton code est plus lent car tu n'utilises pas les optimisations qui sont utilisées dans les codes précédents pour la réalisation du crible d'Ératosthène :
- Il n'est pas utile de chercher les multiples de tous les nombres jusqu'au nombre maximal. On peut s'arrêter à la racine carrée de celui-ci.
- il n'est pas utile de chercher les multiples des nombres qui sont déjà des multiples d'autres nombre.

Et peut être d'autres détails d'implémentation que je n'ai pas chercher à analyser.

[DjPoke]

Whaaa ! Rapide la réponse !

En fait, ton code est plus lent car tu n'utilises pas les optimisations qui sont utilisées dans les codes précédents pour la réalisation du crible d'Ératosthène :
- Il n'est pas utile de chercher les multiples de tous les nombres jusqu'au nombre maximal. On peut s'arrêter à la racine carrée de celui-ci.
- il n'est pas utile de chercher les multiples des nombres qui sont déjà des multiples d'autres nombre.

Et peut être d'autres détails d'implémentation que je n'ai pas chercher à analyser.

Je ne fais aucun des deux. Tu devrais chercher à comprendre mon code, et pourquoi pas l'optimiser en ASM.
Tu remarqueras que dans mon code, il n'y a ni divisions, ni modulos, ni multiplications, qui sont les opérations les plus lentes en ASM.
Enfin, je pense qu'un accès plus direct à la mémoire devrait aussi le booster.

[manababel]

Bonjour djPoke

votre code est le même que ceux postés précédemment

voici comment fonctionne votre code :
https://www.math93.com/index.php/histoi ... terrestre.

avec le code ci desous, vous pouvez constater que c'est bien le même code que les précédents

Code : Tout sélectionner

OpenConsole()
n.q = 15485864
Dim p.b(n)

t0.q = ElapsedMilliseconds()

For i.q = 3 To n ;Step 2
  ;If p(i)=0
    y = i + i
    While y <= n
      p(y) = 1
      y + i
    Wend
  ;EndIf
Next

count=0
For x=1 To n Step 2
  If p(x) = 0
      count+1   
   EndIf
 Next
 
 mill = ElapsedMilliseconds()-t0
 
PrintN("")
PrintN(StrF(mill/1000.0) +" seconds "+ Str(count)+" primes found!")

Repeat
ForEver
CloseConsole()

End

[manababel]

j'ai essayé d'optimiser cette algorhime.
le test a ete fait sur un core i9-9750h à 2.6 Ghz 6 coeurs/12 threads

le nombre total à tester et 1548586400
par défaut sur les codes précédents, le nombre total à tester et 15485864

résultats : ( valeurs moyennes )
le code PB : 16sec
le code ASM : 13sec
le code 'threadé' en PB : 9sec
le code 'threadé' en ASM : 8sec

par défaut je n'utile que 10 threads, au-dessus les programmes sont plus lents

pour un gain vraiment significatif, il faudrait utiliser la carte graphique

autre soucie avec c'est algo, il consomme trop de RAM


code PB:

Code : Tout sélectionner

Global num.q = 1548586400
Global sqrnum.q = Sqr(num)+1
Global Dim PrimeFlags.b(num)
Global mill.q = ElapsedMilliseconds()

mill1.q = ElapsedMilliseconds()
For x=3 To sqrnum Step 2
  If PrimeFlags(x)=#False
    tim = x + x
    Repeat 
      PrimeFlags(tim)=#True
      tim = tim + x
    Until tim>= num
  EndIf  
Next
mill1 = ElapsedMilliseconds()-mill1

mill2.q = ElapsedMilliseconds()    
count=0
For x=1 To num Step 2
  If PrimeFlags(x) = 0
      count+1   
   EndIf
Next
mill2 = ElapsedMilliseconds()-mill2

FreeArray(PrimeFlags())
t1$="part 1 : "+StrD(mill1/1000.0)+" seconds"
t2$="part 2 : "+StrD(mill2/1000.0)+" seconds"
t3$="TOTAL : "+StrD((mill1+mill2)/1000.0)+" seconds"
t4$=Str(count)+" trouvé"
t$=t1$ + Chr(13) +t2$ + Chr(13) +t3$ + Chr(13) +t4$ 
MessageRequester("Information",t$,#PB_MessageRequester_Ok)

code ASM:

Code : Tout sélectionner

Define num.q = 1548586400
Define sqrnum.q = Sqr(num)+1
Dim PrimeFlags.b(num)

mill1.q = ElapsedMilliseconds()
!mov r9,[a_PrimeFlags]
!mov rdx,3
!saut2:
  !cmp byte [r9+rdx],0
  !jne saut1
    !mov rbx,rdx
    !add rbx,rbx
    !boucle:
      !mov byte [r9+rbx],1
      !add rbx,rdx
      !cmp rbx,[v_num]
    !jl boucle   
  !saut1:
  !add rdx,2
  !cmp rdx,[v_sqrnum]
!jle saut2
mill1 = ElapsedMilliseconds()-mill1

mill2.q = ElapsedMilliseconds() 
count=0
For x=1 To num Step 2
  If PrimeFlags(x) = 0
      count+1   
   EndIf
Next
mill2 = ElapsedMilliseconds()-mill2

FreeArray(PrimeFlags())
t1$="part 1 : "+StrD(mill1/1000.0)+" seconds"
t2$="part 2 : "+StrD(mill2/1000.0)+" seconds"
t3$="TOTAL : "+StrD((mill1+mill2)/1000.0)+" seconds"
t4$=Str(count)+" trouvé"
t$=t1$ + Chr(13) +t2$ + Chr(13) +t3$ + Chr(13) +t4$ 
MessageRequester("Information",t$,#PB_MessageRequester_Ok)

code 'threadé' PB

Code : Tout sélectionner

Global ndt=10
Global num.q = 1548586400
Global sqrnum.q = Sqr(num)+1
Global Dim PrimeFlags.b(num)
Global Dim Thread(ndt)

Threaded tim
Threaded y
;
Procedure test(y)
  tim = y + y
  Repeat
    PrimeFlags(tim)=#True
    tim = tim + y
  Until tim>= num

EndProcedure
;
Procedure testThread()
  For i=0 To ndt-1
    If IsThread(Thread(i)) = 0
      Thread(i) = 0
      ProcedureReturn i
    EndIf
  Next
  ProcedureReturn - 1
EndProcedure

mill1.q = ElapsedMilliseconds()
For x=3 To sqrnum Step 2
  If PrimeFlags(x)=#False
    Repeat
      var = testThread()
    Until var<>-1
    Thread(var)=CreateThread(@test(),x)
  EndIf  
Next
mill1 = ElapsedMilliseconds()-mill1

Repeat
  ct=0
  For i=0 To ndt-1
    If IsThread(Thread(i)) > 0
      ct=ct+1
    Else
      Thread(i)=0
    EndIf
  Next
Until ct=0 

  
mill2.q = ElapsedMilliseconds()
count=0
For x=1 To num Step 2
  If PrimeFlags(x) = #False
      count+1   
   EndIf
Next
mill2 = ElapsedMilliseconds()-mill2

FreeArray(PrimeFlags())
t1$="part 1 : "+StrD(mill1/1000.0)+" seconds"
t2$="part 2 : "+StrD(mill2/1000.0)+" seconds"
t3$="TOTAL : "+StrD((mill1+mill2)/1000.0)+" seconds"
t4$=Str(count)+" trouvé"
t$=t1$ + Chr(13) +t2$ + Chr(13) +t3$ + Chr(13) +t4$ 
MessageRequester("Information",t$,#PB_MessageRequester_Ok)

code 'threadé' ASM

Code : Tout sélectionner

Global ndt=10
Global num.q = 1548586400
Global sqrnum.q = Sqr(num)+1
Global Dim PrimeFlags.b(num)
Global Dim Thread(ndt)

Procedure test(y) 
  !mov rax,[p.v_y]
  !mov rbx,rax
  !add rbx,rbx
  !mov rcx,[a_PrimeFlags]
  !boucle:
    !mov byte[rcx+rbx],1
    !add rbx,rax
    !cmp rbx,[v_num]
  !jl boucle
EndProcedure
;
Procedure testThread()
  For i=0 To ndt-1
    If IsThread(Thread(i)) = 0
      Thread(i) = 0
      ProcedureReturn i
    EndIf
  Next
  ProcedureReturn - 1
EndProcedure

mill1.q = ElapsedMilliseconds()
For x=3 To sqrnum Step 2
  If PrimeFlags(x)=#False
    Repeat
      var = testThread()
    Until var<>-1
    Thread(var)=CreateThread(@test(),x)
  EndIf  
Next
mill1 = ElapsedMilliseconds()-mill1

Repeat
  ct=0
  For i=0 To ndt-1
    If IsThread(Thread(i)) > 0
      ct=ct+1
    Else
      Thread(i)=0
    EndIf
  Next
  Debug ct
Until ct=0 

  
mill2.q = ElapsedMilliseconds()
count=0
For x=1 To num Step 2
  If PrimeFlags(x) = #False
      count+1   
   EndIf
Next
mill2 = ElapsedMilliseconds()-mill2

FreeArray(PrimeFlags())
t1$="part 1 : "+StrD(mill1/1000.0)+" seconds"
t2$="part 2 : "+StrD(mill2/1000.0)+" seconds"
t3$="TOTAL : "+StrD((mill1+mill2)/1000.0)+" seconds"
t4$=Str(count)+" trouvé"
t$=t1$ + Chr(13) +t2$ + Chr(13) +t3$ + Chr(13) +t4$ 
MessageRequester("Information",t$,#PB_MessageRequester_Ok)

[manababel]

suite au poste d'Olivier
https://www.purebasic.fr/french/viewtop ... =1&t=18494

j'ai reussi a optimiser le code .
il est plus rapide et consomme 2 fois moins de memoire

le plus gros problème avec ce programme vient de la ram
1- il consomme énormément de ram
2- la ram est lente

voici le code qui rand le programme plus rapide . (on ne gère plus les nombres pairs dans la boucle principale)

Code : Tout sélectionner

  !boucle:
    !mov r8,rbx
    !shr r8,1 ; test si le nombre est paire
    !jnc boucle2
      !mov byte[rcx+rbx],1
    !boucle2:
    !add rbx,rax
    !cmp rbx,[v_num]
  !jle boucle

le programme consomme deux fois moins de ram car 50% était utilisé pour stocker les nombres pairs, ce n'est plus le cas

code non threader

Code : Tout sélectionner

Define num.q = 1548586400
Define sqrnum.q = Sqr(num)+1
Dim PrimeFlags.b(num>>1)
 
mill1.q = ElapsedMilliseconds()
  
For i.q=3 To sqrnum Step 2
  
  If PrimeFlags(i>>1) = 0
    
    !mov r9,[a_PrimeFlags]
    !mov rdx,[v_i]
    
    !mov rcx,rdx
    !add rcx,rcx
    !boucle:
      !mov rbx,rcx
      !shr rbx,1
      !jnc xxx ; on ne gere pas les nombres paires
        !mov byte [r9+rbx],1
      !xxx:
      !add rcx,rdx
      !cmp rcx,[v_num]
    !jl boucle   

  EndIf  

  
Next


mill1 = ElapsedMilliseconds()-mill1

mill2.q = ElapsedMilliseconds() 

count=0
For x=0 To (num-1)>>1 Step 1
  If PrimeFlags(x) = 0
    count+1
    ; Debug (x*2)+1 = nombre premier
  EndIf 
Next
mill2 = ElapsedMilliseconds()-mill2

num_ko = (num/2)/1024
num_mo = num_ko/1024
num_go = num_mo/1024
;EnableDebugger
FreeArray(PrimeFlags())
t$="part 1 : "+StrD(mill1/1000.0)+" seconds" + Chr(13)
t$=t$+"part 2 : "+StrD(mill2/1000.0)+" seconds" + Chr(13)
t$=t$+"TOTAL : "+StrD((mill1+mill2)/1000.0)+" seconds" + Chr(13)
t$=t$+Str(count)+" trouvé" + Chr(13)
t$=t$+Str(num_ko) + " Ko" + Chr(13)
t$=t$+Str(num_mo) + " Mo" + Chr(13)
t$=t$+Str(num_Go) + " Go" + Chr(13)


MessageRequester("Information",t$,#PB_MessageRequester_Ok)

code multi-thread

Code : Tout sélectionner

Global num.q = 1548586400
Global sqrnum.q = Sqr(num)+1
Dim PrimeFlags.b(num>>1)

Global ndt=CountCPUs()
Global Dim Thread(ndt)
Global wait

Procedure test(y) 
  wait=1
  !mov rax,[p.v_y]
  !mov rbx,rax
  !add rbx,rbx
  !mov rcx,[a_PrimeFlags]
  !boucle:
    !mov r8,rbx
    !shr r8,1
    !jnc boucle2
      !mov byte[rcx+r8],1
    !boucle2:
    !add rbx,rax
    !cmp rbx,[v_num]
  !jle boucle
EndProcedure
;
Procedure testThread()
  For i=0 To ndt-1
    If IsThread(Thread(i)) = 0
      Thread(i) = 0
      ProcedureReturn i
    EndIf
  Next
  ProcedureReturn - 1
EndProcedure

mill1.q = ElapsedMilliseconds()
For x=3 To sqrnum Step 2
  If PrimeFlags(x>>1)=#False
    Repeat
      var = testThread()
    Until var<>-1
    wait=0
    Thread(var)=CreateThread(@test(),x)
  EndIf  
Next
mill1 = ElapsedMilliseconds()-mill1

Repeat
  ct=0
  For i=0 To ndt-1
    If IsThread(Thread(i)) > 0
      ct=ct+1
    Else
      Thread(i)=0
    EndIf
  Next
Until ct=0 

  
mill2.q = ElapsedMilliseconds()
count=0
For x=0 To (num-1)>>1 Step 1
  If PrimeFlags(x) = #False
    count+1   
    ; Debug (x*2)+1 = nombre premier
   EndIf
Next
mill2 = ElapsedMilliseconds()-mill2

num_ko = (num>>1)/1024
num_mo = num_ko/1024
num_go = num_mo/1024
;EnableDebugger
FreeArray(PrimeFlags())
t$="part 1 : "+StrD(mill1/1000.0)+" seconds" + Chr(13)
t$=t$+"part 2 : "+StrD(mill2/1000.0)+" seconds" + Chr(13)
t$=t$+"TOTAL : "+StrD((mill1+mill2)/1000.0)+" seconds" + Chr(13)
t$=t$+Str(count)+" trouvé" + Chr(13)
t$=t$+Chr(13)
t$=t$+"nombre de thread : " +Str(ndt) + Chr(13)
t$=t$+Chr(13)
t$=t$+Str(num_ko) + " Ko" + Chr(13)
t$=t$+Str(num_mo) + " Mo" + Chr(13)
t$=t$+Str(num_Go) + " Go" + Chr(13)


MessageRequester("Information",t$,#PB_MessageRequester_Ok)

attention à la variable num.q ( num.q = 1548586400 )
Voici les résultats que j'obtiens

ancienne version non threader : 12 sec
ancienne version threader : 8 sec
nouvelle version non threader : 6 sec
nouvelle version threader : 4 sec


en utilisant la commande "BTS", il est possible de gagner de la mémoire et peut être du temps (voire lien cité en début du poste)

[Kwai chang caine]

Encore une fois on joue pas dans la même cour
Tel programmeur, tel PC

part 1 : 21.461 seconds
part 2 : 6.26 seconds
TOTAL : 27.721 seconds
77024275 trouvé

nombre de thread : 2

756145 Ko
738 Mo
0 Go

Merci pour le partage