RECHERCHE LINÉAIRE DE NOMBRES PREMIERS [C - MULTIPLATEFORME]
lynxtyle
Messages postés
79
Date d'inscription
samedi 25 septembre 2004
Statut
Membre
Dernière intervention
31 octobre 2011
-
10 nov. 2011 à 18:28
sazaju Messages postés 48 Date d'inscription lundi 4 août 2008 Statut Membre Dernière intervention 3 juin 2013 - 15 nov. 2011 à 11:25
sazaju Messages postés 48 Date d'inscription lundi 4 août 2008 Statut Membre Dernière intervention 3 juin 2013 - 15 nov. 2011 à 11:25
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/53747-recherche-lineaire-de-nombres-premiers-c-multiplateforme
https://codes-sources.commentcamarche.net/source/53747-recherche-lineaire-de-nombres-premiers-c-multiplateforme
15 nov. 2011 à 11:25
14 nov. 2011 à 15:53
Dans tous les cas, la manière dont tu initialises ton tableau vide est loin d'être optimisée, ce qui lorsqu'on lit ton code d'augure rien de bon pour la suite. Avant de te lancer dans des procédures évoluées comme CUDA je te conseillerais d'apprendre à maitriser les outils de base. Surtout si tu t'adresses à des débutants : Quelqu'un d'expérimenté pourra garder les bons trucs de ton code et oublier les mauvais, mais un débutant va tout garder, et prendre des mauvaises habitudes.
Encore une fois, si je prend le temps de te laisser des commentaire, c'est pour t'aider. Si tu n'en veux pas dit le et j'arrêterai de commenter tes sources.
Tu as là un sujet intéressant. Si tu ne sais pas dans quelle direction partir je te conseillerais de paralleliser le remplissage du tableau (d'abord en C bien optimisé, puis plus tard pourquoi pas une version CUDA. Ce serait un très bon cas d'initiation à cette technologie).
14 nov. 2011 à 13:19
Donc comme pour PGL10 si t'as des attentes plus pointues tu peux en faire la demande j'aurai surement de quoi te combler mais les premiers codes de la série seront pour le moment de bas niveau histoire d'avoir tout les mécanismes expliqués (là tu mélange les 2 premières sources et tu atteinds la limite des 8*4Go pour stocker ton information...)
Ensuite je fais te et me contredire sur un point : certe optenir quelques milliards de nombre premier n'a pas d'intérêt mais les codes finaux permettent de traiter des nombres premiers très élevés (144*10^18 et plus) et à partir de là se trouve des intérêts... Pour ma part le résultat final est un mémoire disponible à l'Institut Galilée "Clés SLL Faillibles ?" (tout est dans le titre... certe il faut des moyens mais on se rend compte qu'aujourd'hui le Web est loin d'être très sûr)
Enfin pour les limites de la plateforme non il y a des limites impossible à obtenir à la compilation (ok pour le int64 j'aurai pu mais quand je l'ai développé j'ai pas pensé aux 32 bits) car il est impossible de savoir à l'avance la taille que prend à l'avance ton programme en mémoire surtout que cette taille n'est que rarement fixe et surtout à part windows qui à son standard, sur les unixoïd c'est un grand bazar...
(si j'avoue que j'aurai pu trouver les limites mais avec des risques justement à cause de comportement imprévu... mais grâce à l'allocation dynamique j'aurai pu faire une boucle d'allocation sur l'erreur... c'est à dire j'alloue le maxi puis si j'ai une erreur j'alloue maxi-- jusqu'à ce que l'allocation réussisse... mais là encore je préfère laisser les élève trouver plutôt que donner une solution toute faite)
Je ne sais pas encore ce que je vais faire pour la source suivante : mixe des 2 premières sources ou proposer cette source optimisé avec OpenCL ou CUDA (et donc battre des record de vitesse de calcul avec PGL10 ^_^') ou partir sur une initiation aux io 64 bits avec seeko64 et compagnie ou tout autre chose ?
14 nov. 2011 à 11:25
Sans aller profondément dans les détails, tu pourrais grandement optimiser to code en ne mettant dans ton tableau que les nombres impairs, puisque tu sais que les nombres pairs ne sont jamais premiers.
Pour commencer, ca réduirait la consommation mémoire de moitié.
Ne le prend pas mal mais je ne suis pas d'acord avec ta remarque "techniquement si j'applique toute les accélèrations possibles je te parie qu'on téléchargera beaucoup l'exécutable mais que très peu s'attarderaient sur le code...".
Mes raisons :
- Calculer des nombres premiers, ca sert à rien. Le but de ces sources est uniiquement de se faire plaisir (tu peux trouver des listes toutes faites sur des sites comme celui-ci http://www.prime-numbers.org/ gratuitement ou a prix très abordable).
- Vu que ce genre de source n'interresse que les gens qui s'amusent à les reproduire, si ton algo est vraiment rapide, ils n'ont rien à faire de ton exécutable... Au contraire, ils vont décortiquer ton code pour essayer de trouver quelques astuces permettant de rendre leur propre code plus rapide :o)
Enfin, merci pour ton source : ca fait plaisir de voir qu'il y a toujours des gens qui font du code "juste pour le fun" ;o)
Eric
NB: Pour les limites propres à la plateforme, je suis pratiquement sur que tu peux les déterminer à la compilation en utilisant des defines standards et relativement portables.
13 nov. 2011 à 21:21
tout d'abord le code attaque un point rarement rencontré sauf lorsqu'on s'attaque à des problèmes de maths : les limites machines... qui sont loin d'être les limites des spécifications du language car sinon on aurait pu sortir un tableau d'une taille int_max. Ici on rencontre donc un premier problème qui est la limite du système d'exploitation... (les 1,5Go maximum attribué par application sous windows, sous linux ça diffère suivant les distributions) ce qui nous oblige à avoir une limite maximum inférieur à 1,5 millards d'octet (car il faut aussi compter dans cette somme la taille du reste de l'application...). l'utilisation de l'allocation dynamique de la mémoire permet au passage d'éviter en cas de dépassement d'avoir une erreur de segmentation (il refuse dès le départ et donc inutil d'attendre que le programme plante).
De plus le code fonctionne sous 32 et 64 bits... la raison pour laquel je peux monter à maximum 1 milliard sur 32 bits et 1,4 milliard sur 64 bits est le fait que sur la plateforme 32 bits mon long long équivaut à un int (et donc fausse mon résultat ce qui plante le tout). Si j'aurai stoppé la recherche à MAXI/2 on peut faire la recherche jusqu'à 1,4 milliard sur 32 bits aussi (ou alors au lieu de tester i*v<x tester i<x/v... ce qui nous permet d'effectuer les calculs jusqu'à MAXI)...
Je voudrai aussi revenir sur ma source précédente qui n'a apparament rien à voir (http://www.cppfrance.com/codes/FONCTION-EDITION-FICHIER-BIT-BIT-MULTIPLATEFORME_53710.aspx) mais qui permet de repousser encore ces limites en travaillant directement sur les bits... on peut alors stocker 8 fois plus de valeurs, donc sur système 64 bits on aurait pu monter jusqu'à 12 milliards... (ou mieux on traite directement l'information sur le disque... en réunissant les 2 sources en l'état actuel tu peux traiter jusqu'à 32 milliards)
Ensuite c'est aussi un cas d'école sur le fait que j'applique le crible d'Eratosthène de façon la plus basique possible mais qu'au final on peut relever plein de points où il est inutile de faire les calculs. Sans parler des remarques déjà présentes en commentaires dans le code il y a aussi le fait que je fait une exploration du tableau avec i++ alors qu'on sait dès le départ qu'on cherche que dans les impair donc i=i+2 à partir d'un i impaire... ensuite dans des optimisations qui apporterait beaucoup de gain de temps : une fois un premier trouvé, inutile de calculer tout les multiple de i... on peut facilement en éliminer... par exemple inutile de faire les multiple pair (et oui tout ce qui auront un résultat pair seront déjà éliminé !), puis inutile de faire les multiple de i avec les nombres premiers connu (et oui par exemple 3x5 et 5x3 donne le même résultat... donc inutile de faire les même calcul 2 fois !)... enfin bon au final on peut éliminer un maximum de calculs inutiles...!
Je reviens aussi sur un point présent en commentaire dans la source : vu que c'est une recherche linéaire, arrivé au premier N, on sait alors qu'on à tout les premiers inférieurs à N*2... une des accélérations possible dans la recherche est donc de la parallèliser car il y a plusieurs premiers à traiter entre N et N*2 (sur mon i7 ça permet de traiter 8 premiers à la fois, et en version OpenCL je peux en traiter pour ma part environs 1000 à la fois... d'ailleur je suis en train de me demander si j'en ferai pas une version OpenCL ou CUDA pour l'occasion ^_^')
Enfin bon... techniquement si j'applique toute les accélèrations possibles je te parie qu'on téléchargera beaucoup l'exécutable mais que très peu s'attarderaient sur le code... maintenant ils ont un code simple, pas mal de pistes pour faire leurs expériences : à eux de s'amuser ! Surtout qu'il faut bien l'avouer qu'aujourd'hui calculer les nombres premiers inférieurs à quelques milliards n'a pas d'intérêt ;)
Ensuite si les recherches plus pointues t'intéresses je pourrai poster beaucoup d'autres choses (d'ailleur il n'y a pas que les nombres premiers... donc si t'as des attentes n'hésite pas à demander)
13 nov. 2011 à 20:02
13 nov. 2011 à 18:44
Pour les plus intéressés il y a un mémoire à la bibliothèque de l'Institut Galilée sur ces travaux qui au final serve pour le déchiffrement des clés SSL (qui ne sera par fourni ici).
La je pensai fournir la source suivante avec la gestion des fichiers de très grande capacité et utilisant la bibliothèque gmp (la limite de recherche devenant la limite du système de fichier qui là est déterminé)... version non optimisé encore une fois pour rester soft...
Pourquoi pas l'avoir mis directement ? Simplement par ce que je réécris tout ces codes pour l'occasion afin d'avoir des choses faciles à comprendre et compiler... une fois gmp rajouté je vais perdre 50% de ce qui ne connaissent pas grand chose au C car il faut rajouter des liens au compilateur (et avoir installé la bibliothèque etc...) donc je fourni tout les mécanismes avant...
Mais si ça n'intéresse pas j'arrête de publier ici ;)
13 nov. 2011 à 17:55
10 nov. 2011 à 18:28
Pour un MAXI de 1 millard
sur le 2,4Ghz - 4Go de RAM : 80sec
sur un même 2,4Ghz mais 512Mo de RAM : 1h (à cause sur "swap")
sur un i7 970 refroidissement liquide - 24Go de RAM : 20sec
Pour les MAXI j'ai pu relever les maximums suivant "toléré" par les systèmes :
1.000.000.000 pour les windows 32 bits
1.400.000.000 pour les windows 64 bits
j'ai pu passer un int_max (plus de 2 milliards) sur un debian 64 bits
je ne les garanties pas mais normalement jusqu'à 1 milliard ça passe partout et surtout n'oubliez pas de mettre une valeur inférieur à votre RAM (sinon ça va être long... donc par exemple pour la machine à 512Mo il vaut mieux un MAXI de 300.000.000)