multithread pour calcul nombre premier.

Version imprimable

Bonjour,

J'ai fais une fonction permettant de savoir si un nombre est premier ou non. Comme je calcul des très grand nombre je voudrais trouver un moyen de calculer plus rapidement.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 static bool isprem(BigInteger a) { BigInteger b ; if(a%2==0) return false; for(b=3;b*b<=a;b=b+2) { if(a%b==0) return false ; } return true ; }
Je voudrais savoir si en utilisant les threads il serait possible d'améliorer les performances de ma fonction, par exemple en fesant traiter la moitié des calculs par un thread et l'autre moitié par un autre ?

Merci.

PS : Je n'ai jamais utilisé de thread.

03/05/2014, 15h42
PatteDePoule

Tout à fait! C'est vraiment un bon chemin à prendre.

Tu peux même en lancer plus que 2. Il faut faire des tests de performance pour trouver le nombre optimal.

Pour commencer regarde dans la FAQ, ça va te permettre de bien démarrer.

Bonjour. Si ton but est vraiment la vitesse, alors c'est d'abord l'algorithme qu'il faut changer, par exemple pour ECPP ou AKS si tu as besoin d'un algorithme déterministe.

Cela étant dit, voici comment on pourrait le paralléliser :

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
static volatile bool MayBePrime;
static readonly object NextDividerLock = new object();
static BigInteger NextDivider;
const int NextDividerIncrement = 32;
 
public static bool IsPrime(BigInteger a)
{
            if(a%2==0) return false;
 
            NextDivider= 3;
            MayBePrime= true;
            RunPrimalityTestingTasks(a);
            return MayBePrime;
}
 
static void RunPrimalityTestingTasks(BigInteger a)
{
            int cores = Environment.ProcessorCount;
            Task[] tasks = new Task[cores];
            for (int i = 0; i < cores; ++i) tasks[i] = Task.Run(() => PrimalityTestingWorker(a));
            Task.WaitAll(tasks);
}
 
static void PrimalityTestingWorker(BigInteger a)
{
     while(MayBePrime)
     {
           BigInteger start, exclusiveEnd;
           GetDividerRange(out start, out exclusiveEnd);
 
           for (b = start; b < exclusiveEnd; b += 2);
           {
                if (b * b >= a) return;
                if (a % b == 0) 
                {
                      MayBePrime = false;
                      return;
                 }
           }
     }
}
 
static void GetDividerRange(out BigInteger start, out BigInteger exclusiveEnd)
{
      lock(NextDividerLock)
      {
           start = NextDivider;
           end = start + NextDividerIncrement 
           NextDivider = exclusiveEnd;
      }
}

Code non-testé.

04/05/2014, 14h21
fred61

Merci pour vos réponses, DonQuiche je vais essayer de comprendre ton code et le tester.
04/05/2014, 21h39
Graffito

Dans le cas de pur calculs, le nombre optimum de threads correspond au nombre de coeurs (x2 en cas de multi-threading) :

Code:

int NbThreads = Environment.ProcessorCount ;
06/05/2014, 16h01
fred61

Juste pour information, j'ai réécris mon code en utilisant le multithread sur un processeur multicoeur et effectivement la vitesse d'exécution est multipliée par le nombre de threads utilisés.
Merci pour votre aide et vos informations.
07/05/2014, 15h45
pascalCH

Nombre premier

Hello,

juste histoire de faire un peu d’algorithmie,

1. un nombre est premier si il n'est divisible que par 1 et lui-même
2. il suffit de tester les divisions successives de 2 à (N/2)+1
3. dans les divisions successives, si on en dispose, il suffit de tester sur les nombres premiers inférieurs ou égaux à (N/2) + 1
4. un nombre premier supérieur à 3 vaut toujours ( Y * 6 ) +/- 1

ça parait pas comme ça, mais introduire le point 4 permet de diviser par 2 le nombre de tests à réaliser....

à vos claviers !!!
18/05/2014, 11h20
Invité

nombres entiers ?

Bonjour

Il se trouve que les nombres entiers sont organisés.

En divisant un nombre par 6, on obtient la nature du nombre : PAIR-IMPAIR-PREMIER...
Avec le module "nombre % 6", on a la même chose, à savoir :
a) 1%6 = 1 b)2%6 = 2 ... f) 6%6 = 0
Donc, la définition "hexa" du nombre multiple donne les rangs : 2,3,4,6. Ces derniers ne sont pas composés de nombre premier !
Pour trouver les nombres premiers, il faut voir comme résultat (n%6) : 1,5. Et mieux comprendre en faisant des tests, afin de s'assurer des résultats obtenus. Ce phénomène calcule tous les nombres entiers.

Pour terminer, on a une série infinie de nombres entiers à valeurs ajoutées (PAIR...). L'opération hexa transforme le nombre en un résultat original, il est à noter que jusqu'à présent le modèle (n%6) ne s'est jamais trompé. Ce modèle dessine deux rangs distincts sur lesquels sont situés les premiers multiples. Ce qui fait, que le programme ne calcule que 2/6 de comparaisons. Puisque les rangs(2,3,4,6) sont de type (PAIR, IMPAIR)...

Savoir aussi, qu'au début de cette chronologie des nombres entiers. Lorsqu'on commence le compte à partir de 1, on est sûr de trouver des premiers multiples.

Ceci est la partie élémentaire des nombres entiers, sans entrer dans cette fourmilière...