Crible d'Eratosthène segmenté

[ganon551]

Bonjour à tous,

J'aimerais coder l'algorithme du crible segmenté en c++. J'ai déjà bien exploré le crible normal, et les performances en hausse de la version segmentée m'attirent.

Du coup j'ai écris le code suivant, qui est une version très naïve du crible, je veux juste que ça fonctionne et pouvoir après l'optimiser.

Code :

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
#include <iostream>
#include <math.h>
#include <vector>
#include <cstdlib>
 
using namespace std;
 
int main()
{
int max = 100000;
int square, i, j,k;
int limite = ceil(sqrt(max));
int compteur2 = 0;
int slice;
 
if(max > 10000)
slice = 10000;
else
slice = limite;
 
if(limite % 2 != 0)
limite++;
 
square = ceil(sqrt(limite));
 
vector<char> tableau(limite, 0x1);
 
for(i = 2; i < limite; i+=2)
{
    tableau[i] = 0x0;
}
 
for(j = 3; j <= square; j+=2)
{
    for(k = j * j; k <= limite; k+= j)
    {
        tableau[k] = 0x0;
    }
}
 
int compteur = 1;
 
for(i = 3; i < limite; i+=2)
{
    if(tableau[i] == 0x1)
    compteur++;
}
 
std::vector<int> segment(slice,1);
 
for(int y = limite; y <= max;y+=slice)
{
    for(int z = 0; z <= slice; z++)
    {
        if(z % 2 == 0)
        segment[z] = 0;
        else
        {
            if(z+y < max)
            segment[z] = z + y;
            else
            segment[z] = 0;
        }
    }
 
    for(int g = 3; g <= limite; g+=2)
    {
        if(tableau[g] == 0x1)
        {
            for(int h = 1;h <= slice;h++)
            {
 
            if(segment[h] != 0)
            {
                if(segment[h] % g == 0)
                segment[h] = 0;
            }
 
 
            }
        }
    }
    for(int r = 1; r <= slice;r++)
    {
        if(segment[r] != 0)
        {
            compteur2++;
 
        }
    }
 
}
 
cout << compteur2+compteur << endl;
 
return 0;
}

Bon je sais, le code est sale mais j'ai essayé tellement de choses que forcément ça salit

Du coup mon problème est le suivant : Si je déclare max à plus de 100.000, le programme plante au moment de la déclaration du vector<int> segment. Ce que je ne comprend pas, étant donné que je l'initialise avec la variable "slice" qui n'a rien à voir avec "max".

Si je remplace ce vector par un array de int, ça marche très bien.

Autre problème, et c'est peut-être lié, si vous lisez le code vous remarquerez ça :

Code :

1
2
3
4
5
 
if(z+y < max)
segment[z] = z + y;
else
segment[z] = 0;

C'est la seule solution que j'ai trouvé à un problème, en effet z va de limite à max par pas de slice, à la fin je me retrouve donc avec un vector segment qui fait toujours la même taille (ici 10.000), alors que je n'ai besoin que d'une taille de 10.000 - limite. Je ne sais pas si je me fais bien comprend

Du coup, est-il possible "proprement" de fixer la taille du vector<int> segment dans ma boucle z ?

Autre question, niveau performance, que vaut-il mieux choisir entre un vector et un array, sachant que je compte déclarer des array/vector de unsigned long long (64 bits donc) d'une taille comprise entre 32k et 256k selon le choix de l'utilisateur ?

Merci pour vos éclaircissements

[r0d]

Bonjour,

quel compilateur utilises-tu?

Essaie de remplacer

Code :

std::vector<int> segment(slice,1);

par

Code :

std::vector<int> segment(slice);

, et dis-nous ce que ça donne.

De façon générale, les tableaux sont aussi rapides que les vector. Mais dans certains cas, vector est plus rapide.

[Bousk]

Bonjour,

Envoyé par r0d

De façon générale, les tableaux sont aussi rapides que les vector. Mais dans certains cas, vector est plus rapide.

Euh... Quoi ???

vector représente un tableau, en interne il s'agit d'un tableau tout ce qu'il y a de plus classique, maquillé pour contenir des fonctions et le modifier.
les seules actions "lentes" de vector sont l'ajout d'élément, quand une réallocation est nécessaire.
Dans tous les cas, vector ne sera pas plus rapide qu'un C-Array, puisqu'il ajoute une indirection. Mais on peut compter sur l'inline etc afin d'optimiser tout ça et que ça passe (complètement) inaperçu.

Le mieux étant de réserver la taille suffisante, pour qu'aucune réallocation ne soit faite avec les ajouts à venir, avec vector::reserve

Ce que je ne comprend pas, étant donné que je l'initialise avec la variable "slice" qui n'a rien à voir avec "max".

Code :

1
2
3
4
5
int limite = ceil(sqrt(max));
if(max > 10000)
slice = 10000;
else
slice = limite;

slice dépend de max

Le pourquoi du crash me dépasse par contre, que dit le debuger ?

[r0d]

Il me semble que la move semantic, déjà utilisée dans certaines implémentations de std::vector, permet de gagner du temps dans certains cas.

[ganon551]

Merci pour vos réponses.

J'ai déjà essayé de faire un simple vector<int> segment(slice), sans mettre de valeur d'initialisation, ça foire toujours.

Je compile sous MinGW, la dernière version en date.

Je précise, après avoir posté hier j'ai essayé de faire comme suit :

Code :

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
 
std::vector<int> segment(slice,1);
 
for(int y = limite; y <= max;y+=slice)
{
    if(y + slice + limite > max)
    {
        segment.resize(slice - limite);
    }
 
 
    for(int z = 0; z <= (int)segment.size(); z++)
    {
        if(z % 2 == 0)
        segment[z] = 0;
        else
        {
            segment[z] = z + y;
        }
    }
 
    for(int g = 3; g <= limite; g+=2)
    {
        if(tableau[g] == 0x1)
        {
            for(int h = 1;h <= (int)segment.size();h++)
            {
 
            if(segment[h] != 0)
            {
                if(segment[h] % g == 0)
                segment[h] = 0;
            }
 
 
            }
        }
    }
    for(int r = 1; r <= (int)segment.size();r++)
    {
        if(segment[r] != 0)
        {
            compteur2++;
 
        }
    }
 
}

J'ai donc fais un resize dans le cas où y + slice dépasserait la valeur de max. Maintenant le code marche, sauf quand max = 200.000 ou 1.000.000. Ce qui est relativement étrange

(EN ce qui concerne la relation entre max et slice, comme tu remarques, slice est toujours égal à 10.000 dans chacun de mes test, vu que max est toujours supérieur à 10.000).

Le debugger indique :

"Program received signal SIGTRAP, Trace/breakpoint trap.
In ntdll!TpWaitForAlpcCompletion () (C:\Windows\system32\ntdll.dll)".

Au fait, j'ai vu une source en C où le gars utilisait les fonctions malloc, memcpy, etc, pour allouer de façon dynamique la place nécessaire en mémoire. Est-ce plus rapide, ou simplement parcequ'il n'utilise pas le C++ ?

EDIT : Bon pour 2.000.000 le programme plante aussi, mais pas pour 3 ou plus.

EDIT 2 : Je remarque quelque chose, le programme plante, mais m'affiche le on nombre de premiers, ce qui veut dire qu'il plante après la boucle for principale, ce qui semble étrange.

EDIT 3 : Encore plus étrange ! Le programme plante à 39204, 198917, 996005, 4972901. Il y a un facteur 5 (à peu près, de 4.99 à 5.07) entre chacun de ces nombres. Théorie du complot ?

[Lintel-oo]

Parfois le comportement d'un programme peut sembler étrange lorsqu'on corrompt la mémoire

Tu essaies en effet de modifier l'accès à un emplacement non permis lorsque tu déclares :

Code :

1
2
3
4
5
for(int z = 0; z < slice; z++)
    {
        [...]
       segment[z] = 0;
    }

Essaie plutôt ainsi :

Code :

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
for(int y = limite; y <= max;y+=slice)
{
    for(int z = 0; z < slice; z++)
    {
        if(z % 2 == 0)
        segment[z] = 0;
        else
        {
            if(z+y < max)
            segment[z] = z + y;
            else
            segment[z] = 0;
        }
    }
 
    for(int g = 3; g <= limite; g+=2)
    {
        if(tableau[g] == 0x1)
        {
            for(int h = 1;h < slice;h++)
            {
 
            if(segment[h] != 0)
            {
                if(segment[h] % g == 0)
                segment[h] = 0;
            }
 
 
            }
        }
    }
    for(int r = 0; r < slice;r++)
    {
        if(segment[r] != 0)
        {
            compteur2++;
 
        }
    }
 
}

C'est à dire avec des inférieurs stricts dans les for. Tu peux également mettre des unsigned int à la place des int et faire de nombreuses petites optimisations mais je pense que tu t'en doute

PS :

Au fait, j'ai vu une source en C où le gars utilisait les fonctions malloc, memcpy, etc, pour allouer de façon dynamique la place nécessaire en mémoire. Est-ce plus rapide, ou simplement parce qu'il n'utilise pas le C++ ?

C'est pour le C n'utilise jamais ça en c++ ^^ même si c'est possible ce n'est vraiment pas recommandé

[ganon551]

Merci pour ta réponse

Finalement j'ai trouvé l'erreur, qui ne venait pas du tout du vector segment, bien que je ne comprenne pas pourquoi.

L'erreur était ici :

Code :

1
2
3
4
5
6
7
8
 
for(j = 3; j <= square; j+=2)
{
    for(k = j * j; k <= limite; k+= j)
    {
        tableau[k] = 0x0;
    }
}

Quand je dis k<= limite, il n'est pas content, il essaie d'accéder à une "case" du vecteur qui ne lui appartient pas. Du coup j'ai juste enlevé le <= pour mettre un <, et hop tout marche parfaitement

Par contre les performances sont très décevantes, je ne m'attendait pas à ça. Je trouve les premiers jusqu'à 10.000.000 en 5s500, c'est le temps qu'il me faut pour aller jusqu'à 1.000.000.000 avec mon autre implémentation sans la segmentation.

Je pensais que cette version serait "cache-friendly" puisqu'elle utilise un segment qui rentre dans le cache. Mais que je fasse slice = 128; ou slice = 4096 * 1024, ça marche pratiquement pareil, la version avec 128 marche même mieux.

C'est étrange

[Bousk]

Envoyé par ganon551

Merci pour ta réponse

Finalement j'ai trouvé l'erreur, qui ne venait pas du tout du vector segment, bien que je ne comprenne pas pourquoi.

L'erreur était ici :

Code :

Quand je dis k<= limite, il n'est pas content, il essaie d'accéder à une "case" du vecteur qui ne lui appartient pas. Du coup j'ai juste enlevé le <= pour mettre un <, et hop tout marche parfaitement

En C++, comme dans la majorité des langages, les index des tableaux sont 0-based et vont de 0 a taille exclus
Pour un tableau de nb éléments, on pourra accéder de tableau[0] à tableau[nb-1]