C # Prime Generator, Maxing Bit Array

Question

(C #, Prime-Generator) Heres einige Code ein Freund und ich waren Stochern auf:

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

Auf meinem dorky AMD x64 1800+ (Dual-Core) für alle Primzahlen unter 1 Milliarde in 34546.875ms. Problem scheint im Bitfeld zu speichern. Der Versuch, mehr Kurbel als ~ 2billion ist mehr als die BitArray speichern möchte. Alle Ideen, wie um das zu bekommen?

Answer 1

Ich würde „swap“ Teile des Arrays auf der Festplatte. Damit meine ich, teilen Sie Ihre Bit-Array in halbe Milliarde Bit-Blöcken und speichert sie auf der Festplatte.

Die haben nur ein paar Brocken im Speicher zu einem beliebigen Zeitpunkt. Mit C # (oder einer anderen OO-Sprache), sollte es einfach sein, die riesige Auswahl innerhalb dieser Chunking Klasse zu kapseln.

Sie werden es mit einer langsameren Generation Zeit bezahlen, aber ich sehe keinen Weg dran vorbei, bis wir größere Adressräume erhalten und 128-Bit-Compiler.

Answer 2

oder als Alternative zu dem von Pax vorgeschlagen, nutzt die neuen Memory-Mapped-Datei Klassen in .NET 4.0 und lassen Sie das Betriebssystem entscheiden, welche Stücke müssen zu einem bestimmten Zeitpunkt in Erinnerung sein.

Beachten Sie jedoch, dass Sie wollen versuchen, den Algorithmus zu optimieren Ort zu erhöhen, so dass Sie nicht unnötig Sie tauschen am Ende Seiten in und aus dem Speicher (heikler als dieser Satz macht es klingen).

Answer 3

mehr BitArrays Verwenden Sie die maximale Größe zu erhöhen. Wenn eine Zahl ist, um große Bitschiebevorgang es und speichert das Ergebnis in einem Bit-Array für die Bits 33-64 gespeichert werden.

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

Natürlich wäre es schön, wenn BitArray würde Größe bis zu System.Numerics.BigInteger unterstützen.
Swapping auf die Festplatte wird Ihr Code wirklich langsam machen.
Ich habe ein 64-Bit-Betriebssystem, und mein BitArray ist auch beschränkt auf 32-Bit.

PS: Ihre Primzahl Berechnungen wierd aussieht, mein sieht wie folgt aus:

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

Der Sieve-Algorithmus würde eine bessere Leistung sein. Ich konnte alle 32-Bit-Primzahlen (insgesamt etwa 105 Millionen) für den int Bereich in weniger als 4 Minuten mit dem bestimmen. Rückkehr natürlich die Liste der Primzahlen ist eine andere Sache als Speicherbedarf dort etwas mehr als 400 MB (1 int = 4 Byte) sein würde. eine for-Schleife die Zahlen in eine Datei gedruckt wurden und dann für mehr Spaß an einen DB importiert :) jedoch für den 64-Bit, das Programm müßte mehrere Modifikationen Primzahlen und vielleicht Ausführung über mehrere Knoten verteilt erfordern. Beachten Sie auch die folgenden Links

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

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