Turbo nombres premiers

Programmation d'applications complexes
Avatar de l’utilisateur
DjPoke
Messages : 121
Inscription : mar. 02/nov./2010 13:53
Localisation : Corte, Corse, France
Contact :

Turbo nombres premiers

Message par DjPoke »

Bonsoir,

Je viens de terminer un programme de calcul (très ?) rapide de nombres premiers, basé sur mes propres recherches.
Je voudrais savoir si quelqu'un pourrait le tester, pour y trouver une éventuelle faille, mais aussi pour savoir s'il existe des algorithmes aussi rapides.

Merci d'avance.

Voici le code :

Code : Tout sélectionner

OpenConsole()
Repeat
PrintN("Entrez un nombre a verifier :")
a$=Input()
nb.q=Val(a$)
Premier=1
tt.f=ElapsedMilliseconds()
i.q=2
j.q=3
While (j.q*j.q)<=nb.q
  j.q=j.q+1  
Wend
While i.q<j.q
  If (nb.q % i.q)=0
    Premier=0
    j.q=nb.q/i.q
    PrintN(Str(i.q)+" * "+Str(j.q))
  EndIf
  i.q=i.q+1
Wend
tt.f=(ElapsedMilliseconds()-tt.f)/1000.000
If Premier=1
  PrintN("Ce nombre est PREMIER !")
Else
  PrintN("Ce nombre n'est PAS PREMIER !")
EndIf
PrintN("Temps de verification : "+StrF(tt.f))
PrintN("")
PrintN("Voulez vous verifier un autre nombre ? (o/n)")
a$=Input()
If LCase(a$)<>"o"
  CloseConsole()
  End
EndIf
PrintN("")
ForEver
Avatar de l’utilisateur
Fig
Messages : 1176
Inscription : jeu. 14/oct./2004 19:48

Re: Turbo nombres premiers

Message par Fig »

Déja quand le nombre se finit par 0-5 ou un chiffre pair, il ne peut pas être premier... Or ton programme se lance quand même dans des calculs interminables ;)
Tu peux aussi virer tout les nombre qui ne satisfont pas au petit théorème de Fermat, tu es sûr qu'ils ne sont pas premiers.

Sinon, pourquoi tu ne fais pas une racine carré arrondie au dessus pour ton premier while/wend ?

Voila, sinon c'ets vrai que c'est déja assez rapide. :P (punaise on a plus de amileys, il se passe quoi là ??)
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 6.00LTS - 64 bits
zaphod
Messages : 135
Inscription : dim. 07/déc./2008 9:32

Re: Turbo nombres premiers

Message par zaphod »

...
Dernière modification par zaphod le dim. 27/mai/2012 7:38, modifié 1 fois.
Avatar de l’utilisateur
graph100
Messages : 1318
Inscription : sam. 21/mai/2005 17:50

Re: Turbo nombres premiers

Message par graph100 »

attention la =)

Va pas dire que PB est lent !!
quand je compile 3 - 4 fois, je tombe entre 0.67 sec et 0.60 sec

mais j'ai modifié le code : tu utilises des type trop grand ! ça ralenti le truc alors que c'est pour stocker des booléens :)

Code : Tout sélectionner

; algo nat the great pour blitzmax
; port en pb by zaphod - 23/05/2011
; en blitzmax = 0.838 sec
; en pb = 1.42 sec
; pentium 4 - 3 Ghz
; 
; modifier par graph100
; avec la modif : 0.67 sec
; core2duo 2.50Ghz
; 
; >>>> Compiler sans le debuger
;
Define num.i = 15485864

num + 1

Define sqrnum.i = Sqr(num) + 1

Dim PrimeFlags.b(num)
Dim Primes.i(num)
Define tim.i,count.i
Define mill.i = ElapsedMilliseconds()


For x = 2 To sqrnum
	If primeflags(x) = #False
		Primes(count) = x
		count + 1     
		
		tim = x
		Repeat
			tim + x
			primeflags(tim) = #True
		Until x + tim >= num
	EndIf
Next


For y = sqrnum To num - 1
	If primeflags(y) = #False
		Primes(count) = y
		
		count + 1      
	EndIf
Next
mill = ElapsedMilliseconds()-mill



MessageRequester("", StrF(mill / 1000.0) + " seconds " + Str(count) + " primes found!")
_________________________________________________
Mon site : CeriseCode (Attention Chantier perpétuel ;))
Avatar de l’utilisateur
DjPoke
Messages : 121
Inscription : mar. 02/nov./2010 13:53
Localisation : Corte, Corse, France
Contact :

Re: Turbo nombres premiers

Message par DjPoke »

Merci pour vos réponses.
En tout cas, cela m'a fait réaliser à quel point PB est plus rapide que les autres. :)
Le Soldat Inconnu
Messages : 4312
Inscription : mer. 28/janv./2004 20:58
Localisation : Clermont ferrand OU Olsztyn
Contact :

Re: Turbo nombres premiers

Message par Le Soldat Inconnu »

De cette manière, c'est encore plus rapide

Et ça corrige un bug sur la dernière valeur qui n'était pas un nombre premier dans le précédent algo, essai en visualisant les valeurs avec Num = 2000 et tu verra que 2000 est considéré comme nombre premier ...

0.326s chez moi sur un I5 2.67 MHz, vive PB.
0.5s avec ton code

Code : Tout sélectionner

; algo nat the great pour blitzmax
; port en pb by zaphod - 23/05/2011
; en blitzmax = 0.838 sec
; en pb = 1.42 sec
; pentium 4 - 3 Ghz
;
; >>>> Compiler sans le debuger
;
Define num.i = 15485864
Define sqrnum.i = Sqr(num)+1
Dim PrimeFlags.b(num)
Dim Primes.i(num)
Define tim.i,count.i = 2
Define mill.i = ElapsedMilliseconds()
;
For x = 3 To sqrnum Step 2
		If PrimeFlags(x) = #False 
				tim = x + x
				Repeat
						PrimeFlags(tim) = #True
						tim + x
				Until tim >= num
		EndIf
Next 
;Local count:Int
Primes(1) = 2
For x = 3 To num Step 2
		If PrimeFlags(x) = #False 
				Primes(count) = x
				count+1   
				Debug x
		EndIf
Next
mill = ElapsedMilliseconds()-mill
;
MessageRequester("",StrF(mill/1000.0) +" seconds "+ Str(count)+" primes found!")
Je ne suis pas à moitié Polonais mais ma moitié est polonaise ... Vous avez suivi ?

[Intel quad core Q9400 2.66mhz, ATI 4870, 4Go Ram, XP (x86) / 7 (x64)]
Avatar de l’utilisateur
graph100
Messages : 1318
Inscription : sam. 21/mai/2005 17:50

Re: Turbo nombres premiers

Message par graph100 »

en fait j'avais oublié de compter 2 dans l'algo :oops:
sinon le dernier nb premier était bon dans ma version ;)
et sur mon pc, il n'y a pas de différence nette entre ton algo (@lsi) et le mien, faudrait que je teste avec un plus grand nombre.
Mais effectivement ça va plus vite !

teste avec la modif suivante ^^ :

Code : Tout sélectionner

; algo nat the great pour blitzmax
; port en pb by zaphod - 23/05/2011
; en blitzmax = 0.838 sec
; en pb = 1.42 sec
; pentium 4 - 3 Ghz
;
; >>>> Compiler sans le debuger
;
Define num.i = 15485864
Define sqrnum.i = Sqr(num)+1
Dim PrimeFlags.b(num)
Dim Primes.i(num)
Define tim.i,count.i = 2
Define mill.i = ElapsedMilliseconds()
;
For x = 3 To sqrnum Step 2
	If PrimeFlags(x) = #False
		Primes(count) = x
		count+1   
		
		tim = x + x
		Repeat
			PrimeFlags(tim) = #True
			tim + x
		Until tim >= num
	EndIf
Next
;Local count:Int

Primes(1) = 2
For y = x To num Step 2
	If PrimeFlags(y) = #False
		Primes(count) = y
		count+1   
	EndIf
Next
mill = ElapsedMilliseconds()-mill
;
MessageRequester("",StrF(mill/1000.0) +" seconds "+ Str(count)+" primes found!")
_________________________________________________
Mon site : CeriseCode (Attention Chantier perpétuel ;))
Le Soldat Inconnu
Messages : 4312
Inscription : mer. 28/janv./2004 20:58
Localisation : Clermont ferrand OU Olsztyn
Contact :

Re: Turbo nombres premiers

Message par Le Soldat Inconnu »

ça devrait être plus rapide mais je ne vois aucune différence. j'ai testé en mettant Num = 200000000
Je ne suis pas à moitié Polonais mais ma moitié est polonaise ... Vous avez suivi ?

[Intel quad core Q9400 2.66mhz, ATI 4870, 4Go Ram, XP (x86) / 7 (x64)]
Avatar de l’utilisateur
graph100
Messages : 1318
Inscription : sam. 21/mai/2005 17:50

Re: Turbo nombres premiers

Message par graph100 »

bah, le gain doit être négligeable ! Pense-tu qu'on peut faire plus rapide en assembleur ??

>< je test l'extension de erix14, c'est juste énorme ><

http://www.purebasic.fr/french/viewtopi ... 8&start=75
_________________________________________________
Mon site : CeriseCode (Attention Chantier perpétuel ;))
Starwolf20
Messages : 10
Inscription : mar. 01/sept./2009 18:39

Re: Turbo nombres premiers

Message par Starwolf20 »

Salut !!
zaphod
Messages : 135
Inscription : dim. 07/déc./2008 9:32

Re: Turbo nombres premiers

Message par zaphod »

...
Dernière modification par zaphod le dim. 27/mai/2012 7:38, modifié 1 fois.
Avatar de l’utilisateur
graph100
Messages : 1318
Inscription : sam. 21/mai/2005 17:50

Re: Turbo nombres premiers

Message par graph100 »

Ça dépend peut être des différents processeurs qui ne sont pas gérer pareil par les langages ?
Faudrait avoir le truc en blitzmax pour pouvoir comparer sur différents pc
_________________________________________________
Mon site : CeriseCode (Attention Chantier perpétuel ;))
Starwolf20
Messages : 10
Inscription : mar. 01/sept./2009 18:39

Re: Turbo nombres premiers

Message par Starwolf20 »

L'algo de Nat the great est tres elegant, compact et efficace.

A titre d'information et puisque on a parlé d'assembleur, j'ai tenté de decortiquer le code generé par PB.
Sans être un UBER specialiste, je l'ai trouvé tres bon.
Atitre d'exemple, voici ce que ca donne en optimisant une partie du code.
Nb : Activez l'assembleur en ligne dans les options du compilateur.

Code : Tout sélectionner

; algo nat the great pour blitzmax
; port en pb by zaphod - 23/05/2011
; en blitzmax = 0.838 sec
; en pb = 1.42 sec
; pentium 4 - 3 Ghz
;
; >>>> Compiler sans le debuger
;
Define num.i = 15485864
Define sqrnum.i = Sqr(num)+1
Dim PrimeFlags.b(num)
Dim Primes.i(num)
Define tim.i,count.i = 2
Define mill.i = ElapsedMilliseconds()
;
For x = 3 To sqrnum Step 2
		If PrimeFlags(x) = #False
				Primes(count) = x
				count+1   
				
				tim = x + x
;-------------------------------------- Partie du code remplacé en assembleur				
;;;				Repeat;
;;;						PrimeFlags(tim) = #True
;;;						tim + x
;;;					Until tim >= num
									
       	; Repeat
          	MOV	 ebx,dword [v_tim]
          	MOV	 ebp,dword [a_PrimeFlags]
          Repeat5:
        ; PrimeFlags(tim) = #True
          ;MOV	 ebx,dword [v_tim]        ; deplacé en dehors de la boucle
          ;MOV	 ebp,dword [a_PrimeFlags] ; deplacé en dehors de la boucle
          	MOV	 byte [ebp+ebx],1
        ; tim + x
          ;MOV	 ebx,dword [v_tim]
          	ADD	 ebx,dword [v_x]
          ;MOV	 dword [v_tim],ebx        ; deplacé en dehors de la boucle
        ; Until tim >= num
          ;MOV	 ebx,dword [v_tim]         
          	CMP	 ebx,dword [v_num]
          	JL	 l_repeat5
        ;_Until5:
        MOV	 dword [v_tim],ebx
;-------------------------------------- 	
        
		EndIf
Next
;Local count:Int

Primes(1) = 2
For y = x To num Step 2
		If PrimeFlags(y) = #False
				Primes(count) = y
				count+1   
		EndIf
Next
mill = ElapsedMilliseconds()-mill
;
MessageRequester("",StrF(mill/1000.0) +" seconds "+ Str(count)+" primes found!")
Avatar de l’utilisateur
graph100
Messages : 1318
Inscription : sam. 21/mai/2005 17:50

Re: Turbo nombres premiers

Message par graph100 »

bah 0.5 sec pour moi ;)

ça va plus vite effectivement, chez LSI, ça doit dépoter vu qu'il faisait 0.3 sec avant
_________________________________________________
Mon site : CeriseCode (Attention Chantier perpétuel ;))
Le Soldat Inconnu
Messages : 4312
Inscription : mer. 28/janv./2004 20:58
Localisation : Clermont ferrand OU Olsztyn
Contact :

Re: Turbo nombres premiers

Message par Le Soldat Inconnu »

entre 0.280 / 0.296 :mrgreen:
Je ne suis pas à moitié Polonais mais ma moitié est polonaise ... Vous avez suivi ?

[Intel quad core Q9400 2.66mhz, ATI 4870, 4Go Ram, XP (x86) / 7 (x64)]
Répondre