J'ai pas lu en totalité ton algo ni tenté de le comprendre, mais en le parcourant en diagonale je vois déjà que tu utilises des divisions dans une double boucle do...while, et des nombres flottants au lieu de nombre entiers (floor, etc.). C'est LE truc idéal pour ralentir à mort ton algo. Une division, c'est coûteux* : c'est déjà bien plus coûteux qu'une multiplication, et en plus les calculs flottants (avec des nombre à virgule, quoi) sont également bien plus coûteux que les calcules en nombre entiers. Or dans ton cas ton problème est justement sur des nombres entiers (les nombres premiers), pourquoi donc passer par les nombres décimaux dans ton algo ? Rien que ça ralentit le tout. Et comme mentionné dans un message plus haut (par Philippe je crois), pour savoir si a est un multiple de b, avec a et b entier, il suffit de regarder si (a%b==0) : carrément moins coûteux qu'une division, et en plus tu ne travailles qu'avec des entiers (int).
Je n'ai pas trop regardé comment fonctionne ton algo dans l'ensemble et si le reste du code est bien fait où s'il y a d'autres trucs à améliorer, mais déjà si tu fais rien que cette modification, de remplacer tes divisions de float et tes comparaisons avec floor** par un test sur le modulo ([tt]nbactuel % Nbp[tableauactuel][/tt]) à mon avis tu auras un gain vraiment non négligeable, et tes 2'39 vont fondre comme neige au soleil.
* quand je dis coûteux, c'est à l'échelle de l'optimisation : évidemment une petite division comme ça entre deux nombres ça ne fait pas de mal, mais dans le cas d'un algo que tu cherches à optimiser, la moindre microseconde coûte, surtout dans des boucles répété plein de fois.
** en plus en théorie la formule utilisant la comparaison avec floor introduit potentiellement un risque d'erreur dû à l'erreur d'arrondi, même si FLT_EPSILON est faible il n'en n'est pas moins non nul.
Tu verras si tu as prochainement des cours d'algorithmie ou d'info un peu plus bas niveau dans ton école, y'a plein de trucs intéressants à apprendre sur le sujet
En même temps c'est un peu compréhensible qu'une division soit plus long (en terme de nombre de cycles processeur) qu'une multiplication, et qu'un calcul sur des flottants soit plus long qu'un calcul sur des nombres entiers (surtout quand on sait que les flottants sont codés suivant la norme IEEE.754, si ça t'intéresse de te documenter dessus pour mieux comprendre).
Pour des usages ponctuels ou de tous les jours, ça n'a aucune incidence dans ton programme, (que le calcul prenne 1 cycle ou 4 cycles d'horloge, à la vitesse où c'est cadencé tu ne t'en apercevra pas) mais pour des algos, les passes d'optimisation, etc. ces quelques cycles en plus multiplié par un bon paquet d'itérations, tu vois vite la différence entre un algo en O(n) et un en O(log(n)) !
L'algorithmie et l'optimisation de ces algo est un sujet vaste et passionnant, et on voit vite que dans le contexte d'optim d'un algo, certains choix pouvant paraà®tre anodins peuvent changer beaucoup s'ils sont bien choisis, et que certains algos ou idées toutes bêtes peuvent faire gagner énormément mine de rien
Retire les printf( ) et les NSString formatés dans ta méthode ... tu verras l'impact sur le temps d'exécution. Dans ce genre de situation, on calcule une fois pour toutes les nombres premiers dont on a besoin que l'on stocke dans un tableau (pour les nombres premiers < 1 million c'est une boucle calcul de l'ordre du dixième, du centième de seconde)
Encore en lecture en diagonale (donc sans chercher à comprendre l'algo quoi), je vois :
encore des "if (x != floor(x))" au lieu de "if (a%b != 0)"
un "if (test) ... else if (!test) ..." donc inutile (le "else" tout seul au lieu de "else if" suffit, là tu perds des cycles d'horloge à faire un test inutile, et en plus tu fais 2x ton calcul "nbactuel%Nbp[tableauactuel]" !
un printf, ça prend du temps et ces cycles d'horloge aussi, mine de rien l'affichage couteux aussi. Si tu testes un algo avec des NSLog ou printf et le même algo sans les printf tu vas vite t'en apercevoir
Très légère optimisation (je me demande même si le compilateur ne la fait pas toute seule), préférer "++x" à "x++" quand tu n'as pas besoin de post-increment (quand cela ne change pas ton algo de faire un pre-increment ou le post-increment) : le post-increment oblige le compilo à mettre de côté la valeur courante le temps du calcul, bien souvent inutilement
en parlant d'optimisation que le compilateur fait tout seul, dans les réglages de ton projet, vérifier quel niveau d'optimisation est choisi pour la compilation (correspond au flag -O de gcc, -O0 = pas d'optim, -O1, -O2, -O3 = il fait de plus en plus d'efforts pour optimiser). Normalement d'ailleurs dans les configurations de compilation par défaut, la config "Debug" n'optimise pas ou peu le code, la config "Release" l'optimise au mieux, donc tu devrais voir une différence de vitesse entre ces deux configs.
Voilà , encore un peu de ménage à faire :P Tu verras, après tout ça déjà tu pourras comparer le temps d'exécution du nouveau programme nettoyé (et optimisé en mode release) avec ton temps d'origine, comme quoi avec des modifications simples (même pas dans la logique décisionnelle de l'algo, en plus), on peut facilement accélérer genre x4 la vitesse de calcul...
PS : Pour faire tes calculs de temps que prend ton algo et ton programme, théoriquement il ne suffit pas simplement de le lancer et chronométrer le temps avant qu'il te donne la réponse :
Il existe des commandes shell (comme "time" typiquement) qui permet de mesurer le temps d'exécution d'un programme (pour que cela ait un sens il faut bien sûr que ton programme lance le calcul tout de suite sans te demander de rentrer une valeur ou afficher une interface graphique -- car sinon le temps que tu tapes la valeur et valide pour lancer le calcul pouvant varier -- et qu'il finisse dès le calcul terminé ; sinon ça va fausser le chronométrage bien sûr). C'est donc adapté pour les programmes de type "ligne de commande", et pas aux programmes avec une interface graphique ou un prompt. Mais bon à connaà®tre
Mais pour correctement évaluer le temps de calcul d'un algo, surtout, il faut :
L'exécuter plusieurs fois de suite, car d'une part ça permet de faire une moyenne, et en plus avec les processeurs modernes et les architectures diverses et surtout les systèmes de cache, un programme peut mettre un temps T à faire un calcul la première fois, et mettre bien moins de temps la seconde s'il le proc a ce qu'il faut dans son cache...
Effectuer des relevés de temps pour plusieurs valeurs d'entrée : ici certes pour vérifier que tu optimises ton algo tu peux comparer le temps d'exécution toujours pour la même valeur d'entrée, mais si tu veux vraiment avoir une idée de la rapidité de ton algo dans son ensemble, faut regarder ses temps pour diverses valeurs d'entrée n. Pour voir s'il est plutôt linéaire O(n) ou quadratique O(n²) ou au contraire logarithmique O(log(n), car ce qui est intéressant c'est aussi de savoir s'il est de plus en plus lent plus la valeur d'entrée n est grande, et si oui à quelle vitesse sa rapidité se dégrade, etc
A priori je dirai (uniquement à vue de nez) que c'est un algo en O(n.log(n)) (double boucle do...while, mais c'est pas du n² pour autant puisque pour chaque nombre n à tester tu ne re-parcourres que le tableau des nombres premiers précédemment calculés, et pas tous les diviseurs de 0 à n), ce qui est plutôt encourageant pour un algo de primes.
Retire les printf( ) et les NSString formatés dans ta méthode ... tu verras l'impact sur le temps d'exécution. Dans ce genre de situation, on calcule une fois pour toutes les nombres premiers dont on a besoin que l'on stocke dans un tableau (pour les nombres premiers < 1 million c'est une boucle calcul de l'ordre du dixième, du centième de seconde)
en effet ça joue un ptit peu aussi...je savais pas qu'il fallait penser à autant de truc pour optimiser :P
quand tu dit de l'ordre du centième de seconde c'est pour calculer les nombres premiers < 1 million?parsque même optimisé à fond ça peut pas aller aussi vite ! à moins que mon algorythme soit vraiment mal foutu.en effet dans mon prog je les stocker dans un tableau,mais c'est le but du programme donc je les regénèrent à chaque lancement.
Pour l'instant, j'en suis là dans mes tests : On détecte les nombres premiers entre 1 et Nmax, pour les nombres premiers < 1 million, j'en suis à 6 millièmes de secondes.
J'applique le crible d'Erathostène que tu as évoqué un peu plus haut
sérieux c'est Erathostène qui la trouvé ? je savais pas que ça avais un nom cette méthode...je dit pas que j'arrive à son ptit orteil mais je suis content de savoir que j'ai fait pareil que lui sans le savoir
le truc c'est que j'utilise un interface graphique et je ne le fait pas dans le shell.Et je ne fait pas que afficher les nombres 1er,mon prog décompose aussi le nombre rentré en nombres premiers et l'affiche.
lorsque j'enlève les printf et les NSString il va énormement plus vite ! :P
Du coup comment tu arrives à des temps si bas Philippe ?
Voilà mon code, compilé avec [tt]gcc primes.c -O3 -o primes[/tt] et mesuré avec [tt]time ./primes 10000[/tt] par exemple
#include <stdlib.h><br />#include <stdio.h><br /><br />// doit être assez large pour contenir le nombre de nombres premiers à stocker<br />#define PRIMES_TAB_SIZE 500000<br /><br />int main(int argc, char* argv[])<br />{<br /> int primes[PRIMES_TAB_SIZE];<br /> int nbPrimes = 0; // found primes<br /> int testedVal, idx, nMax;<br /> int hasDivider;<br /> <br /> if (argc<2) {<br /> printf("Usage: %s Nmax\n",argv[0]);<br /> exit(1);<br /> }<br /> nMax = atoi(argv[1]);<br /><br /> primes[nbPrimes++] = 2;<br /> // 2 est le premier nombre premier<br /> // pour les suivants, on part de 3, et on incrémente de 2 en 2<br /> // (et non de 1 en 1) comme ça on ne teste que les nombres impairs<br /> for(testedVal=3;testedVal<nMax;testedVal+=2)<br /> {<br /> hasDivider = 0;<br /> for(idx=0;idx<nbPrimes;++idx)<br /> {<br /> if (testedVal % primes[idx] == 0) // found a multiple, so testedVal is not a prime<br /> {<br /> hasDivider = 1;<br /> break;<br /> }<br /> }<br /> if (!hasDivider) primes[nbPrimes++] = testedVal;<br /> }<br /> <br /> /*<br /> for(idx=0;idx<nbPrimes;++idx) {<br /> printf("[%03d] %d\n",idx,primes[idx]);<br /> }<br /> */<br />}
héhé je vois que mon ptit jeu amuse tout le monde... :P
je suis content parsque je suis à 19s aussi pour un million mais le problème c'est que je tombe à 6'25" pour 5 millions... et puis mon MBP me sert de bouilloire maintenant (93° le processeur... )
Matos : mac book pro Intel 2,66 GHz Intel COre 2 Duo
Le code : on enregistre le fait que le bit de position i soit le rang d'un entier i non premier (ou premier cela revient au même, mais calloc existe alors que l'initialisation à 0xFFFFFFFF prendrait du temps) (compilé -O3 aussi)
Ceci dit, je n'ai pas essayé, c'est peut-être moins coûteux en temps de travailler sur les octets plutôt que sur les bits (pour la petite histoire, j'avais besoin de vérifier mes macros sur les bits pour un mini-projet d'étudiants) et mes macros sont peut-être encore optimisables ...
<br />// Les macros :<br /><br />/***********************************************************************<br /> * getBit(a,i) est une macro qui vaut le "i-ième bit" de la zone mémoire<br /> * pointée par le pointeur a. sizeof(*a) doit valoir 1.<br /> * Si i >= 8, (exple i=20) le bit est pris dans l'octet <br /> * - à l'adresse a+i/8, ce qui correspond à la valeur a[i/8] (exple a[2])<br /> * - au bit i%8 (exple 4ème octet, sur 2^3 donc) <br /> * La valeur de la macro est un int qui vaut 0 ou 1 <br /> ***********************************************************************/<br />#define getBit(a,i) (((a)[(i)/8] & 1<<((i)%8) )!=0) <br /><br />/***********************************************************************<br /> * setBit(a,i) est une macro qui donne la valeur 1 au "i-ième bit" de la zone mémoire<br /> * pointée par le pointeur a. sizeof(*a) doit valoir 1.<br /> * Si i >= 8, (exple i=20) le bit est pris dans l'octet <br /> * - à l'adresse a+i/8, ce qui correspond à la valeur a[i/8] (exple a[2])<br /> * - au bit i%8 (exple 4ème octet, sur 2^3 donc) <br /> ***********************************************************************/<br />#define setBit(a,i) ( (a)[(i)/8] = (a)[(i)/8] | 1<<((i)%8) )<br /><br />int main(int argc, char * argv[]){<br /> unsigned long long Nmax; <br /> sscanf(argv[1],"%llu",&Nmax);<br /><br /> int p=2,m;<br /> unsigned char * nonPrime=calloc(1+Nmax/8,1);<br /> nonPrime[Nmax/8]=0x1;<br /> <br /> while(p*p<=Nmax){ <br /> // Mettre le bit à 1 sur les multiples du nombre premier p<br /> for(m=p*p;m<=Nmax;m+=p) setBit(nonPrime,m);<br /> // Chercher le nombre premier suivant<br /> for(p++;getBit(nonPrime,p);p++) ;<br /> }<br /> <br /> free(nonPrime);<br /> return 0;<br />}<br />
Peut-être que je me trompe Ali mais j'ai essayer de comprendre ton code et malgré pleins de trucs que je ne comprend pas,je crois que tu incrémente de deux en deux pour remplir ton tableau primes alors qu'il serai plus rapide d'incrémenter par les nombres premiers trouvés précédement.
Ah oui j'ai oublié de n'aller que jusqu'à √nMax D'ailleurs au lieu d'aller jusqu'à n/2 (d'ailleurs pour les divisions par une puissance de 2 c'est plus rapide de faire un shift, en l'occurrence n>>1 est équivalent mais plus rapide que n/2 pour un entier), donc de tester si i<nMax/2, tu peux tester non pas que i<sqrt(nMax), mais tester que [tt]i*i<nMax[/tt] (puisque sqrt est monotone)
Ah oui j'ai oublié de n'aller que jusqu'à √nMax D'ailleurs au lieu d'aller jusqu'à n/2 (d'ailleurs pour les divisions par une puissance de 2 c'est plus rapide de faire un shift, en l'occurrence n>>1 est équivalent mais plus rapide que n/2 pour un entier), donc de tester si i<nMax/2, tu peux tester non pas que i<sqrt(nMax), mais tester que [tt]i*i<nMax[/tt] (puisque sqrt est monotone)
oui en effet ça mérite d'être testé...
j'ai testé la différence entre i < nMax/2 et i*i < nMax et la différence n'est pas significative du moins jusqu'a un million avec mon algorythme...mais je mesure pas du tout précisément faudrait que je fasse un compteur pour ça...
Correction de mon code pour ne tester les diviseurs que jusqu'à [tt]primes[idx]<√testedVal[/tt] (ou plutôt [tt]primes[idx]*primes[idx]<testedVal[/tt]) en remplaçant la boucle for interne ainsi :
en parlant d'optimisation que le compilateur fait tout seul, dans les réglages de ton projet, vérifier quel niveau d'optimisation est choisi pour la compilation (correspond au flag -O de gcc, -O0 = pas d'optim, -O1, -O2, -O3 = il fait de plus en plus d'efforts pour optimiser). Normalement d'ailleurs dans les configurations de compilation par défaut, la config "Debug" n'optimise pas ou peu le code, la config "Release" l'optimise au mieux, donc tu devrais voir une différence de vitesse entre ces deux configs.
je me suis mit en mode release et en effet ça à changé :P par contre je n'arrive pas a trouver flag -O3 , il faut faire click-droit sur le fichier de projet dans Xcode et Get Info c'est ça ?
Et en effet, mon algo (qui est à priori le même sur le principe que prepa75) n'est pas le crible d'Erathostène si je dis pas de bétise. Pour chaque nombre N je vérifie qu'il s'il est divisible par un des nombres premiers trouvés avant.
Alors que toi Philippe, tu fais vraiment le crible officiel : pour chaque nombre tu barres tous les multiples de ce nombre, puis tu cherches le prochain nombre non barré (qui est donc le prochain premier) et tu continues. Jusqu'à √nMax. Ce qui explique la différence de perfs
je me suis mit en mode release et en effet ça à changé :P par contre je n'arrive pas a trouver flag -O3 , il faut faire click-droit sur le fichier de projet dans Xcode et Get Info c'est ça ?
Pour le flag -O3 c'est quand tu compiles en ligne de commande directement avec gcc (ce qu'on je fait jamais quand on utilise Xcode, Xcode appelle gcc comme il faut pour nous justement). Le réglage dans Xcode qui correspond se trouve en effet dans les "Build Settings" du projet (Pomme-I sur le projet dans Xcode, puis aller sur l'onglet Build), il suffit de taper "optim" dans le champ de recherche pour tomber dessus : il s'agit du réglage "Optimization Level" dans le groupe de réglages "GCC 4.2 - Code Generation" (et quand tu cliques en face de ce réglage tu vois qu'il te propose en effet les options correspondant aux flags -O0, -O1, -O2, -O3, -Os)
Pour le flag -O3 c'est quand tu compiles en ligne de commande directement avec gcc (ce qu'on je fait jamais quand on utilise Xcode, Xcode appelle gcc comme il faut pour nous justement). Le réglage dans Xcode qui correspond se trouve en effet dans les "Build Settings" du projet (Pomme-I sur le projet dans Xcode, puis aller sur l'onglet Build), il suffit de taper "optim" dans le champ de recherche pour tomber dessus : il s'agit du réglage "Optimization Level" dans le groupe de réglages "GCC 4.2 - Code Generation" (et quand tu cliques en face de ce réglage tu vois qu'il te propose en effet les options correspondant aux flags -O0, -O1, -O2, -O3, -Os)
Nikel j'ai trouvé...mais je ne risque pas d'avoir vos performances
Réponses
pour une fois je post sans poser une question,admirez l'effort :P
j'ai fini mon programme et je tenais à vous montrer mon algorythme...dites moi si il y a un problème de méthode/structure...
merci par avance pour vos remarques
pour information : le 78497ème nombre premier est : 999983
Une division, c'est coûteux* : c'est déjà bien plus coûteux qu'une multiplication, et en plus les calculs flottants (avec des nombre à virgule, quoi) sont également bien plus coûteux que les calcules en nombre entiers.
Or dans ton cas ton problème est justement sur des nombres entiers (les nombres premiers), pourquoi donc passer par les nombres décimaux dans ton algo ? Rien que ça ralentit le tout. Et comme mentionné dans un message plus haut (par Philippe je crois), pour savoir si a est un multiple de b, avec a et b entier, il suffit de regarder si (a%b==0) : carrément moins coûteux qu'une division, et en plus tu ne travailles qu'avec des entiers (int).
Je n'ai pas trop regardé comment fonctionne ton algo dans l'ensemble et si le reste du code est bien fait où s'il y a d'autres trucs à améliorer, mais déjà si tu fais rien que cette modification, de remplacer tes divisions de float et tes comparaisons avec floor** par un test sur le modulo ([tt]nbactuel % Nbp[tableauactuel][/tt]) à mon avis tu auras un gain vraiment non négligeable, et tes 2'39 vont fondre comme neige au soleil.
* quand je dis coûteux, c'est à l'échelle de l'optimisation : évidemment une petite division comme ça entre deux nombres ça ne fait pas de mal, mais dans le cas d'un algo que tu cherches à optimiser, la moindre microseconde coûte, surtout dans des boucles répété plein de fois.
** en plus en théorie la formule utilisant la comparaison avec floor introduit potentiellement un risque d'erreur dû à l'erreur d'arrondi, même si FLT_EPSILON est faible il n'en n'est pas moins non nul.
En même temps c'est un peu compréhensible qu'une division soit plus long (en terme de nombre de cycles processeur) qu'une multiplication, et qu'un calcul sur des flottants soit plus long qu'un calcul sur des nombres entiers (surtout quand on sait que les flottants sont codés suivant la norme IEEE.754, si ça t'intéresse de te documenter dessus pour mieux comprendre).
Pour des usages ponctuels ou de tous les jours, ça n'a aucune incidence dans ton programme, (que le calcul prenne 1 cycle ou 4 cycles d'horloge, à la vitesse où c'est cadencé tu ne t'en apercevra pas) mais pour des algos, les passes d'optimisation, etc. ces quelques cycles en plus multiplié par un bon paquet d'itérations, tu vois vite la différence entre un algo en O(n) et un en O(log(n)) !
L'algorithmie et l'optimisation de ces algo est un sujet vaste et passionnant, et on voit vite que dans le contexte d'optim d'un algo, certains choix pouvant paraà®tre anodins peuvent changer beaucoup s'ils sont bien choisis, et que certains algos ou idées toutes bêtes peuvent faire gagner énormément mine de rien
ça a l'air super intéressant et c'est concret et utile donc tout benef
qu'en pense-tu Ali ?
Dans ce genre de situation, on calcule une fois pour toutes les nombres premiers dont on a besoin que l'on stocke dans un tableau (pour les nombres premiers < 1 million c'est une boucle calcul de l'ordre du dixième, du centième de seconde)
Voilà , encore un peu de ménage à faire :P
Tu verras, après tout ça déjà tu pourras comparer le temps d'exécution du nouveau programme nettoyé (et optimisé en mode release) avec ton temps d'origine, comme quoi avec des modifications simples (même pas dans la logique décisionnelle de l'algo, en plus), on peut facilement accélérer genre x4 la vitesse de calcul...
A priori je dirai (uniquement à vue de nez) que c'est un algo en O(n.log(n)) (double boucle do...while, mais c'est pas du n² pour autant puisque pour chaque nombre n à tester tu ne re-parcourres que le tableau des nombres premiers précédemment calculés, et pas tous les diviseurs de 0 à n), ce qui est plutôt encourageant pour un algo de primes.
en effet ça joue un ptit peu aussi...je savais pas qu'il fallait penser à autant de truc pour optimiser :P
quand tu dit de l'ordre du centième de seconde c'est pour calculer les nombres premiers < 1 million?parsque même optimisé à fond ça peut pas aller aussi vite ! à moins que mon algorythme soit vraiment mal foutu.en effet dans mon prog je les stocker dans un tableau,mais c'est le but du programme donc je les regénèrent à chaque lancement.
On détecte les nombres premiers entre 1 et Nmax, pour les nombres premiers < 1 million, j'en suis à 6 millièmes de secondes.
sérieux c'est Erathostène qui la trouvé ? je savais pas que ça avais un nom cette méthode...je dit pas que j'arrive à son ptit orteil mais je suis content de savoir que j'ai fait pareil que lui sans le savoir
le truc c'est que j'utilise un interface graphique et je ne le fait pas dans le shell.Et je ne fait pas que afficher les nombres 1er,mon prog décompose aussi le nombre rentré en nombres premiers et l'affiche.
lorsque j'enlève les printf et les NSString il va énormement plus vite ! :P
Juste pour voir, je viens de coder le crible vite fait, et "time" me donne les temps suivants pour ma part :
Du coup comment tu arrives à des temps si bas Philippe ?
Voilà mon code, compilé avec [tt]gcc primes.c -O3 -o primes[/tt] et mesuré avec [tt]time ./primes 10000[/tt] par exemple Testé sur mon MacBook Pro Core2Du 2.2GHz
je suis content parsque je suis à 19s aussi pour un million mais le problème c'est que je tombe à 6'25" pour 5 millions...
et puis mon MBP me sert de bouilloire maintenant (93° le processeur...
Le code : on enregistre le fait que le bit de position i soit le rang d'un entier i non premier (ou premier cela revient au même, mais calloc existe alors que l'initialisation à 0xFFFFFFFF prendrait du temps)
(compilé -O3 aussi)
Ceci dit, je n'ai pas essayé, c'est peut-être moins coûteux en temps de travailler sur les octets plutôt que sur les bits (pour la petite histoire, j'avais besoin de vérifier mes macros sur les bits pour un mini-projet d'étudiants) et mes macros sont peut-être encore optimisables ...
et moi j'ai dit que j'allais jusqu'a nMax/2 et non nMax (normalement il faudrait sqrt(nMax) mais c'est plus rapide de diviser par 2 )
sous réserve de bien avoir compris ton code...
ouais le tiens est plus puissant (le mien fait 2,16 GHz) mais je ne pense pas que la différence soit aussi significative
c'est bête de perdre autant avec l'interface graphique...ça faisait des beau temps sinon
D'ailleurs au lieu d'aller jusqu'à n/2 (d'ailleurs pour les divisions par une puissance de 2 c'est plus rapide de faire un shift, en l'occurrence n>>1 est équivalent mais plus rapide que n/2 pour un entier), donc de tester si i<nMax/2, tu peux tester non pas que i<sqrt(nMax), mais tester que [tt]i*i<nMax[/tt] (puisque sqrt est monotone)
oui en effet ça mérite d'être testé...
j'ai testé la différence entre i < nMax/2 et i*i < nMax et la différence n'est pas significative du moins jusqu'a un million avec mon algorythme...mais je mesure pas du tout précisément
Ce qui change tout côté temps :
je me suis mit en mode release et en effet ça à changé :P par contre je n'arrive pas a trouver flag -O3 , il faut faire click-droit sur le fichier de projet dans Xcode et Get Info c'est ça ?
Waouw en effet !! mais je ne comprend pas la différence par rapport à avant : voici ma boucle interne peut-tu me dire comment la modifier ?
Et en effet, mon algo (qui est à priori le même sur le principe que prepa75) n'est pas le crible d'Erathostène si je dis pas de bétise.
Pour chaque nombre N je vérifie qu'il s'il est divisible par un des nombres premiers trouvés avant.
Alors que toi Philippe, tu fais vraiment le crible officiel : pour chaque nombre tu barres tous les multiples de ce nombre, puis tu cherches le prochain nombre non barré (qui est donc le prochain premier) et tu continues. Jusqu'à √nMax.
Ce qui explique la différence de perfs
Le réglage dans Xcode qui correspond se trouve en effet dans les "Build Settings" du projet (Pomme-I sur le projet dans Xcode, puis aller sur l'onglet Build), il suffit de taper "optim" dans le champ de recherche pour tomber dessus : il s'agit du réglage "Optimization Level" dans le groupe de réglages "GCC 4.2 - Code Generation" (et quand tu cliques en face de ce réglage tu vois qu'il te propose en effet les options correspondant aux flags -O0, -O1, -O2, -O3, -Os)
Nikel j'ai trouvé...mais je ne risque pas d'avoir vos performances
merci par avance
P.S. : je peut vous mettre le projet entier si ça peut vous aider.
[EDIT] : j'ai élaguer un ptit peu mon programme et j'ai simplifier au maximum.
.h :
et .m :