C # Prime Generator, Maxing Bit Array

Question

(C #, il primo generatore) Heres po 'di codice un amico e io stavamo rovistando su:

public List<int> GetListToTop(int top)
{            
    top++;
    List<int> result = new List<int>();
    BitArray primes = new BitArray(top / 2);
    int root = (int)Math.Sqrt(top);
    for (int i = 3, count = 3; i <= root; i += 2, count++)
    {
        int n = i - count;
        if (!primes[n])
            for (int j = n + i; j < top / 2; j += i)
            {
                primes[j] = true;
            }
    }
    if (top >= 2)
        result.Add(2);            
    for (int i = 0, count = 3; i < primes.Length; i++, count++)
    {
        if (!primes[i])
        {
            int n = i + count;
            result.Add(n);
        }
    }

    return result;
}

Al mio dorky AMD x64 1800+ (dual core), per tutti i numeri primi inferiori a 1 miliardo in 34546.875ms. Problema sembra essere memorizzare più nella matrice di bit. Cercando di far girare più di ~ 2 miliardi è più della BitArray vuole memorizzare. Tutte le idee su come ottenere intorno a questo?

Answer 1

lo farei "Swap" parti della matrice su disco. Con questo, voglio dire, dividere la matrice di bit in mezzo miliardo di pezzi bit e memorizzarli sul disco.

L'hanno solo pochi pezzi in memoria in qualsiasi momento. Con C # (o qualsiasi altro linguaggio OO), dovrebbe essere facile per incapsulare la vasta gamma all'interno di questa classe di suddivisione in blocchi.

Si paga per questo con un tempo più lento generazione, ma non vedo alcun modo per aggirare questo fino ad arrivare spazi di indirizzi più grandi e compilatori a 128 bit.

Answer 2

O come un approccio alternativo a quello suggerito da Pax, utilizzare le nuove classi file mappato in memoria in .NET 4.0 e lasciare che il sistema operativo decidere quali pezzi devono essere in memoria in un dato momento.

Si noti tuttavia che si vuole cercare di ottimizzare l'algoritmo per incrementare località in modo che non si inutilmente finire scambiare pagine dentro e fuori dalla memoria (più complicato di questa sola frase rende il suono).

Answer 3

Utilizzare più BitArrays per aumentare la dimensione massima. Se un numero è di grande bit-spostarlo e memorizzare il risultato in una po-array per la memorizzazione di bit 33-64.

BitArray second = new BitArray(int.MaxValue);
long num = 23958923589;
if (num > int.MaxValue)
{
    int shifted = (int)num >> 32;
    second[shifted] = true;
}

long request = 0902305023;
if (request > int.MaxValue)
{
    int shifted = (int)request >> 32;
    return second[shifted];
}
else return first[request];

Naturalmente sarebbe bello se BitArray sarebbe a favore di dimensione fino a System.Numerics.BigInteger.
Swapping su disco renderà il vostro codice di molto lento.
Ho un sistema operativo a 64-bit, e la mia BitArray è anche limitato a 32-bit.

PS: i vostri calcoli numero primo sembra strano, il mio assomiglia a questo:

for (int i = 2; i <= number; i++)
    if (primes[i])
        for (int scalar = i + i; scalar <= number; scalar += i)
        {
            primes[scalar] = false;
            yield return scalar;
        }

Answer 4

L'algoritmo Sieve sarebbe meglio performante. Ho potuto determinare tutti i primi 32 bit (in totale circa 105 milioni) per l'intervallo int in meno di 4 minuti con questo. Naturalmente tornando l'elenco dei numeri primi è una cosa diversa, come i requisiti di memoria ci sarebbe stato un po 'più di 400 MB (1 int = 4 byte). Utilizzando un ciclo for i numeri sono stati stampati in un file e poi importati in un DB per più divertente :) Comunque per il bit 64 innesca il programma avrebbe bisogno di diverse modifiche e forse richiedono distribuiti esecuzione su più nodi. Consultare anche i seguenti link

http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm

http://en.wikipedia.org/wiki/Prime-counting_function