RECHERCHE LINÉAIRE DE NOMBRES PREMIERS [C - MULTIPLATEFORME]

Signaler
Messages postés
79
Date d'inscription
samedi 25 septembre 2004
Statut
Membre
Dernière intervention
31 octobre 2011
-
sazaju
Messages postés
48
Date d'inscription
lundi 4 août 2008
Statut
Membre
Dernière intervention
3 juin 2013
-
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

sazaju
Messages postés
48
Date d'inscription
lundi 4 août 2008
Statut
Membre
Dernière intervention
3 juin 2013

Je ne vois pas la source, c'est normal ?
LeFauve42
Messages postés
239
Date d'inscription
vendredi 20 octobre 2006
Statut
Membre
Dernière intervention
20 avril 2009

Pour répondre à ta question, oui j'ai lu tes commentaires malgrès leur longueur :o). Tu parles d'incrémenter ton compteur de 2 par 2 pour sauter les nombres pairs. Je te dis de ne carrement pas les mettre dans ton tableau, ce qui est bien plus efficace.

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).
lynxtyle
Messages postés
79
Date d'inscription
samedi 25 septembre 2004
Statut
Membre
Dernière intervention
31 octobre 2011
2
@LEFAUVE42 : Tu aurais pu lire les commentaires... tu fais que redire ce que j'ai dit... Ensuite encore une fois comme dit à PGL10 il va y avoir d'autre sources derrière plus complète qui vont tomber qui reprennent tout ces mécanismes... et les accélèrations sont pour la plupars proposé dans les commentaires (de la source et du post...) : il suffit de lire et de les appliquer pour obtenir un bon résultat (la seule solution proposé un peu compliqué que j'ai proposé c'est de le parallèliser... et j'ai proposé de peut-être sortir une source avec OpenCL pour ça...)
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 ?
LeFauve42
Messages postés
239
Date d'inscription
vendredi 20 octobre 2006
Statut
Membre
Dernière intervention
20 avril 2009

Bonjour,

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.
lynxtyle
Messages postés
79
Date d'inscription
samedi 25 septembre 2004
Statut
Membre
Dernière intervention
31 octobre 2011
2
En fait là ce petit code est un "cas" d'école et peut mériter plusieurs points d'explications que je n'ai pas donné ici mais qui mériterait d'être fourni à ce que je n'ai pas comme élève :

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)