Comment puis-je faire fonctionner ce premier chercheur en parallèle?

Question

Je sais que la première découverte est bien étudiée, et il y a beaucoup de différentes implémentations. Ma question est, en utilisant la méthode fournie (exemple de code), comment puis-je faire pour briser le travail? La machine sur laquelle il fonctionnera aura 4 processeurs hyperthreadés quad core et 16Go de RAM. Je me rends compte qu'il y a quelques améliorations qui pourraient être faites, en particulier dans la méthode IsPrime. Je sais aussi que des problèmes surviendront lorsque la liste contient plus de int.MaxValue éléments. Je me fiche de toutes ces améliorations. La seule chose qui m'importe est de savoir comment casser le travail.

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace Prime 
{ 
    class Program 
    { 
     static List<ulong> primes = new List<ulong>() { 2 }; 

     static void Main(string[] args) 
     { 
      ulong reportValue = 10; 
      for (ulong possible = 3; possible <= ulong.MaxValue; possible += 2) 
      { 
       if (possible > reportValue) 
       { 
        Console.WriteLine(String.Format("\nThere are {0} primes less than {1}.", primes.Count, reportValue)); 

        try 
        { 
         checked 
         { 
          reportValue *= 10; 
         } 
        } 
        catch (OverflowException) 
        { 
         reportValue = ulong.MaxValue; 
        } 
       } 

       if (IsPrime(possible)) 
       { 
        primes.Add(possible); 
        Console.Write("\r" + possible); 
       } 
      } 

      Console.WriteLine(primes[primes.Count - 1]); 
      Console.ReadLine(); 
     } 

     static bool IsPrime(ulong value) 
     { 
      foreach (ulong prime in primes) 
      { 
       if (value % prime == 0) return false; 
       if (prime * prime > value) break; 
      } 

      return true; 
     } 
    } 
} 

Il y a 2 régimes de base que je vois: 1) à l'aide de toutes les discussions pour tester un seul numéro, ce qui est probablement idéal pour les nombres premiers plus élevés mais je ne peux pas vraiment penser à la façon de la mettre en œuvre, ou 2) en utilisant chaque fil pour tester un seul nombre premier possible, ce qui peut provoquer la découverte d'une chaîne non continue de nombres premiers et l'exécution de problèmes de ressources inutilisées lorsque le nombre suivant à tester est supérieur au carré du nombre premier le plus élevé trouvé.

Pour moi, il semble que ces deux situations sont difficiles seulement dans les premiers stades de la construction de la liste des nombres premiers, mais je ne suis pas entièrement sûr. Ceci est fait pour un exercice personnel de briser ce genre de travail.

Answer 1

Si vous le souhaitez, vous pouvez paralléliser les deux opérations: la vérification d'un nombre premier et la vérification de plusieurs nombres premiers à la fois. Bien que je ne sois pas sûr que cela aiderait. Pour être honnête, je considérerais supprimer le threading dans main().

J'ai essayé de rester fidèle à votre algorithme, mais pour l'accélérer, j'ai utilisé x * x au lieu de reportvalue; c'est quelque chose que vous pourriez facilement revenir si vous le souhaitez. Pour améliorer encore mon découpage de noyau, vous pouvez déterminer un algorithme pour déterminer le nombre de calculs requis pour effectuer les divisions en fonction de la taille des nombres et diviser la liste de cette façon. (Aka plus petit nombre prennent moins de temps à diviser par donc faire les premières partitions de plus)

aussi mon concept de threadpool peut ne pas exister la façon dont je veux l'utiliser

Voici mon aller à elle (pseudo-ish- Code):

List<int> primes = {2}; 
List<int> nextPrimes = {}; 
int cores = 4; 
main() 
{ 
    for (int x = 3; x < MAX; x=x*x){ 
    int localmax = x*x; 
    for(int y = x; y < localmax; y+=2){ 
     thread{primecheck(y);} 
    } 
    "wait for all threads to be executed" 
    primes.add(nextPrimes); 
    nextPrimes = {}; 
    } 
} 

void primecheck(int y) 
{ 
    bool primality; 
    threadpool? pool; 
    for(int x = 0; x < cores; x++){ 
    pool.add(thread{ 
     if (!smallcheck(x*primes.length/cores,(x+1)*primes.length/cores ,y)){ 
     primality = false; 
     pool.kill(); 
     } 
    }); 
    } 
    "wait for all threads to be executed or killed" 
    if (primality) 
    nextPrimes.add(y); 
} 

bool smallcheck(int a, int b, int y){ 
    foreach (int div in primes[a to b]) 
    if (y%div == 0) 
     return false; 
    return true; 
} 

E: J'ai ajouté ce que je pense que la mise en commun devrait ressembler, regardez la révision si vous voulez le voir sans.

Answer 2

Utilisez plutôt le tamis d'Ératosthène. Il ne vaut pas la peine de paralléliser, sauf si vous utilisez un bon algorithme en premier lieu.

Séparer l'espace pour tamiser dans de grandes régions et tamiser chacun dans son propre fil. Ou mieux utiliser un concept de file d'attente pour de grandes régions. Utilisez un tableau de bits pour représenter les nombres premiers, cela prend moins d'espace que de les représenter explicitement.

Voir aussi this answer pour une bonne implémentation d'un tamis (en Java, pas de division en régions).