Discussion :

[screetch]

ma politique la dessus c'est d'inclure ce dont tu as besoin même si tu sais qu'un autre include l'inclus lui aussi et donc que tu vas l'avoir indirectement.
Le programme principal utilisant vector, il devrait inclure vector (après tout on pourrait préceclarer vector dans le fichier verifPremier.h, et si on décide de faire ca on fait péter le fichier main.cpp ce que je trouve un peu cradoc)
on est donc pas vraiment censé aller voir les autres fichiers inclus lorsqu'on décide de quoi on a besoin; ca viole un peu l'encapsulation. Et on ajoute une dépendance bien mal venue.

[koala01]

ma politique la dessus c'est d'inclure ce dont tu as besoin même si tu sais qu'un autre include l'inclus lui aussi et donc que tu vas l'avoir indirectement.
Le programme principal utilisant vector, il devrait inclure vector (après tout on pourrait préceclarer vector dans le fichier verifPremier.h, et si on décide de faire ca on fait péter le fichier main.cpp ce que je trouve un peu cradoc)
on est donc pas vraiment censé aller voir les autres fichiers inclus lorsqu'on décide de quoi on a besoin; ca viole un peu l'encapsulation. Et on ajoute une dépendance bien mal venue.

Je partirais plutôt d'une politique inverse :

Par défaut, je considère qu'un fichier inclus me fournit tout ce dont il a besoin, que ce soit par inclusion d'autres fichiers ou par déclaration anticipée.

S'il apparait, pour une raison ou une autre, qu'il manque une définition complète d'une classe, j'inclus le fichier correspondant

Si tu peux, de cette manière, limiter le boulot du préprocesseur, cela peut te faire gagner pas mal de temps sur de (très) gros projets

[screetch]

je comprends bien oui, ca tombe dans une zone un peu grise; le main.cpp utilise ici un vector avec resize() donc pour moi il a besoin de <vector>. SI il ne s'en servait pas il ne devrait pas inclure <vector>

comme dans un même temps le fichier header va lui aussi avoir besoin de <vector> ca parait doublon

mais en fait le fichier header pourrait se contenter de le predeclarer ou inclure un fichier qui ne fait que predeclarer. Il me semble que main.cpp a une dépendance forte vers <vector> et elle devrait se traduire dans les headers

ares, j'ai aussi tendance a croire que tant que ca marche, pas la peine de toucher, j'oublie toujours plein de headers inclus par ricochet. C'est pas vital, je voulais pinailler...

[Emmanuel Deloget]

Salut,

Pourquoi ne pas utiliser une list plutôt qu'un vector? J'ai l'impression que ce serait plus approprié pour ton algo :
-Tu fais un accès séquentiel à ton container ( pas besoin de l'accès par indices ), donc tu peut accéder à tes nombres premiers avec un simple itérator sur cette liste.
-Ça solutionne le problème de la réservation anticipée de la mémoire, puisque là, le push_back n'est pas pénalisant.

Une liste stocke ses données a peu près n'importe ou en mémoire. Du coup, accéder à un élément de la liste va probablement provoquer un cache miss, ce qui va avoir un impact non négligeable sur le temps de calcul si la liste est importante. Un tableau permet de limiter ce problème puisque les éléments sont contigus. Un cache miss va générer le prefetch de toute une partie du tableau, et les éléments attenant seront déjà dans le cache avant d'y accéder.

Sur la taille du tableau à allouer : vu que tu stocke les nombre premiers, le nombre max d'élément est au plus égal à la racine carrée du nombre maximum testé. Sur 100,000,000, ce nombre est donc au plus égal à 10,000.

Sur les valeurs à utiliser pour faire la division : tu peux te limiter à < racine_carre(n) ; Dans R=X/Y où X,Y sont entier et Y > racine_carrée(X), R ne peut pas être entier ET supérieur à Y. Du coup, s'il est entier, alors il a déjà été vérifié avant.

Au niveau des micro-optimisations : cet article peut t'intéresser. Tu est dans un cas où tu va avoir de nombreuses mauvaises prédiction de branchement, donc ça peut valoir le coup de jouer avec les conditions. Si tu utilises g++ pour compiler, tu peux lui donner des informations supplémentaires sur le fait que certaines branches sont plus probables que d'autres (cf. http://www.imodulo.com/gnu/gcc/Other-Builtins.html)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
# define likely(x)      __builtin_expect(!!(x), 1)
# define unlikely(x)    __builtin_expect(!!(x), 0)
 
if (likely(cond)) {
  // cond est vrai dans la majorité des cas
}
if (unlikely(cond)) {
  // cond est faux dans la majorité des cas. 
}

Il n'y a pas d'équivalent sur Visual C++.

Un autre optimisation possible est d'utiliser les instructions SIMD. La liste des diviseurs possible est connue, puisqu'il s'agit de la liste des nombres premiers calculés. Si cette liste est organisée de manière a aligner les blocs de valeurs sur 16 bytes, alors il devient possible de charger les valeurs 4 à 4 dans un registre 128 bits. La vérification ressemble a :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
o = { n, n, n, n }
 
load128(o, v0)
p = 0
while (nbnump - p > 4) {
  load128 (tablenump + p, v1)
  v2 = div_entier_4x32(v0, v1)
  v3 = mul_entier_4x32(v2,v1)
  v2 = sub_entier_4x32(v0,v3)
  r = {0, 0, 0, 0}
  si !r[0] || !r[1] || !r[2] || !r[3] {
    // le nombre n'est pas premier
    return 0
  }
  p += 4
}
for i=p; p<nbnump; ++p
  if ((n % tablenump[p]) == 0) return 0
 
return 1

Bien sur, c'est du pseudo code. Il faut encore trouver les instructions SSE qui vont bien...

[screetch]

Sur la taille du tableau à allouer : vu que tu stocke les nombre premiers, le nombre max d'élément est au plus égal à la racine carrée du nombre maximum testé. Sur 100,000,000, ce nombre est donc au plus égal à 10,000.

preuve?

il y a 25 nombre premiers inferieurs a 100, alors qu'il devrait y en avoir au plus 10 d'après toi. Je ne doute pas que 10000 est assez mais je me demande si il existe une formule =)

[screetch]

maintenant je doute que 10000 soit assez =) il y en a 664,579 inférieurs a 10,000,000 (http://en.wikipedia.org/wiki/Prime-counting_function)

[koala01]

En fait, la racine carrée permet de déterminer quelle est la valeur maximale à tester car c'est effectivement la valeur qui permet, multipliée par elle-même, d'obtenir la valeur de référence, mais ce n'est absolument pas pour cela que l'on peut en déduire qu'il n'y aura jamais qu'un nombre de... nombres premiers inférieur à cette racine carrée... Ce serait oublier que, entre X et X*X, il y a énormément de possibilités

Il est cependant vrai que, plus on monte dans la valeur maximale, moins le nombre de nombres premiers augmente

[screetch]

il y a pas mal de théorie dessus (beaucoup de frapadingues sur terre pour faire des recherches sur un sujet aussi compliqué )
et ca a pas l'air de décroitre tres vite; pour 10^24, il y a un termes en 10^22 de nombres premiers. Y'en a quand même beaucoup!

[Emmanuel Deloget]

maintenant je doute que 10000 soit assez =) il y en a 664,579 inférieurs a 10,000,000 (http://en.wikipedia.org/wiki/Prime-counting_function)

et @koala.

Comment j'ai fait mes maths moi ?...



Je crois que je n'étais pas assez concentré sur ce que j'écrivais... (c'est pas peu dire)

@koala01 : je ne crois pas qu'il y ait un preuve. Il y a une conjoncture qui donne une idée de la quantité de nombres premiers entre deux valeurs, mais pas grand chose de plus (en tout cas, selon mes souvenirs).

[akorx]

Petit souci !

Bon j'ai besoin de votre aide une fois de plus... mon programme que voici calcule bien les 10 millions de premiers nombres premiers mais se ferme sans explication lorsque je lui en demande 1 milliard.

Je supposais initialement qu'il s'agissait d'un souci au niveau de mes "int" et je les ai donc passés en "unsigned int" mais sans succes...

- fichier main() :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
#include <iostream>
#include <fstream>
#include <ctime>
#include <vector>
#include <windows.h>
#include "verifPremier.h"
 
using namespace std;
 
int main()
{
    unsigned int i(3);
    unsigned int nb(1000000000); // je veux ici le premier milliard de nb premiers
    unsigned int *Pi=&i;
    vector<unsigned int> t;
    //t.reserve(nb/2);
    t.push_back(2);
    long H;
    time(&H);
    cout << "Recherche des " << nb << " premiers nombres premiers :" << endl << endl;
    cout << "Heure de lancement                 = " << ctime(&H) << endl;
    clock_t const T0 = clock();
        while (t.size()<=nb)
        {
            if (t.size()%(nb/1000)==0)
            {
                cout << '\r' << t.size() << " trouves" ;
            }
            siPremier(Pi,t);
            i+=2;
        }
    time(&H);
    clock_t const TFin = clock();
    cout << endl << endl ;
    cout << "Heure de fin                       = " << ctime(&H) << endl ;
    cout << "Temps de calcul                    = " << ((TFin-T0)*1000/CLOCKS_PER_SEC) << " ms" << endl << endl;
    cout << "Plus grand nombre premier trouve   = " << t.back() << endl << endl ;
    cout << "Ecriture des resultats dans le fichier resultat.txt... patientez" << endl << endl ;
    ofstream fichier("resultat.txt", ios::trunc | ios::trunc);  //déclaration du flux et ouverture du fichier
    for (i=0;i<=nb;i++)
    {
        fichier << t[i] << endl;
        if (i%(nb/100)==0)
        {
            cout << '\r' << i/(nb/100) << " % effectues" ;
        }
    }
    fichier.close();  // on referme le fichier
    cout << endl << endl << "Ecriture terminee." << endl << endl << endl << endl << endl;
    system("PAUSE");
    return 0;
}

- fichier verifPremier.h :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
#ifndef VERIFPREMIER_H_INCLUDED
#define VERIFPREMIER_H_INCLUDED
#include <vector>
 
//void siPremier(int *Pi , std::vector<int> & t );
void siPremier(unsigned int *Pi , std::vector<unsigned int> & t );
void autresiPremier(int r , std::vector<int> & t );
 
#endif // VERIFPREMIER_H_INCLUDED

- fichier verifPremier.cpp :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include <iostream>
#include <cmath>
#include <vector>
#include "verifPremier.h"
 
using namespace std;
 
void siPremier(unsigned int *Pi , std::vector<unsigned int> & t )
{
    int taille=t.size();
    int i=0;
    int j=0;
    //while (pow(t[i],2)<=*Pi && i<=taille-1 && j==0)
    while (t[i]*t[i]<=*Pi && i<=taille-1 && j==0)
    {
        if (*Pi%t[i]==0)
        {
            j++;
        }
        i++;
    }
    if (j==0)
    {
        t.push_back(*Pi);
    }
}

Une âme charitable pourrait me dire pourquoi il se plante? je suis quasiment persuadé que ça tourne autour des limites de mes variables mais sans en être sûr...

Autre question : mon programme fonctionne bien évidemment sur un seul cœur, comment les programmeurs qui bossent sur des "calculs scientifiques" feraient ils pour optimiser un tel calcul avec mes 4 cœurs par exemple dans la mesure où rien ici n'est "parallélisable" hormis peut être l'écriture en temps réel des résultats dans le fichier "resultat.txt" (un thread serait dédié au parcours du vector "t" et à l'écriture du fichier "resultat.txt")... sans grand intérêt mais ma question est purement pédagogique) ?

NB : La plus grosse perte de temps ici tourne surement aussi autour de l'affichage dans le main() de la progression du calcul via :

if (t.size()%(nb/1000)==0)
{
cout << '\r' << t.size() << " trouves" ;
}

... je pense qu'ici le modulo "pese" lourd et qu'il faudrait mieux avoir un autre système d'affichage de la progression.

[3DArchi]

Une âme charitable pourrait me dire pourquoi il se plante? je suis quasiment persuadé que ça tourne autour des limites de mes variables mais sans en être sûr...

Sur 32 bits, tu arrives aux limites du système

Autre question : mon programme fonctionne bien évidemment sur un seul cœur, comment les programmeurs qui bossent sur des "calculs scientifiques" feraient ils pour optimiser un tel calcul avec mes 4 cœurs par exemple dans la mesure où rien ici n'est "parallélisable" hormis peut être l'écriture en temps réel des résultats dans le fichier "resultat.txt" (un thread serait dédié au parcours du vector "t" et à l'écriture du fichier "resultat.txt")... sans grand intérêt mais ma question est purement pédagogique) ?

l'écriture dans un fichier dans un thread séparé, oui. Mais il risque de passer (?) son temps à attendre le disque plutôt que de récupérer les données.
Quand à paralléliser sur plusieurs coeurs : je ne sais pas si ton algorithme trivial s'y prête. Mais il doit peut être (?) exister des algo de recherche de nombre premier parallélisable ? Mes maths sont trop loin pour te répondre.

NB : La plus grosse perte de temps ici tourne surement aussi autour de l'affichage dans le main() de la progression du calcul via :

if (t.size()%(nb/1000)==0)
{
cout << '\r' << t.size() << " trouves" ;
}

... je pense qu'ici le modulo "pese" lourd et qu'il faudrait mieux avoir un autre système d'affichage de la progression.

Ce n'est pas le modulo, c'est l'affichage. L'accès à l'affichage (ou à un fichier sur un disque) dégrade sans commune mesure tes performances. On ne fait pas de mesure de perfs avec des traces à l'intérieur.

[akorx]

Sur 32 bits, tu arrives aux limites du système

En quoi ici j'atteinds de telles limites ? mes valeurs ne dépassent pas le milliard ce qui est "tout petit"... quant au vector il ne contient "que" 1 milliard de cases de unsigned int...

[3DArchi]

En quoi ici j'atteinds de telles limites ? mes valeurs ne dépassent le milliard ce qui est "tout petit"...

Un int sur un windows 32 bits est sur 4 octets. 1 Milliard * 4 octets pour un entier = ~3,7Go. Le max adressable en 32 bits sous windows est un peu inférieure à 3 Go. Il faut revoir ta façon de faire

[akorx]

Un int sur un windows 32 bits est sur 4 octets. 1 Milliard * 4 octets pour un entier = ~3,7Go. Le max adressable en 32 bits sous windows est un peu inférieure à 3 Go. Il faut revoir ta façon de faire

Ah ok encore merci 3DArchi pour la petite explication... une solution pour contourner ce problème pourrait donc être l'utilisation de n tableau t (avec chacun une taille acceptable) ?

[akorx]

Je réponds à ma propre remarque située juste au dessus... j'ai lu un peu rapidement ta réponse 3Darchi et je n'avais pas bien compris où se situait la limite dont tu parlais. La limite étant lié à l'OS et à son adressage en RAM, ma solution n'est pas envisageable .