Le moyen le plus rapide de calculer des nombres premiers en C# ?

Question

J'ai en fait une réponse à ma question mais elle n'est pas parallélisée donc je suis intéressé par les moyens d'améliorer l'algorithme.Quoi qu'il en soit, cela pourrait être utile tel quel pour certaines personnes.

int Until = 20000000;
BitArray PrimeBits = new BitArray(Until, true);

/*
 * Sieve of Eratosthenes
 * PrimeBits is a simple BitArray where all bit is an integer
 * and we mark composite numbers as false
 */

PrimeBits.Set(0, false); // You don't actually need this, just
PrimeBits.Set(1, false); // remindig you that 2 is the smallest prime

for (int P = 2; P < (int)Math.Sqrt(Until) + 1; P++)
    if (PrimeBits.Get(P))
        // These are going to be the multiples of P if it is a prime
        for (int PMultiply = P * 2; PMultiply < Until; PMultiply += P)
            PrimeBits.Set(PMultiply, false);

// We use this to store the actual prime numbers
List<int> Primes = new List<int>();

for (int i = 2; i < Until; i++)
    if (PrimeBits.Get(i))
        Primes.Add(i);

Peut-être que je pourrais en utiliser plusieurs BitArraysable BitArray.Et() eux autres ensemble?

Answer 1

Vous pourriez gagner du temps en croisant votre tableau de bits avec une liste à double lien, afin de pouvoir passer plus rapidement au nombre premier suivant.

De plus, en éliminant les composites ultérieurs une fois que vous avez atteint un nouveau p premier pour la première fois, le premier multiple composite de p restant sera p*p, puisque tout ce qui précède a déjà été éliminé.En fait, il vous suffit de multiplier p par tous les nombres premiers potentiels restants qui restent après lui dans la liste, en vous arrêtant dès que votre produit est hors de portée (supérieur à Jusqu'à).

Il existe également de bons algorithmes probabilistes, comme le test de Miller-Rabin. La page Wikipédia est une bonne introduction.

Answer 2

Parallélisation mise à part, vous ne voulez pas calculer sqrt(Until) à chaque itération.Vous pouvez également supposer des multiples de 2, 3 et 5 et calculer uniquement pour N%6 dans {1,5} ou N%30 dans {1,7,11,13,17,19,23,29}.

Vous devriez pouvoir paralléliser l'algorithme de factorisation assez facilement, puisque la Nième étape ne dépend que du sqrt(n)ième résultat, donc après un certain temps, il n'y aura plus de conflits.Mais ce n’est pas un bon algorithme, car il nécessite beaucoup de divisions.

Vous devriez également être en mesure de paralléliser les algorithmes de tamisage, si vous disposez de paquets de travail d'écriture dont la fin est garantie avant une lecture.La plupart du temps, les rédacteurs ne devraient pas entrer en conflit avec le lecteur - au moins une fois que vous avez effectué quelques entrées, ils devraient travailler au moins N au-dessus du lecteur, vous n'avez donc besoin d'une lecture synchronisée qu'assez occasionnellement (lorsque N dépasse la dernière lecture synchronisée). valeur).Vous ne devriez pas avoir besoin de synchroniser le tableau bool sur un nombre quelconque de threads d'écriture, car les conflits d'écriture ne surviennent pas (au pire, plusieurs threads écriront un true au même endroit).

Le principal problème serait de s'assurer que tout travailleur attendu pour écrire a terminé.En C++, vous utiliseriez une comparaison et un ensemble pour passer au travailleur attendu à tout moment.Je ne suis pas un passionné de C#, donc je ne sais pas comment le faire dans ce langage, mais la fonction Win32 InterlockedCompareExchange devrait être disponible.

Vous pouvez également essayer une approche basée sur les acteurs, car vous pouvez ainsi planifier les acteurs travaillant avec les valeurs les plus basses, ce qui peut être plus facile de garantir que vous lisez des parties valides du tamis sans avoir à verrouiller le bus à chaque incrément de N.

Quoi qu'il en soit, vous devez vous assurer que tous les travailleurs ont dépassé l'entrée N avant de la lire, et le coût de cela est là où se fait le compromis entre parallèle et série.

Answer 3

Sans profilage, nous ne pouvons pas déterminer quelle partie du programme doit être optimisée.

Si vous étiez dans un grand système, vous utiliseriez un profileur pour constater que le générateur de nombres premiers est la partie à optimiser.

Profiler une boucle contenant une douzaine d'instructions ne vaut généralement pas la peine - la surcharge du profileur est importante par rapport au corps de la boucle, et la seule manière d'améliorer une boucle aussi petite est de modifier l'algorithme pour faire moins d'itérations. .Donc IME, une fois que vous avez éliminé toutes les fonctions coûteuses et que vous avez une cible connue de quelques lignes de code simple, il est préférable de changer l'algorithme et de chronométrer une exécution de bout en bout plutôt que d'essayer d'améliorer le code par niveau d'instruction. profilage.

Answer 4

Le profilage @DrPizza ne fait qu'améliorer une implémentation, il ne révèle pas d'opportunités d'exécution parallèle ni ne suggère de meilleurs algorithmes (sauf si vous avez l'expérience du contraire, auquel cas j'aimerais vraiment voir votre profileur).

Je n'ai que des machines monocœur à la maison, mais j'ai exécuté un équivalent Java de votre tamis BitArray et une version à thread unique de l'inversion du tamis - contenant les nombres premiers de marquage dans un tableau et utilisant un roue pour réduire l'espace de recherche d'un facteur cinq, puis marquer un tableau de bits par incréments de la roue en utilisant chaque nombre premier de marquage.Cela réduit également le stockage à O(sqrt(N)) au lieu de O(N), ce qui aide à la fois en termes de N, de pagination et de bande passante plus grande.

Pour des valeurs moyennes de N (1e8 à 1e12), les nombres premiers jusqu'à sqrt(N) peuvent être trouvés assez rapidement, et après cela vous devriez pouvoir paralléliser la recherche ultérieure sur le CPU assez facilement.Sur ma machine monocœur, l'approche par roue trouve des nombres premiers jusqu'à 1e9 en 28 s, alors que votre tamis (après avoir sorti le sqrt de la boucle) prend 86 s - l'amélioration est due à la roue ;l'inversion signifie que vous pouvez gérer N supérieur à 2 ^ 32 mais le rend plus lent.Le code peut être trouvé ici.Vous pouvez également paralléliser la sortie des résultats du tamis naïf après avoir dépassé sqrt(N), car le tableau de bits n'est pas modifié après ce point ;mais une fois que vous avez affaire à N suffisamment grand pour que cela compte, la taille du tableau est trop grande pour les entiers.

Answer 5

Vous devriez également envisager un éventuel changement de algorithmes.

Considérez qu'il peut être moins coûteux d'ajouter simplement les éléments à votre liste, au fur et à mesure que vous les trouvez.

Peut-être que préallouer de l'espace pour votre liste rendra la création/le remplissage moins coûteux.

Answer 6

Essayez-vous de trouver de nouveaux nombres premiers ?Cela peut paraître stupide, mais vous pourrez peut-être charger une sorte de structure de données avec des nombres premiers connus.Je suis sûr que quelqu'un a une liste.Il pourrait être beaucoup plus simple de trouver des nombres existants qui en calculent de nouveaux.

Vous pouvez également consulter Microsofts Bibliothèque d'effets parallèles pour rendre votre code existant multithread afin de tirer parti des systèmes multicœurs.Avec un minimum de modifications de code, vous pouvez créer des boucles multithread.

Answer 7

Il y a un très bon article sur le Tamis d'Eratosthène : Le véritable tamis d’Ératosthène

C'est dans un cadre fonctionnel, mais la plupart des optimisations s'appliquent également à une implémentation procédurale en C#.

Les deux optimisations les plus importantes sont de commencer à barrer à P^2 au lieu de 2*P et d'utiliser une roue pour les nombres premiers suivants.

Pour la simultanéité, vous pouvez traiter tous les nombres jusqu'à P^2 en parallèle à P sans effectuer de travail inutile.

Answer 8

    void PrimeNumber(long number)
    {
        bool IsprimeNumber = true;
        long  value = Convert.ToInt32(Math.Sqrt(number));
        if (number % 2 == 0)
        {
            IsprimeNumber = false;
            MessageBox.Show("No It is not a Prime NUmber");
            return;
        }
        for (long i = 3; i <= value; i=i+2)
        {             
           if (number % i == 0)
            {

                MessageBox.Show("It is divisible by" + i);
                IsprimeNumber = false;
                break;
            }

        }
        if (IsprimeNumber)
        {
            MessageBox.Show("Yes Prime NUmber");
        }
        else
        {
            MessageBox.Show("No It is not a Prime NUmber");
        }
    }