Discussion :

[fred61]

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 :

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

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.

[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.

[DonQuiche]

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 c# :

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
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é.

[fred61]

Merci pour vos réponses, DonQuiche je vais essayer de comprendre ton code et le tester.

[Graffito]

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

Code :

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

int NbThreads = Environment.ProcessorCount ;

[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.