PureBasic

Forums PureBasic
Nous sommes le Dim 25/Oct/2020 3:55

Heures au format UTC + 1 heure




Poster un nouveau sujet Répondre au sujet  [ 28 messages ]  Aller à la page Précédente  1, 2
Auteur Message
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Ven 27/Mai/2011 23:46 
Hors ligne
Avatar de l’utilisateur

Inscription: Sam 21/Mai/2005 17:50
Messages: 1318
bon je crois que j'ai compris la différence entre mon proc et les I5 :mrgreen:
Raah, je suis furax, j'ai acheté mon pc en septembre 2009, et il se fait déjà larguer :|

_________________
_________________________________________________
Mon site : CeriseCode (Attention Chantier perpétuel ;))


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Sam 28/Mai/2011 11:35 
Hors ligne
Avatar de l’utilisateur

Inscription: Ven 11/Fév/2005 17:34
Messages: 4233
Localisation: Arras, France
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 :/


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Sam 28/Mai/2011 18:16 
Hors ligne
Avatar de l’utilisateur

Inscription: Sam 24/Jan/2004 14:54
Messages: 3731
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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Sam 28/Mai/2011 23:19 
Hors ligne
Avatar de l’utilisateur

Inscription: Sam 21/Mai/2005 17:50
Messages: 1318
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

_________________
_________________________________________________
Mon site : CeriseCode (Attention Chantier perpétuel ;))


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Dim 29/Mai/2011 17:38 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 27/Jan/2005 19:07
Messages: 2194
ç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 :)

_________________
Est beau ce qui plaît sans concept :)
Speedy Galerie


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Lun 30/Mai/2011 10:34 
Hors ligne
Avatar de l’utilisateur

Inscription: Ven 11/Fév/2005 17:34
Messages: 4233
Localisation: Arras, France
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 :mrgreen:
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 :)


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Mar 15/Sep/2020 6:18 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 02/Nov/2010 13:53
Messages: 122
Localisation: Corte
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:
;
; 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

_________________
Mes travaux informatiques (et autres) gratuits : https://retro-bruno.fr/
"Mon moteur, ce sont les gens qui me motivent"


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Sam 19/Sep/2020 14:03 
Hors ligne
Avatar de l’utilisateur

Inscription: Dim 10/Mar/2013 22:22
Messages: 168
Localisation: France
DjPoke a écrit:
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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Sam 19/Sep/2020 14:05 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 02/Nov/2010 13:53
Messages: 122
Localisation: Corte
Ah, ok...

_________________
Mes travaux informatiques (et autres) gratuits : https://retro-bruno.fr/
"Mon moteur, ce sont les gens qui me motivent"


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Sam 19/Sep/2020 14:14 
Hors ligne
Avatar de l’utilisateur

Inscription: Dim 10/Mar/2013 22:22
Messages: 168
Localisation: France
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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Sam 19/Sep/2020 14:58 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 02/Nov/2010 13:53
Messages: 122
Localisation: Corte
Naheulf a écrit:
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.

_________________
Mes travaux informatiques (et autres) gratuits : https://retro-bruno.fr/
"Mon moteur, ce sont les gens qui me motivent"


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Dim 20/Sep/2020 16:18 
Hors ligne

Inscription: Jeu 14/Mai/2020 7:40
Messages: 39
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/histoire-des-maths/notions-et-theoremes/186-crible-d-eratosthene#:~:text=La%20fa%C3%A7on%20la%20plus%20simple,d'Eratosth%C3%A8ne%20(IIIe%20av.&text=%C3%89RATOSTH%C3%88NE%20de%20Cyr%C3%A8ne%20est%20un,premier%20mesur%C3%A9%20le%20m%C3%A9ridien%20terrestre.

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

Code:
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


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Ven 25/Sep/2020 11:49 
Hors ligne

Inscription: Jeu 14/Mai/2020 7:40
Messages: 39
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:
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:
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:
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:
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)


Haut
 Profil  
Répondre en citant le message  
Afficher les messages postés depuis:  Trier par  
Poster un nouveau sujet Répondre au sujet  [ 28 messages ]  Aller à la page Précédente  1, 2

Heures au format UTC + 1 heure


Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 3 invités


Vous ne pouvez pas poster de nouveaux sujets
Vous ne pouvez pas répondre aux sujets
Vous ne pouvez pas éditer vos messages
Vous ne pouvez pas supprimer vos messages

Rechercher:
Aller à:  
cron

 


Powered by phpBB © 2008 phpBB Group | Traduction par: phpBB-fr.com
subSilver+ theme by Canver Software, sponsor Sanal Modifiye