Il modo più veloce per calcolare i numeri primi in C#?

Question

In realtà ho una risposta alla mia domanda ma non è parallelizzata, quindi sono interessato a come migliorare l'algoritmo.Ad ogni modo potrebbe essere utile così com'è per alcune persone.

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);

Forse potrei usarne più di uno BitArraysabbia BitArray.And() loro insieme?

Answer 1

Potresti risparmiare tempo incrociando il tuo array di bit con un elenco doppiamente collegato, in modo da poter avanzare più rapidamente al numero primo successivo.

Inoltre, eliminando i compositi successivi una volta raggiunto un nuovo numero primo p per la prima volta, il primo multiplo composito di p rimanente sarà p*p, poiché tutto ciò che lo precede è già stato eliminato.Infatti, devi solo moltiplicare p per tutti i potenziali numeri primi rimasti dopo di esso nell'elenco, fermandoti non appena il tuo prodotto è fuori intervallo (maggiore di Until).

Esistono anche alcuni buoni algoritmi probabilistici, come il test di Miller-Rabin. La pagina di Wikipedia è una buona introduzione.

Answer 2

Parallelizzazione a parte, non vuoi calcolare sqrt(Until) ad ogni iterazione.Puoi anche assumere multipli di 2, 3 e 5 e calcolare solo per N%6 in {1,5} o N%30 in {1,7,11,13,17,19,23,29}.

Dovresti essere in grado di parallelizzare l'algoritmo di fattorizzazione abbastanza facilmente, poiché l'ennesima fase dipende solo dal risultato sqrt(n)esimo, quindi dopo un po' non ci saranno conflitti.Ma non è un buon algoritmo, poiché richiede molte divisioni.

Dovresti anche essere in grado di parallelizzare gli algoritmi di setaccio, se hai pacchetti di lavoro di scrittura che sono garantiti per essere completati prima di una lettura.Per lo più gli autori non dovrebbero entrare in conflitto con il lettore - almeno una volta che hai inserito alcune voci, dovrebbero lavorare almeno N sopra il lettore, quindi hai bisogno di una lettura sincronizzata solo occasionalmente (quando N supera l'ultima lettura sincronizzata valore).Non dovrebbe essere necessario sincronizzare l'array bool su un numero qualsiasi di thread di scrittura, poiché non si verificano conflitti di scrittura (nel peggiore dei casi, più di un thread scriveranno un true nello stesso posto).

Il problema principale sarebbe garantire che ogni lavoratore atteso per scrivere abbia completato.In C++ utilizzeresti un confronto e imposta per passare al lavoratore che è atteso in qualsiasi momento.Non sono un esperto di C#, quindi non so come farlo in quel linguaggio, ma la funzione Win32 InterlockedCompareExchange dovrebbe essere disponibile.

Potresti anche provare un approccio basato sugli attori, poiché in questo modo puoi programmare gli attori che lavorano con i valori più bassi, il che potrebbe essere più semplice per garantire che stai leggendo parti valide del setaccio senza dover bloccare il bus su ogni incremento di N.

In ogni caso, devi assicurarti che tutti i lavoratori abbiano superato la voce N prima di leggerla, e il costo per farlo è il punto in cui viene effettuato il compromesso tra parallelo e seriale.

Answer 3

Senza profilazione non possiamo dire quale parte del programma necessita di ottimizzazione.

Se ci si trovasse in un sistema di grandi dimensioni, si utilizzerebbe un profiler per scoprire che il generatore di numeri primi è la parte che necessita di ottimizzazione.

Di solito non vale la pena profilare un ciclo con una dozzina circa di istruzioni: il sovraccarico del profiler è significativo rispetto al corpo del ciclo e l'unico modo per migliorare un ciclo così piccolo è modificare l'algoritmo per eseguire meno iterazioni .Quindi IME, una volta che hai eliminato eventuali funzioni costose e hai un obiettivo noto di poche righe di codice semplice, è meglio cambiare l'algoritmo e cronometrare un'esecuzione end-to-end piuttosto che provare a migliorare il codice in base al livello di istruzione profilazione.

Answer 4

@DrPizza Profiling aiuta davvero solo a migliorare un'implementazione, non rivela opportunità per l'esecuzione parallela né suggerisce algoritmi migliori (a meno che tu non abbia esperienza altrimenti, nel qual caso mi piacerebbe davvero vedere il tuo profiler).

A casa ho solo macchine single core, ma ho eseguito un equivalente Java del tuo setaccio BitArray e una versione a thread singolo dell'inversione del setaccio, mantenendo i numeri primi di marcatura in un array e utilizzando un ruota per ridurre lo spazio di ricerca di un fattore cinque, quindi contrassegnando una serie di bit con incrementi della ruota utilizzando ciascun numero primo di marcatura.Riduce inoltre lo spazio di archiviazione a O(sqrt(N)) anziché a O(N), il che aiuta sia in termini di N maggiore, paginazione e larghezza di banda.

Per valori medi di N (da 1e8 a 1e12), i numeri primi fino a sqrt(N) possono essere trovati abbastanza rapidamente, dopodiché dovresti essere in grado di parallelizzare abbastanza facilmente la ricerca successiva sulla CPU.Sulla mia macchina single core, l'approccio con ruota trova numeri primi fino a 1e9 in 28 secondi, mentre il tuo setaccio (dopo aver spostato sqrt fuori dal ciclo) impiega 86 secondi: il miglioramento è dovuto alla ruota;l'inversione significa che puoi gestire N maggiore di 2 ^ 32 ma lo rende più lento.È possibile trovare il codice Qui.Potresti parallelizzare l'output dei risultati dal sieve ingenuo anche dopo aver superato sqrt(N), poiché l'array di bit non viene modificato dopo quel punto;ma una volta che hai a che fare con N abbastanza grande da essere importante, la dimensione dell'array è troppo grande per gli int.

Answer 5

Dovresti anche considerare un possibile cambio di algoritmi.

Considera che potrebbe essere più economico aggiungere semplicemente gli elementi alla tua lista, man mano che li trovi.

Forse preallocare spazio per la tua lista renderà più economico costruire/popolare.

Answer 6

Stai cercando di trovare nuovi numeri primi?Potrebbe sembrare stupido, ma potresti essere in grado di caricare una sorta di struttura dati con numeri primi conosciuti.Sono sicuro che qualcuno là fuori abbia una lista.Potrebbe essere un problema molto più semplice trovare numeri esistenti che ne calcolino di nuovi.

Potresti anche guardare Microsofts Libreria di effetti paralleli per rendere il codice esistente multi-thread per sfruttare i sistemi multi-core.Con modifiche minime al codice puoi creare loop multi-thread.

Answer 7

C'è un ottimo articolo sul Setaccio di Eratostene: Il vero setaccio di Eratostene

È in un ambiente funzionale, ma la maggior parte dell'ottimizzazione si applica anche a un'implementazione procedurale in C#.

Le due ottimizzazioni più importanti consistono nell'iniziare a cancellare da P^2 anziché da 2*P e nell'utilizzare una ruota per i successivi numeri primi.

Per concorrenza, puoi elaborare tutti i numeri fino a P^2 in parallelo a P senza fare lavoro non necessario.

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");
        }
    }