Discussion :

[tomap3]

Salut

Je voudrais faire une application réparti sur deux ou plusieurs machines pour le calcule des nombres premiers. J'ai vu qu'il y avais l'algorithme de Crible d'Ératosthène: http://fr.wikipedia.org/wiki/Crible_...atosth%C3%A8ne
mais je ne vois pas comment l'appliquer pour un calcule distribué sur deux machines, vu qu'il n y pas de mémoire commune contenant le tableau.
Avez vous des idées sur comment faire svp ?
Merci d'avance.

Voici l'algorithme (code C) de crible d'Eratosthène en séquentiel (non distribué) :

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
void premiers(int tableau[], long tailleTableau)
{
   long i, j;
 
   tableau[0] = tableau[1] = 0;
   for (i = 2 ; i < tailleTableau ; i++)
      tableau[i] = 1;
 
   for (i = 2 ; i < sqrt(tailleTableau) ; i++)
      if (tableau[i])
         for (j = i*i ; j < tailleTableau ; j += i)
            tableau[j] = 0;
 
   /*Affichage :
   for (i = 0 ; i < tailleTableau ; i++)
      if (tableau[i]) printf ("%ld ", i);
   Fin Affichage */
}

EDIT:
Pour pouvoir répartir le calcule sur plusieurs processus (ce trouvant sur des machines différentes) j'ai pensé à considérer un processus maître qui envoi au autres processus esclaves leur intervalles de calcule (la suite de nombres sur lesquels le processus exécutera l'algorithme) et ce processus maître a lui aussi son intervalle de calcule.

Mais même comme ça ce n'est évident car l'algorithme de calcule des nombres premiers que va effectué un processus P1 sur le 1er intervalle de nombres va avoir un impacte sur le reste des nombres (voir l'algorithme de Crible d'Ératosthène) et donc les calcules du processus P2 par exemple pourront être fausse car peut être P1 a éliminé un nombre (non premier) appartenant à l'intervalle de calcule de P2 mais P2 va quand même effectué le calcule sur ce nombre car il n'as pas été informé par P1.

Vous pouvez peut être me dire dans ce cas de faire en sorte qu'à chaque fois qu'un processus élimine un nombre (non premier), il envoi un message au autres processus (ou au processus concerné) afin les informé que ce nombre est non premier pour qu'ils ne le traitent pas. Mais le problème dans ce cas serai: si le processus P2 (par exemple) a déjà traité le nombre en question avant qu'il ne reçoi le message provenant de P1 lui disant de ne pas le traiter (car non premier).

Des idées pour régler ces problèmes svp ?

[Zavonen]

Eratosthene, me parait difficilement parallélisable.
Atkin par contre (voir wiki) ou mon cours:
Nombres-->naturels-->exercices-->>programmation -->atkin
l'est sans doute (voir les 3 if successifs dans la solution python).
http://perso.univ-rennes1.fr/antoine...51_088_096.pdf

[lakkarin]

Bonjour,

Si je participe à ce forum, c'est seulement pour attirer l'attention aux developpeurs que vous êtes, que j'ai vu qu'il y a un Crible sur un autre forum qui s'appelle " CRIBLE DE LACHKAR" sur le forum de Bibm@th / nombres.
Peut être que crible est rapide que celui d'Eratosthene.
Il faut l'essayer pour juger.

Salut

[alex_pi]

Bonjour,

Si je participe à ce forum, c'est seulement pour attirer l'attention aux developpeurs que vous êtes, que j'ai vu qu'il y a un Crible sur un autre forum qui s'appelle " CRIBLE DE LACHKAR" sur le forum de Bibm@th / nombres.
Peut être que crible est rapide que celui d'Eratosthene.
Il faut l'essayer pour juger.

Salut

C'est bien de se balader de forum en forum pour faire la pub pour un crible inexistant, mais ce serait peut être un peu mieux de le décrire sérieusement, d'en proposer une implémentation et de montrer en quoi il est plus efficace que celui d'Eratosthène hein...

[lakkarin]

C'est bien de se balader de forum en forum pour faire la pub pour un crible inexistant, mais ce serait peut être un peu mieux de le décrire sérieusement, d'en proposer une implémentation et de montrer en quoi il est plus efficace que celui d'Eratosthène hein...

Bonjour,

Si je me balade d'un forum à l'autre, c'est pour rester toujours en contact avec du nouveau.
En ce qui concerne Le Crible de Lachkar, d'après ce que j'ai vu sur le Forum de Bibmath, il s'agit bien d'un Crible qui se compose de 5 colonnes et N-1 lignes.

Il se présente comme di-dessous :


1 2 3 4 5
0 1 3 5 7 9
1 6 8 10 12 14
2 11 13 15 17 19
3 16 18 20 22 24
4 21 23 25 27 29
5 26 28 30 32 34


Donc on peut facilement commencer par l'élimination de certaines colones, lignes en les barrant horizontalement, verticalement ou diagonalement .

la colonne 3 c'est les multiples de5
les lignes impaires sont les nombres impairs,
les multiples de 3 sont les diagonales de droites vers la gauches,
les multiples de 7 sont les diagonales de gauches vers la droite..

Donc, on procèdant de cette façon, il nous ne reste que les nombres premiers.

Sur le Forum en question, ils ont commencer à faire des essais de programmations.

Salut

[alex_pi]

En ce qui concerne Le Crible de Lachkar, d'après ce que j'ai vu sur le Forum de Bibmath, il s'agit bien d'un Crible qui se compose de 5 colonnes et N-1 lignes.

Il se présente comme di-dessous :

Code :

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

1
2
3
4
5
6
7
8
 
	1	2 	3	4	5
0	1	3 	5	7	9
1	6	8	10	12	14
2	11	13	15	17	19
3	16	18	20	22	24
4	21	23	25	27	29
5	26	28	30	32	34

Donc on peut facilement commencer par l'élimination de certaines colones, lignes en les barrant horizontalement, verticalement ou diagonalement .

la colonne 3 c'est les multiples de5
les lignes impaires sont les nombres impairs,
les multiples de 3 sont les diagonales de droites vers la gauches,
les multiples de 7 sont les diagonales de gauches vers la droite..

C'est incompréhensible là ton explication... Et puis bon, s'appuyer sur une représentation graphique, c'est peut être bien à la main, mais pour le programmer, ça ne sert à rien... Parcourir une diagonale pour supprimer les multiple de 7, ça n'a aucune chance d'être plus rapide que de faire une boucle en incrémentant l'indice de 7 à chaque fois. Sans compter le temps passé à construire le tableau initialement alors que pour le crible d'Eratosthène c'est trivial.

Et puis bon, j'attends avec angoisse la représentation graphique des multiples de 163...

Et accessoirement, tu n'as pas 2 et 4 dans ton tableau. Autant le second, ce n'est pas bien grave, autant le premier, pour récupérer tous les nombres premiers sans qu'il soit là, c'est un peu mal barré...

Bref, c'est mal barré ton "crible de Lachkar"

[lakkarin]

bonjour,

D'apres ce que j'ai vu sur le forum, il applique une formule pour remplir son tableau.
La formule est N = ( P + k ) x 5 ( dans laquelle P désigne la position en ligne de nombre N et k est une constante pour chaque colonne )

Colonne 1 k = 0.2
Colonne 2 k = 0.6
colonne 3 k = 1.0
Colonne 4 k = 1.4
Colonne 5 k = 1.8

donc à la position P = 0 on a N
C1 N = 1
C2 N = 3
C3 N = 5
C4 N = 7
C5 N = 9

0 la position P = 1 on a

C1 N = ( 1+0.2)x5 = 6
C2 N = ( 1+0.2)x5 = 8


......

à la position P=11 on a

C1 N = (11+0.2)x5 = 56

......


Pour 163 on peut la déduire de la formule 163/5 = 32.6 donc il se trouve à la position P=32 et en colonne de k= 0.6 ( colonne 2)


pour touver les multiple de d'un nombre N ,il suffit de choisir N et lui ajouter le numéro d e serie en ligne de P.

Par exemple 11 se touve à P=2 , donc les multiples de 11 sur la colonne 1 se trouve à la position :

11 +2 = 13 qui est 66 car (13+0.2 )x5 = 66

11 + 13 donne 24 et ( 24+0.2)x5 = 121

11+24 donne N = 176

Etc


pour 163 qui se trouve à la position 32 en colonne 2 comme vu en haut donc le prochain sera à la position
P = 32+163 = 195 d'ou N= ( 195+0.6)x5= 978 = 163 x 6
le prochain sera 163 + 195 = 359 d'ou N= 358.6 x 5 = 1793 = 163x11

Idem pour tous les autres multiples et pour les autres colonnes

Salut

[alex_pi]

Ah ouais, je confirme, c'est imbitable...

Et euh, ça doit apporter quoi par rapport au truc tout con d'Eratosthène ?

[lakkarin]

Bonjour

Bah, je pense , si vous êtes fort en programmation, alors essaie de le faire pour voir ce qu'il va t'apporter !!

Salut

[alex_pi]

Bah, je pense , si vous êtes fort en programmation, alors essaie de le faire pour voir ce qu'il va t'apporter !!

Ou alors on est suffisamment fort en programmation pour le regarder dans le blanc des yeux et se rendre compte qu'il n'apporte rien du tout.

Bref...

[lakkarin]

Salut

on ne peut pas juger quelque chose avant de l'essayer §
Tout d'abord il faut établir le tableau qui compose ce crible, et le bien étudier et voir ce qu'on peut tirer.
Même si on coit qu'on peut être assez fort, il faut d'abord faire se qui est faisable.
Car comme vous dite " con d'Eratosthene" il faut pas oublier que grasse à lui qu'on n'a pu dresser des listes pour les nombres premiers

Salut

[alex_pi]

[QUOTE=lakkarin;4403778]
on ne peut pas juger quelque chose avant de l'essayer §
{/QUOTE]
Justement si, ce qui est bien avec l'algorithmique, c'est qu'on peut (parfois, souvent ?) se faire un avis sans coder et faire tourner des benchmark..

Tout d'abord il faut établir le tableau qui compose ce crible, et le bien étudier et voir ce qu'on peut tirer.

Justement, rien que le temps "d'établir le tableau", je pense que le crible d'Eratosthène est déjà terminé...

Car comme vous dite " con d'Eratosthene" il faut pas oublier que grasse à lui qu'on n'a pu dresser des listes pour les nombres premiers

Ce que je dis c'est que son algo est tout con, pas lui... Et tout con dans le sens de très simple, pas de mauvais, au contraire !

[lakkarin]

salut,

c'est vrai que le temps pour le tableau , le crible d'Eratosthene sera déjà, c'est tout à fait normal, ce crible existe depuis des siècle et tout est déjà établi!

par contre celui de Lachkar une fois on connait la proédure , tout devient facile

on part de 1 ; 3 , 5 , 7 ;9 c'est une raison de 2
et pour 1 ; 6 ; 11 ; 16 ... c'est une raison de 5

c'est simple.

vous voulez pas qu'on change un peu ( des siècles et des siècles avec un seul crible!!!)

Tvouvez une astuce , ça sera une innovation

salut

[Mac LAK]

c'est vrai que le temps pour le tableau , le crible d'Eratosthene sera déjà, c'est tout à fait normal, ce crible existe depuis des siècle et tout est déjà établi!

Je n'ai toujours pas trouvé la fonction "Crible d'Erathosthène" dans la CLib, ni dans le framework Java / .NET, encore moins dans la VCL Delphi... "Tout est déjà établi", tu dis ??

vous voulez pas qu'on change un peu ( des siècles et des siècles avec un seul crible!!!)

Ça fait des siècles qu'on utilise la même addition d'entiers, c'est pas une preuve qu'elle est mauvaise.

Le crible est un algo "basique", très simple et efficace, qui est totalement inadapté à la recherche des GRANDS nombres premiers de par sa consommation mémoire proprement colossale et sa complexité exponentielle... Et vu comment marche ton crible "nouvelle version", c'est probablement la même chose.

Je te rappelle quand même que le plus grand nombre premier connu est (2^43 112 609)-1, et avant que tu n'aie un ordinateur capable de maintenir en mémoire le crible pour le trouver, il va s'écouler un bon paquet de temps !! Tu pourras d'ailleurs aller lire la page Wikipédia sur le sujet.

Le Crible, c'est juste un algo classique demandé à la plupart des étudiants, au même titre que le tri à bulles et la n-ième gestion de liste chaînée. Vouloir l'utiliser pour la recherche réelle de nombres premiers (sous-entendu, les GRANDS nombres premiers), c'est juste ne pas avoir compris ni l'algo du Crible, ni ses contraintes d'implémentation, ni même ce qu'est un "grand nombre"...



Pour l'OP : Comme ça, "à chaud", je ne vois aucune manière de pouvoir distribuer le Crible sur plusieurs machines sans avoir de mémoire partagée... Sur plusieurs cœurs de CPU, aucun problème (à la mémoire requise près bien sûr), mais sur deux machines distinctes reliées par réseau, tu vas te retrouver avec des contraintes d'atomicité des opérations qui vont être bien plus coûteuses que le temps gagné par parallélisation.

[lakkarin]

salut

TOUT le monde connait le nombre de Mersene !!!

Seulement pour déterminer un nombre premier , il faut se couper la tête.

faire bouger vos méninges et trouver autres choses . Moi, je suis sûre et j'ai la conviction qu'il y a un truc quelque part, mais pas avec des formules .

salut

[alex_pi]

faire bouger vos méninges et trouver autres choses . Moi, je suis sûre et j'ai la conviction qu'il y a un truc quelque part, mais pas avec des formules .

Par incantation chamanistique ou en lisant le marc de café ?

Tu serais sans doute pris un peu plus au sérieux si tu nous montrais l'algorithme derrière ton crible, en l'écrivant en pseudo-code plutôt qu'en secouant les mains, en montrant trois lignes du tableau et en expliquant qu'il faut rayer les diagonales pour 7... En plus le pseudo-code permettrait de passer la barrière de la langue dont ta maitrise assez approximative ne nous facilite pas les choses.

[Mac LAK]

Seulement pour déterminer un nombre premier , il faut se couper la tête.

Tu crois que ça s'appelle un GRAND NOMBRE pour quelle raison ???

faire bouger vos méninges et trouver autres choses .

Tu vas te calmer : d'une part, nous ne sommes pas tes chiens, c'est pas le forum de recherche mathématique fondamentale sur les nombres premiers ici.

Nous ne TE devons rien, et encore moins quand c'est demandé de cette façon.

Moi, je suis sûre et j'ai la conviction qu'il y a un truc quelque part, mais pas avec des formules .

Et lakkarin nous inventa les maths sans formules...

Sérieux, et je dis ça sans méchanceté aucune, t'as dépassé le niveau Bac en maths ? T'as déjà effleuré des mathématiques supérieures ? Ou tu dis juste des bêtises en croyant avoir l'idée du siècle que des milliers de mathématiciens autrement plus intelligents que toi (ou moi) n'ont "jamais eue" ?

[lakkarin]

Bonjour,

Tout d'abord je suis très désolé si j'ai mal exprimé et normalement ce n'est dans mes habitudes.
Je vous demande de m'excuser

Mon but ce n'est pas d'être incorrecte envers des personnes que je connais même .

Pardon.

J'espère que vous continuer à proposer vos idées.

Merci

Salut

[lakkarin]

Tu crois que ça s'appelle un GRAND NOMBRE pour quelle raison ???

Tu vas te calmer : d'une part, nous ne sommes pas tes chiens, c'est pas le forum de recherche mathématique fondamentale sur les nombres premiers ici.

Nous ne TE devons rien, et encore moins quand c'est demandé de cette façon.


Et lakkarin nous inventa les maths sans formules...

Sérieux, et je dis ça sans méchanceté aucune, t'as dépassé le niveau Bac en maths ? T'as déjà effleuré des mathématiques supérieures ? Ou tu dis juste des bêtises en croyant avoir l'idée du siècle que des milliers de mathématiciens autrement plus intelligents que toi (ou moi) n'ont "jamais eue" ?

Bonjour, Mac LAK

je vois que tu es toujours fâché conte moi,
Il ne faut pas le prendre comme ça.
Vous êtes des être humain et tout humain doit être respecté.
Je n'ai jamais pretendu être plus fort qu'autrui , car j'apprends et j'apprends toujours.
Quelqu'un de fort ne doit jamais se vexer , mais il doit monter ses qualités.

Salut

[Mac LAK]

je vois que tu es toujours fâché conte moi,

Non, juste que le topic est "mort", ni plus, ni moins... Un crible est difficilement distribuable (à la limite, sur plusieurs cœurs, et encore, mais pas sur plusieurs machines), et de toutes façons ce n'est pas très efficace pour la recherche des nombres premiers dès qu'on "grimpe" un peu dans les chiffres... Cela prend surtout une place colossale en mémoire, en fait, même en se contentant d'un seul bit par nombre...

Le seul avantage d'un crible, c'est qu'il garantit que l'on n'a oublié AUCUN nombre premier une fois arrivé à la fin du crible (= sa taille de départ). Mais si je te demande de tester si ((2^50)-1) est premier, et c'est encore un "petit" nombre, je te garantit qu'un crible ne sera pas la façon la plus efficace de procéder...