PureBasic

Forums PureBasic
Nous sommes le Sam 24/Oct/2020 3:58

Heures au format UTC + 1 heure




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

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

_________________
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é: Lun 23/Mai/2011 8:21 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1138
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 : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Lun 23/Mai/2011 13:43 
Hors ligne

Inscription: Dim 07/Déc/2008 9:32
Messages: 135
...


Dernière édition par zaphod le Dim 27/Mai/2012 7:38, édité 1 fois.

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

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


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

Inscription: Mar 02/Nov/2010 13:53
Messages: 122
Localisation: Corte
Merci pour vos réponses.
En tout cas, cela m'a fait réaliser à quel point PB est plus rapide que les autres. :)

_________________
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é: Lun 23/Mai/2011 19:14 
Hors ligne
Avatar de l’utilisateur

Inscription: Mer 28/Jan/2004 20:58
Messages: 4312
Localisation: Clermont ferrand OU Olsztyn
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:
; 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)]


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

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


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

Inscription: Mer 28/Jan/2004 20:58
Messages: 4312
Localisation: Clermont ferrand OU Olsztyn
ç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)]


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

Inscription: Sam 21/Mai/2005 17:50
Messages: 1318
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/viewtopic.php?f=8&t=9608&start=75

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


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Lun 23/Mai/2011 21:05 
Hors ligne

Inscription: Mar 01/Sep/2009 18:39
Messages: 10
Salut !!


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Jeu 26/Mai/2011 8:12 
Hors ligne

Inscription: Dim 07/Déc/2008 9:32
Messages: 135
...


Dernière édition par zaphod le Dim 27/Mai/2012 7:38, édité 1 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Jeu 26/Mai/2011 14:12 
Hors ligne
Avatar de l’utilisateur

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


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Jeu 26/Mai/2011 23:08 
Hors ligne

Inscription: Mar 01/Sep/2009 18:39
Messages: 10
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:
; 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!")


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Turbo nombres premiers
MessagePosté: Ven 27/Mai/2011 1:25 
Hors ligne
Avatar de l’utilisateur

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


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

Inscription: Mer 28/Jan/2004 20:58
Messages: 4312
Localisation: Clermont ferrand OU Olsztyn
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)]


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 1, 2  Suivante

Heures au format UTC + 1 heure


Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 7 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