Turbo nombres premiers
Re: Turbo nombres premiers
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
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 )
Mon site : CeriseCode (Attention Chantier perpétuel )
Re: Turbo nombres premiers
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 :/
Re: Turbo nombres premiers
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.
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.
Re: Turbo nombres premiers
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
C'est juste des nombres qui n'ont pas de diviseurs à part 1 et eux mêmes
_________________________________________________
Mon site : CeriseCode (Attention Chantier perpétuel )
Mon site : CeriseCode (Attention Chantier perpétuel )
-
- Messages : 2194
- Inscription : jeu. 27/janv./2005 19:07
Re: Turbo nombres premiers
ç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
pour les cartes bancaires par exemple
Est beau ce qui plaît sans concept
Speedy Galerie
Speedy Galerie
Re: Turbo nombres premiers
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
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
- Messages : 121
- Inscription : mar. 02/nov./2010 13:53
- Localisation : Corte, Corse, France
- Contact :
Re: Turbo nombres premiers
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)
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
Re: Turbo nombres premiers
Si, car ton code est en fait plus lent que les deux précédents.DjPoke a écrit :J’espère que l’on ne m’en voudra pas, je déterre ce post, car j’ai trouvé mieux.
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
- Messages : 121
- Inscription : mar. 02/nov./2010 13:53
- Localisation : Corte, Corse, France
- Contact :
Re: Turbo nombres premiers
Ah, ok...
Re: Turbo nombres premiers
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.
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
- Messages : 121
- Inscription : mar. 02/nov./2010 13:53
- Localisation : Corte, Corse, France
- Contact :
Re: Turbo nombres premiers
Je ne fais aucun des deux. Tu devrais chercher à comprendre mon code, et pourquoi pas l'optimiser en ASM.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.
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.
Re: Turbo nombres premiers
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
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
Re: Turbo nombres premiers
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 ASM:
code 'threadé' PB
code 'threadé' ASM
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)
Re: Turbo nombres premiers
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)
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 multi-thread
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)
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
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
- Messages : 6962
- Inscription : sam. 23/sept./2006 18:32
- Localisation : Isere
Re: Turbo nombres premiers
Encore une fois on joue pas dans la même cour
Tel programmeur, tel PC
Tel programmeur, tel PC
Merci pour le partagepart 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