AccueilCodesTutorielsForumsEmploiLivresConnexion

  • Visual Basic, VB6, VB.NET, VB 2005, VB CodeS-SourceS
  • RSS CodeS-SourceS
  • CodyxBot, le Bot GTalk & MSN qu'il vous faut !
  • Générez des revenus avec vos codes, scripts et tutoriaux
  • Aide à la navigation du site
begin process at 2009 01 07 22:30:36
Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

RECHERCHE DE NOMBRES PREMIERS


Information sur la source

Catégorie :Maths Classé sous : nombres, premiers, recherche, calculs Niveau : Débutant Date de création : 18/11/2004 Date de mise à jour : 22/11/2005 18:29:00 Vu / téléchargé: 12 634 / 519
Auteur : MadM@tt Site perso
Ecrire un message privé
Ce membre participe au partage de revenus publicitaires
Note :
9,6 / 10 - par 5 personnes
9,60 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Commentaire sur cette source (184)
Ajouter un commentaire et/ou une note

Description

Cliquez pour voir la capture en taille normale
Salut à tous
voilà ce soir j'ai eu une pulsion, j'avais envie de chercher des nombres premiers, peut-etre pour plus tard développer un programme de cryptage RSA, donc je me suis amusé.
C'est un programme qui cherche les nombres premiers en fonction du nombre où il s'est arreté dans l'utilisation précédente, c'est à dire que le dernier nombre analysé est sauvegardé dans un fichier, et tous les nombres premiers trouvés sont sauvegardés aussi dans un autre fichier texte.

En plus que je n'aime pas avoir un pc qui ne bosse pas quand je suis pas la, si y'en a dans le meme cas que moi vous verrez ça soulage lol (un peu comme avec Seti@home)
Bon amusez vous, ça vous servira peut-etre pour programmer un crypteur utilisant les nombres premiers.
a +
MadMatt
 

Conclusion

suivant le nombre ça me sort entre 100 et 1000 nombres par secondes, selon la taille du nombre
 

Fichier Zip

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip

Historique

18 novembre 2004 20:20:55 :
vitesse x20 en cherchant jusqu'a la racine au lieu de la moitié
18 novembre 2004 21:04:16 :
reglage du problème concernant l'enregistrement des nombres premiers : si il y en avait trop a sauvegarder ça plantait -> sauvegarde automatique tout les 1 000 nombres
18 novembre 2004 22:29:36 :
gain de quelques secondes grâce à Vlad2i
22 novembre 2005 18:29:00 :
Ajout des mots clés

Commentaires et avis

signaler à un administrateur
Commentaire de MadM@tt le 18/11/2004 18:14:38

PS : pour l'instant mon max est à 260 987 qui dit mieu ?

pour ceux que ça interesse des scientifiques en ont trouvé à x10^340 chiffres je crois, dans cet ordre de grandeur la

Si vous avez un meilleur algorithme a proposer, allez-y

signaler à un administrateur
Commentaire de spy166 le 18/11/2004 18:26:21

Ca sert à quoi d'avoir des chiffres pareils ?

signaler à un administrateur
Commentaire de MadM@tt le 18/11/2004 18:52:29

Pour crypter c'est essentiel :
quand tu prend 2 nombres premiers p et q (qui je le précise ne sont donc divisibles que par 1 ou par eux-meme) et que tu les multiplie : p*q
le produit p*q peut-etre rendu public et des fichiers peuvent etre codés avec, mais pour décoder il faudra se servir de p et q séparément.
Or l'avantage des nombres premiers multipliés ainsi, c'est que à partir du produit p*q il est extremement difficile de retrouver le p et le q du départ... (ça nécessite énormément d'ordis et de temps).

Donc en gros tu code avec p*q qui est public, et seulement l'utilisateur qui a la vraie clé : p et q séparément, peut décoder le fichier obligatoirement avec les 2 nombres séparés (c'est du à des calculs mathématiques assez compliqués)

euh chu pas un expert, jme suis peut etre trompé quelque part mais dans l'ensemble c'est ça

signaler à un administrateur
Commentaire de spy166 le 18/11/2004 19:35:46

Ah oki même principe que le RSA.

signaler à un administrateur
Commentaire de Pingouin le 18/11/2004 19:59:51

Salut,
Juste une petite amélioration de rien : j'ai vu que tu cherchais les diviseurs jusqu'a nombre /2 en fait on peut démontrer (mais c pas évident) qu'il suffit de s'arrêter a la racine carré du nombre, ca diminue sensiblement le nombre de calculs et améliore donc la vitesse, ce qui n'est pas négligeable dans ce genre de prog.
Sinon fais en quelque chose de bo graphiquement comme ca ca pourra en effet décorer le pc pdt kil ne fait rien...

@+

Pingouin

signaler à un administrateur
Commentaire de MadM@tt le 18/11/2004 20:18:18

Génial ça c'est du commentaire, merci Pingouin je vais regarder ça de plus près, sinon je pensais aussi le mettre en écran de veille avec un petit truc graphique, ça sera plus pratique a utiliser et ça ne demandera aucun effort.
@ +

signaler à un administrateur
Commentaire de MadM@tt le 18/11/2004 20:24:54

oulala la vitesse est multipliée par 20 même plus merci Pingouin, sinon spy166 oui c'est le principe du cryptage RSA
par contre je me demande si quand j'arriverai à des nombres tellement grands qu'ils seront stockés sous la forme .....*10^n
est ce que ça me garde en mémoire tous les chiffres du nombre ou alors ça garde seulement l'expression ....*10^n ? si quelqu'un peut m'apporter une réponse

signaler à un administrateur
Commentaire de spy166 le 18/11/2004 21:52:40

Je viens de chronométrer, chez moi en 1 minute tout rond je trouve jusqu'a 1 501 598.
Pas mal non ?

signaler à un administrateur
Commentaire de vlad2i le 18/11/2004 22:05:00

Oulala hehe c'est une méthode brutale pour trouver ca...

Quelques idées :

Un nombre premier x est forcément tel que x mod 4 = 3 ou x mod 4 = 1 et forcément tel que x mod 6 = 1 ou x mod 6 = 5 ca peut largement augmenter la vitesse de ta recherche (par exemple en fesant une boucle de I à I\6 et en testant la primalité des nombres 6*I+1 et 6*I-1)

Ensuite, éviter les nombres évidemment pairs, alias nombres pairs et multiples de 5 par exemple ...

Si tu veux vraiment un algorithme éfficace, j'ai un document de trois chercheurs indiens qui ont utilisé une intégrale de ramanujan pour étudier la congruence des nombres non premiers - et qui que quand il renvoie q'un nombre est premier c'est avec 100% de certitude (l'inverse n'est pas vrai par contre :))

Parce que pour RSA, la sécurité est faible en dessous de 300 chiffres, produit : 300×300 = 90000 chiffres pour le produit pq :) il faut donc que tu gères les grands chiffres :)

Vlad

signaler à un administrateur
Commentaire de MadM@tt le 18/11/2004 22:14:05

merci pour ces infos vlad2i justement je voulais que cette source soit un point de départ pour réaliser un algorithme de cryptage RSA, en arrivant a bien manipuler les nombres premiers.
Comme tu l'a dit il faudra penser au grands nombres, et pour les techniques que tu m'a donné pour calculer plus vite les nombres premiers merci beaucoup je regarderais ça avec bcp d'attention.

mais par contre je ne comprend pas pourquoi tu veux faire une boucle de I à I/6, c'est pas possible de tester ça ? :
If (x mod 4 = 3 or x mod 4 = 1) and (x mod 6 = 1 or x mod 6 = 5) Then

quand tu parle de 100% de certitude, tu veux dire que l'algorithme (barbare c'est clair) que j'utilise n'est pas très fiable ?

Et enfin oui je vais penser à détecter automatiquement les chiffres pairs.

merci
@ +

signaler à un administrateur
Commentaire de vlad2i le 18/11/2004 22:20:11

Ton interpretation est exacte, mais cependant, tu devrais utiliser plutot

If  ((x mod 4 = 3 or x mod 4 = 1) and (x mod 6 = 1 or x mod 6 = 5)) Then
'La tu teste la primalité - la nombre est peut etre premier
else
'Le nombre n'est pas premier
endif

Car il se peut qu'un nombre ne soit pas premier mais passe le test qd meme, et là tu peux d'office tester (ce qui réduit considérablement les tests qd meme)

"quand tu parle de 100% de certitude, tu veux dire que l'algorithme (barbare c'est clair) que j'utilise n'est pas très fiable ?"

Non, en fait il est fiable, mais lent - je parlait de l'algorithme intégral, enfin peu importe

Vlad

signaler à un administrateur
Commentaire de MadM@tt le 18/11/2004 22:27:26

lol ok pour l'algorithme intégral
j'ai essayer de détecter si c'était un nombre pair ou multiple de 5 avant les calculs plus compliqués mais j'ai constaté aucun gain de temps, si ce n'est de la perte.

Pour ton truc de modulo, ça m'a fait gagné environ 1 sec sur 13 c'est pas mal, j'ai donc environ 12 sec pour 100 000 nombres premiers trouvés

merci vlad
(je met la source à jour)

signaler à un administrateur
Commentaire de Mindiell le 19/11/2004 16:33:06

Pour information, ton programme me donne ca au début :
1
5
7

Je suis au regret de te dire qu'il manque 2 et 3 comme nombres premiers. J'accorde le 1 bien qu'au point de vue mathématiques le 1 n'est pas premier pour des questions de généralisation de lois sur ces nombres...

signaler à un administrateur
Commentaire de vlad2i le 19/11/2004 16:38:04

Effectivement : 2 et 3 manquent a l'appel (c'est du à la méthode par modulo) mais ca ne change rien car il suffit d'ajouter deux nombres :)

Quant à 1 il n'est pas premier :) l'algo est donc sûr au delà de 5 inclus :)

signaler à un administrateur
Commentaire de vlad2i le 19/11/2004 16:46:07

J'ajoutes que pour optimiser d'avantage la vérification de primalité, tu devrais stocker les nombres premiers trouvés dans un tableau (ex: prems() ) qui contient les premiers a partir de 3 inclus et pour tester

Function TestPremier(x)
     If X mod 2 = 0 then PasPremier

     For I = 0 to ubound(prems)
          If prems(I)<int(sqr(x)) then
               If X mod Prems(I) = 0 then
                    PasPremier
                    Exit Function
               Endif
          endif
     next

     Premier
     redim preserve prems(ubound(prems)+1)
     prems(ubound(prems)) = X
End Function

Par exemple :)

Vlad

signaler à un administrateur
Commentaire de Mindiell le 19/11/2004 16:57:52

Oui, autant initialiser ton tableau Prems avec 2 alors ;o)

signaler à un administrateur
Commentaire de Pingouin le 19/11/2004 19:34:23

Hugh !
Ben ecoute ca fait plaisir de servir a quelque chose de temps a autres.
Sinon je vois que ca a pas mal progressé depuis mon dernier passage !! En effet quelques tests préliminaires ne sont pas a négligés surtout pour de grands nombres. Encore quelques secondes de gagnées !
Sinon je vais essayer de voir si je le retrouve mais il serait intéressant d'implémanter le dernier algorithme a ce sujet qui nous vient de deux mathématiciens indiens qui parait il est une preuve mathématik mais pas forcement bcp plus rapide voire plus lent d'apres ce que j'ai entendu dire. si kkun voit de koi je veux parler kil n'hésite pas...
Voila voila,
Bonne continuation j'essaierais de garder un oeil la dessus ca m'interesse.

signaler à un administrateur
Commentaire de MadM@tt le 19/11/2004 21:09:37

Mindiell > oui comme l'a dit Vlad2i c'est du au modulo, j'y ai meme pas pensé, je vais arranger ça et je penserai au 1 aussi merci

Vlad2i > excellente idée, ça évite de rediviser à chaque fois par tous les nombres meme ceux pas premier. Et dans la meme logique, autant essayer de diviser par tous les nombres premiers jusqu'a la racine du nombre à tester, ce qui donne :

Function TestPremier(x)
     If X mod 2 = 0 then PasPremier


     '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
     ' Le changement est ici
     For I = 0 to int(sqr(ubound(prems)))+1
     '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
          If prems(I)<int(sqr(x)) then
               If X mod Prems(I) = 0 then
                    PasPremier
                    Exit Function
               Endif
          endif
     next

     Premier
     redim preserve prems(ubound(prems)+1)
     prems(ubound(prems)) = X
End Function

Pingouin > si j'ai bien fait la relation tu doit parler des meme bonhomme que parlait Vlad2i plus haut, avec l'intégrale de ramanujan, si tu trouve quelque chose ça peut etre pas mal

merci à vous pour vos commentaire, j'essayerai de modifier la source ce soir

@ +

signaler à un administrateur
Commentaire de vlad2i le 19/11/2004 22:47:54

Désolé l'ami hehe ton implémentation (ton changement) ne sert à rien :)

For I = 0 to int(sqr(ubound(prems)))+1 <= inutile et innefficace - tu comprends je crois que prems contient les nombres premiers trouvés (exemple prems(4) = 13 ) et que j'avais déjà pensé a mettre "If prems(I)<int(sqr(x)) then" une ligne en dessous :)

Bien essayé :)

Par contre, Pingouin : la formule de Ramanujan permet de tester la primalité de nombres de plusieurs millions de chiffres (binaires) en quelques secondes :) donc plus lent c'est discutable :)

Vlad

signaler à un administrateur
Commentaire de MadM@tt le 20/11/2004 00:09:11

Oui effectivement je n'avais pas vu le problème sous cet angle. Par contre avec ta technique, il y a quand meme des inconvénients :
à chaque lanvement du prog il faut charger tous les nombres premiers déjà trouvés (par exemple la je le laisse tourner de temps en temps depuis 2 jours et j'en suis à 100 000 000 ce qui me fait un fichier de sauvegarde de 70 Mo et donc va charger ça en mémoire)
et il faut être sur d'avoir non seulement des nombres vraiments premier mais je pense que l'algorithme ici est bon et aussi avoir trouvé TOUS les nombres premiers avant celui que tu cherche, donc on ne peut pas commencer arbitrairement à une valeur, on est obligé de démarrer de 1 lors de la première utilisation...

Enfin ça fait pas mal de problème pour, je pense, un gain de temps pas énorme

signaler à un administrateur
Commentaire de Mindiell le 20/11/2004 02:18:09

MadMatt, tu peux te rendre compte que la plupart des nombres non premiers sont divisibles par les petits nombres premiers. Donc en créant ton tableau Prems en le faisant contenir les 200 premiers nombres premiers tu élimineras par exemple déjà un grand nombre de nombres pas premiers, et ensuite tu appliques ta méthode brutale par exemple :)

signaler à un administrateur
Commentaire de MadM@tt le 20/11/2004 11:49:03

ah oui c'est vrai ça peut se faire, ça devrait pas prendre beaucoup en mémoire...
je vais y regarder merci

signaler à un administrateur
Commentaire de crazyjoke le 20/11/2004 22:23:03

Pour la racine du nombre a tester, l'expliquation est facilement concevable :

Un nombre, si il n'est pas premier possède au moins un couple de multiples comme celui ci

a*b

avec a>b et a <> 0, alors il possède aussi comme multiple le couple :

b*a

Il faut donc s'arrêter à la racine carrée : quand a=b; toutes les recherches après sont vaines :).

signaler à un administrateur
Commentaire de zoslex le 22/11/2004 11:13:23

Pas mal du tout comme source. Je suis intéressé par la suite (version prenant en compte toutes les améliorations)...

Mais si tu cherches la rapidité, un truc qui accélère vachement : ne pas afficher la liste.
Quand ça tourne, mets
Me.Liste.Visible = False
puis quand ça s'arrête, tu reviens à
Me.Liste.Visible = True

Jusqu'à 170 000, je passe de 15s à 3s.

Continue, tu tiens le bon bout.

signaler à un administrateur
Commentaire de sibi12 le 22/11/2004 16:01:50

Arf j'avais plein de suggestion en regardant ton code mais je vois qu'on te les a deja tte donnée (même l'explication pr la racine carré)..
J'ai fait un programme du style il y a quelque temps mais je ne le retrouve plus j'ai du l'effacer lors du gd nettoyage :(...

Sinon pour l'idée du tableau je l'avais implémenter, ça prens pas mal de place en mémoire mais le gain de temps est interressant. Pour repondre à ta question avec les grand nombre, si tu t'ai déjà interesser à la représentation en memoire tu devrai savoir qu'un entier sous VB est codé sur 32 bit et est signé. la plage est donc de -2^31 à 2^31-1.

La fpu (floating point unit ou coprocesseur arthmetique) permet de jouer avec des entiers sur 64 bit et qui ont dc une plage si on compte seulement les positif jusque 2^64-1 soit +- 1.8 * 10^19. Le problème est que VB n'implémente qu'une version modifier : le Currency. il décale la valeur de 10 000.  je ne sais plus si cette implemantation est signée ou non mais son max ne depassera de toute facon pas 1.8*10^15 et tu va perdre pas mal de temps.

Si tu veux quelque chose efficace pour un eventuelle RSA je te conseille de te tourner vers le C++ et d'utiliser sa librairie ZZ (une tite recherche sur google pour la trouver).

Pour l'algo des 3 indiens c'est utile uniquement pour les très grand nombre et n'est pas trivial a implémenter. la premiere condition à vérifier est que le nombre ne peux pas s'écrire sous la forme n=a^b ou un truc du style.

Il y a un autre algo fort utiliser pour le RSA c'est Miller-Rabin qui se base sur des nombre aléatoire mais il ne donne qu'une probabilité si le nombre est premier. Si le test dit que le nombre n'est pas premier c sur a 100% sinon la probabilité qu'il ne soit pas premier est de 1/4. en repetant le test n fois la probabilité sera de (1/4)^n. on peux donc être amplement satisfait après une 20aine de test (1 chance sur 4^20 soit 1 sur +- 10^12)

voilà si t'as des question je m'etait pas mal renseigner sur les nombre premiers. Le plus rapide est sans doute Erathostene mais inaplicable sur des grand nombre.

signaler à un administrateur
Commentaire de dnob700 le 22/11/2004 17:18:44

mouais, c'est pas du tout optimisé...

Ca sers à rien d'utiliser des double parce qu'il ont 12 ou 13 chiffre de précision mais au delà, tout est perdu et le calculs que tu fait n'ont plus de signification.

Donc il faut le faire avec des long, mais tant que tu ne gère pas de nombres plus grand que la limite des long, on peut dire que tu gère des "petits" nombres.

donc une méthode très rapide pour faire le calcul est tout simplement le crible d'érathostène, tu cré un tableau pour stocker tes nombre, mais pas un tableau horrible comme on te l'a conseillé plus haut, juste un tableau de byte ou chaque bit représente un nombre :
e premier est 3, le 2ième est 5 et ainsi de suite tout les nombre impair sauf 1.

bon, et ensuite, je suppos eque tu conait le principe du crible d'érathostène (tu coche tout les nombre multiple de nombre premer et à la fin, ce qu'il reste est les nombre premier.

signaler à un administrateur
Commentaire de Mindiell le 22/11/2004 17:42:13

un tableau représentant tous les impairs ?

Le problème, c'est que s'il veut diviser rapidement son nombre a tester par les 100 premiers "nombres premiers", il doit les retrouver, non ? L'avantage du tableau "horrible" c'est qu'il contient les 100 premiers :o)

Pour Erathostene, tu pourrais mieux expliquer ? J'ai pas le temps de faire de recherche, mais j'aimerais comprendre le truc quand meme ;o)

signaler à un administrateur
Commentaire de dnob700 le 22/11/2004 17:53:09

ben non, mon tableau on s'en sers pour faire le croble :

disons que le premier bit vaut 3.

tu parcours donc le tableau de 3 en 3 en mettant tout les octets à zéro (il faut qu'avant ça, tout est été initialisé à 1 ou le contraire).
En parcourant le tableau de 3 en 3, tu passe les nombre de six en six, mais c'est pas grave puice que un sur deux est pair.

quand c'est fini (c'est a dire quand t'arrive au bout de ton tableau).
tu rapars du début et tu cherche le premier éléments qui soit à 1.
ici, ça sera le deuxième, alors tu recherche sa valeur (pour l'élément x (le premier est 1et non pas 0) c'est (x*2+1)) et tu pacours le tableau de x*2+1 en x*2+1 donc là de 5 en 5, mettant tout à 0.

et on recommence, tu cheche le premier qui soit à 1 et tu mets à zéro tout ces multiple.

à la fin, il ne te reste à un que les nombre premier.

avec cette méthode j'ai calculé les 100 000 000 premier nombre premier non pas un 2 jours mais en 2 minutes a peu près (bon, avec un noyau pour la manipulation du tableau en C, mais même en pure VB, ça sera bcp plus rapide).

signaler à un administrateur
Commentaire de Mindiell le 22/11/2004 18:01:49

Donc un tableau de 100 millions de bits ? Marrant comme procédé, je connaissais pas.

Par contre, pour tester si un grand nombre est premier ou pas, ca marche plus du tout (ou alors faut y aller)...

signaler à un administrateur
Commentaire de dnob700 le 22/11/2004 18:15:13

100 milions de bit c'est que 12 méga octets soit moins que les 70 necessaire pour stocker les nombres en dur (j'utilise les chiffres donné plus haut par mad&matt)

de toute façons, à moins de compressé à la volée c'est la meilleure méthode pour sauvegarder les premier nombre premier (jusqu'a 100 milliosn c'est que les premier) après, quand leur consistance devient trop faible il faut envisager autre chose.

mais un tableau de double, dynamique qui plus est, est vraiment une abération (dans la même mémoire on ne mets même pas 2 millions de nombre premier).

signaler à un administrateur
Commentaire de sibi12 le 22/11/2004 18:18:26

Non comme j'ai dit Erathostene est inapplicable pour les grand nombre.  Une source sur cppfrance implementai vraiment bien erathostene mais je tombe plus dessus... si je la retrouve je vous fais signe

signaler à un administrateur
Commentaire de dnob700 le 22/11/2004 18:20:52

oui, mais 100 millions, c'est un petit nombre.

sauf a savoir si 86 125 647 est un nombre premier sans calculer les autres, là, ça sers à rien.

signaler à un administrateur
Commentaire de Mindiell le 22/11/2004 18:22:20

On est d'accord pour le stock de tous les nombres premiers, ca devient délirant. mais si c'était pour accélérer la fonction "est-ce un nombre premier", je pense que mon idée peut donner un compromis intéressant (tableau de 100 voire 200 premiers nombres premiers)...

Ceci dit, le crible d'erathostene m'intrigue, je vais me pencher dessus :)

signaler à un administrateur
Commentaire de vlad2i le 22/11/2004 18:27:40

Les cribles ... absolument inefficaces ...

Le crible d'Eratostène consiste a préparer un tableau et a éliminer les nombres en fonction des Modulo ... ce qui revient a faire le code "brutal" que l'on avait au début, a savoir

For I = 0 to sqr(x)
If x mod I = 0 then x pas premier
...

Maintenant, pour le stock, il faut prendre en compte que si le but du code n'est que de décorer... autant ne pas se trouer les méninges... maintenant si tu veux que ca soit utile, tu peux adapter ton code pour des recherches sur les très très grands nombres premiers (sans me faire de la pub, j'ai fais un module qui permet de gérer de tels entiers et que tu pourrais utiliser assez facilement)

Accélérer la recherche au dela me semble difficile, au vu des limitations (pratiques) de VB...

Mais je ne doute pas que qqn y arrive quand meme :)

Vlad

signaler à un administrateur
Commentaire de Mindiell le 22/11/2004 18:29:30

86 125 647 est divisble par 3... hum ;op

signaler à un administrateur
Commentaire de Pingouin le 22/11/2004 18:56:34

Ué en effet la formule de Ramanujan est rapide autant pour moi (ptet moins que les algo probabiliste il me semble mais bon) mais c vrai que c'est pas evident a implementer.
Par contre a mon avis le crible c'est pas la peine a mon avis c'est pas efficace pour de grands nombres.
Mais au fait tant qu'il y est ya moyen d'etendre le prog a la factorisation en facteurs premiers non ? :-) (histoire d'élargir le débat ... koike 36 commentaires c deja pas mal lol)

Pingouin

signaler à un administrateur
Commentaire de MadM@tt le 22/11/2004 21:48:11

Oula ça ma fait bcp de mails en un jour ça, ne paniquont pas
zoslex > yes bonne idée, vu le gain de temps je vais vite mettre ça au point
Pour les autres à propos des grands nombres j'ai encore jamais regardé mais je me pencherai bien dessus
Sinon au niveau du crible d'erastosthene et patati et patata vous etes sur que ça peut permettre de gagner du temps ? Parce que ça a l'air compliqué et pour moi qui dit compliqué du beaucoup de calculs donc un temps long, enfin je dit ça sans avoir jamais testé quoi....

sinon merci à tous pour vos commentaires

PS : j'essayerai bien de mettre cette source en C++ ou C#, mais est ce que le C# est aussi rapide que le C++ ?

signaler à un administrateur
Commentaire de vlad2i le 22/11/2004 21:50:40

MadMatt>Lit mon commentaire sur Eratostene (qui précise que ca ne fera que le ralentir ton programme)

Vlad :)

signaler à un administrateur
Commentaire de MadM@tt le 22/11/2004 21:58:30

Oui j'ai vu ça mais j'entendais aussi la formule de Ramanujan et le tableau des 100 ou 200 nombres premiers dans le lot
Mais le problème des grands nombres reste encore je vais essayer de regarder ça si je trouve du temps

signaler à un administrateur
Commentaire de sibi12 le 22/11/2004 22:37:02

Vlad2i > Erathostene est surtout rapide pour avoir tout le nombre premier de 1 à n.
il est surtout plus rapide car on ne fait aucune division et 5 6 addition seront tjs plus rapide que 1 modulo(le modulo a la meme instruction machine que la division) il y aussi quelque rotation pour implementer le tableau decrit par dnob700 mais c'est 1 cycle aussi comme l'addition.

sinon si c'est juste pour verifier un nombre ca vaut pas la peine (une idée sur le moment coupler erathostene avec la methode classique : on fait un tableau de sqrt(n)/2 bits et avant de mettre à un les nombre non premier on verifie si il est diviseur de n... à creuser mais fort limité)

MadM@tt > logiquement C# et C++ devrait etre aussi rapide l'un que l'autre mais je n'en suis pas convaincu. l'ennui du C# est qu'il y a plein de truc qu'on ne contrôle pas comme la memoire, le garbage collector peux se declencher à n'importe quel moment, il faut passer en mode non proteger pour gere les pointeurs,... je pense qu'il vaux mieu faire en C++ et au besoin appeler une Dll d'un programme C#

signaler à un administrateur
Commentaire de vlad2i le 22/11/2004 22:46:40

"Vlad2i > Erathostene est surtout rapide pour avoir tout le nombre premier de 1 à n.
il est surtout plus rapide car on ne fait aucune division et 5 6 addition seront tjs plus rapide que 1 modulo(le modulo a la meme instruction machine que la division)"

Eratostene consiste a éliminer les nombres en fonctions des modulos, pas en fonction des additions... on ne fait pas d'additions me semble-t-il

Enfin si ma mémoire n'est pas encore totalement décrépie...

Vlad

signaler à un administrateur
Commentaire de dnob700 le 22/11/2004 23:27:51

C# et C++ ne sont certainement pas aussi rapide.

le C# est compilé pour la CLR, c'est a dire exactement la même chose que du VB (donc il a la même vitesse, d'ailleur de VB.NET est un peu plus lent que du VB6).

Par contre, du vrai C++, compilé pour win32 (ou linux) est plusieurs centaines (peut être seulement plusieurs dizaine, c'est assez dificile de faire des test précis car ça n'a pas grand chose à voir) de fois plus rapide peut-être.

signaler à un administrateur
Commentaire de MadM@tt le 23/11/2004 00:05:25

zoslex > Ton idée de ne pas ajouter dans la liste les nombres trouvés n'apporte aucun gain de temps (visible). En effet tu a surement du supprimer la ligne qui ajoutait le nombre à la liste si il était premier afin de voir si c'était plus rapide, mais ce n'est pas le fait de l'ajouter dans la liste qui prend du temps, mais plutot de savoir s'il est premier ou pas.
J'ai essayé plusieurs méthode pour stocker les resultats dans une chaine de caractère, un tableau, mais pas de changement de vitesse significatif.... à moins que j'ai mal compris ce que tu voulais dire....
mais merci d'avoir proposé l'idée quand meme
@ +

signaler à un administrateur
Commentaire de MadM@tt le 23/11/2004 00:06:48

Ps : j'en suis à un fichier de 310 Mo lol
je suis allé jusqu'à un nombre qui s'écrit avec 8 chiffres, dans les 500 000 000 (500 millions) c'est pas mal non ?
mais ça reste bien loin des supercalculateurs

signaler à un administrateur
Commentaire de Mindiell le 23/11/2004 00:16:53

désolé dnob700, et on n'est pas la pour lancer une polémique, mais de nos jours, les compilateurs donnent des vitesses équivalentes...

MadM@tt, en effet, ne pas utiliser ta liste de gauche accélère de beaucoup le calcul quand tu en fais un long...A priori, ca le fait même planter au bout d'un moment (Textbox trop petite...)

signaler à un administrateur
Commentaire de sibi12 le 23/11/2004 16:20:40

vlad2i > je pense que tu dois confondre erathostene avec autre chose... Il n'y a aucun modulo.

tu prend le premier nombre premier c a d 2 (mais on peux aisément le sauter pour gagner en performance) et tu fais plus 2 et tu coche le nombre obtenu c a d 4 puis 4 + 2 et tu coche dc le 6 tu continue juske n ensuite tu prends le premier nombre qui n'est pas cocher c a d 3 tu fait + 3 tu coche le 6 (il est deja cocher d'ou l'interet de sauter le 2 : cfr dnob700 : "En parcourant le tableau de 3 en 3, tu passe les nombre de six en six, mais c'est pas grave puice que un sur deux est pair")

Il n'y a donc aucun modulo/division même pas une simple multiplication !!!sachant qu'une addition s'effectue en 1 cycle comme toute les autres instruction de l'algorithme (mise à part les accès memoire qui eux sont plutôt fréquent. on doit charger 4 octet tout les 64 nombre si le programme est bien optimiser) on comprend pourquoi il est si rapide.

dnob700 > Le CLR et le run-time VB n'ont absolument rien en commun ! Tu te trompes. Le CLR  prend du code CIL et le traduit en code machine, avec une aussi bonne optimisation que du C++ (pour autant que le programme soit bien écrit), lors de la première exécution d'une fonction, ensuite la fonction est stockée en langage machine et s'exécute comme une application normale (en gros).

En VB c'est complètement différent t'as ton programme en langage machine mais 9 instructions sur 10 font appelle a une dll ce qui ralenti sensiblement ton code surtout que beaucoup d'appelle utilise le protocole COM dont la lenteur des appels de fonction est bien réputé. et même pour les appel qui n'utilise pas COM, passé les arguments sur la pile pour faire une addition n'est pas skon peux trouver de mieux niveau performance.

Je ne pense donc pas qu'on puisse dire que VB soit plus rapide qu'un programme .Net à part peut-être au premier appel de la fonction (au besoin on peut utiliser sgen il me semble pour compiler le CIL en langage machine)

signaler à un administrateur
Commentaire de zoslex le 23/11/2004 17:29:40

Je ne vois pas ce que tu aurais pu mal comprendre.
Le gain est largment visible... Je pense que la perte est constante puisque dû à la perte de temps d'afficher en permanence.
Ce que j'ai changé :


' Procédure qui cherche les nombres premiers
Private Function CherchePremier()
    Dim Number As Double

    'zoslex
    Me.Liste.Visible = False
    
    Me.Caption = "Recherche ... - MadMatt"


puis à la fin de la fonction :


    Me.Caption = "Fini !"
    
    'zoslex
    Me.Liste.Visible = True
    
End Function


Merci de dire si tu vois mieux, ou si tu ne vois toujours rien.
Préviens si tu mets à jour, que je télécharge la dernière version, merci :)

signaler à un administrateur
Commentaire de vlad2i le 23/11/2004 19:03:12

sibi12> C'était donc bien d'eratostene que je parlais : tu m'a fais une excellente explication de ce qu'est un modulo :) (qui est par ailleurs dans le cas de certains nombres bien plus rapide que l'addition successive :p)

De plus, il a parfaitement raison de dire que le CLR compile des programmes a peu près aussi rapides que VB6

MadMatt & zoslex> Encore mieux : essayez l'api LockWindowUpdate :)

LockWindowUpdate list1.hWnd
'remplissage
...
LockWindowUpdate 0
list1.Refresh

Evidemment, il faut faire
LockWindowUpdate 0
list1.Refresh

de temps en temps (exemple tous les 10000 éléments ajoutés) pour que ton prog ne plante pas

Vlad

signaler à un administrateur
Commentaire de sibi12 le 23/11/2004 19:24:08

vlad2i > je ne comprend pas pkoi tu dis que la methode classique en verifiant si tout les nombres de 1 à n sont premier est plus rapide... chaque addition te permet de verifier si un nombre est premier. on cherche pas le modulo, c'est pas le nombre d'addition qu'on cherche. je reste persuader que pour trouver tout les nombre premier de 1 à n c le plus rapide (pour une valeur raisonnable de n sinon les nombre premier s'espace de plus en plus et beaucoup d'addition ne serve plus a rien)

je me disai la même chose du CLR au debut mais en y regardant de plus près le jit fais qu'on a un code plus ou moins aussi rapide que du C++. l'idéal pour le verifier serai de faire un sgen sur un prog .Net et voir

signaler à un administrateur
Commentaire de vlad2i le 23/11/2004 19:28:26

je crois que tu n'as pas compris...

Chercher tous les nombres premiers de 1 à n... c'est exactement ce que fait ce programme

Maintenant, la méthode du crible d'eratostene consiste a barrer tous les éléments d'un tableau périodiquement (a savoir par exemple, tous les multiples de 17) ce qui revient mathématiquement à un modulo, qui est, de plus très rapide.

Si x mod y = 0, alors x est un multiple de y , donc on le barre car un premier ne peut etre un multiple :)

Quant aux compilations, les vitesses dépendent tant de la machine que du programme que de la méthode que du moment

Si c'est pas flagremment différent, considère que c'est pareil

Vlad

signaler à un administrateur
Commentaire de dnob700 le 23/11/2004 20:07:51

je me suis mal exprimé, mais le VB.NET compile pour le clr aussi, et non plus pour la machine virtuel visual basic comme le faisait VB6, c'est donc exactement la même chose que du C#

ce qui n'est par le cas du C++ compilé pour win32 (faites l'essai, je ne veut pas lancer de polémique, mais c'est vraiment plus rapide).

pour ce qui est des nombres premiers, il y a ces deux pdf qui sont très bon si vous êtes un peu interessé par de la théorie :

http://perso.wanadoo.fr/sectionpc/tpe_cryptage/crypto/pdfs/primalite.pdf (en français)

http://perso.wanadoo.fr/sectionpc/tpe_cryptage/crypto/pdfs/primality.pdf (en anglais)

signaler à un administrateur
Commentaire de sibi12 le 23/11/2004 22:00:51

Oui je vois ce que tu veux dire...

mais il te faut plusieurs essais avant de trouver de ton y. alors qu'avec erathosthene tu trouve toute une volée d'x d'un seul coup l'ennui est que parfois il sont deja cocher. enfin j'ai jms trop aimé erathosthene et j'ai jms fait de test mais jme suis tjs di ke ça devait etre plus rapide... têtre que je me trompe.. je n'en sais rien.

"Quant aux compilations, les vitesses dépendent tant de la machine que du programme que de la méthode que du moment"

Je vois pas où tu veux en venir.. même si je reconnais que ce sera jms aussi rapide que du C++ (quoique en theorie ça devrait après la première compilation mais je me suis vite rendu compte du contraire), ça n'equivaut quand même pas à du VB vu la lourdeur des appels de fonction.

signaler à un administrateur
Commentaire de MadM@tt le 23/11/2004 22:08:54

zoslex > oui je n'avais pas compris, j'ai essayé ton code mais je n'ai pas trouvé d'amélioration vraiment flagrante, tu trouve vraiment