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.

[pascalCH]

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 !!!

[Invité]

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