C # premier générateur, Maxing Array Bit

Question

(C #, générateur premier) Heres un code ami et moi avons farfouillé sur:

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

Sur mon Dorky AMD x64 1800+ (dual core), pour tous les nombres premiers inférieurs à 1 milliards d'euros en 34546.875ms. Problème semble être plus stocker dans le tableau de bits. Essayer de manivelle plus de ~ 2billion est plus que le BitArray veut stocker. Toutes les idées sur la façon de contourner cela?

Answer 1

Je voudrais parties du tableau « swap » sur le disque. Par cela, je veux dire, diviser votre tableau de bits en morceaux de bits demi-milliard et de les stocker sur le disque.

ont seulement quelques morceaux en mémoire à un moment donné. Avec C # (ou toute autre langue OO), il devrait être facile de résumer l'énorme tableau dans cette classe Chunking.

Vous payez avec un temps de génération plus lente, mais je ne vois pas autour jusqu'à ce que nous obtenons des espaces d'adressage plus grands et les compilateurs 128 bits.

Answer 2

Ou comme une approche alternative à celle proposée par Pax, utiliser des nouvelles classes de fichiers mémoire mappée dans .NET 4.0 et laissez le système d'exploitation décider quels morceaux doivent être en mémoire à un moment donné.

Notez toutefois que vous aurez envie d'essayer et d'optimiser l'algorithme pour augmenter la localité afin que vous ne finissent pas inutilement échanger pages dans et hors de la mémoire (plus délicat que cette phrase fait son).

Answer 3

Utilisez plusieurs BitArrays pour augmenter la taille maximale. Si un nombre est à peu grand-déplacer et stocker le résultat dans un bit tableau pour stocker des bits 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];

Bien sûr, il serait bien si BitArray soutiendrait la taille jusqu'à System.Numerics.BigInteger.
Permutation sur le disque fera votre code vraiment lent.
J'ai un système d'exploitation 64 bits, et mon BitArray est également limité à 32 bits.

PS: vos calculs de nombres premiers a l'air bizarre, le mien ressemble à ceci:

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'algorithme Sieve serait plus performant. Je peux déterminer tous les nombres premiers de 32 bits (au total environ 105 millions) pour la gamme de int en moins de 4 minutes avec cela. Bien sûr retour la liste des nombres premiers est une autre chose que l'exigence de mémoire il y aurait un peu plus de 400 Mo (1 int = 4 octets). En utilisant une boucle les numéros ont été imprimés dans un fichier, puis importé à un DB pour plus de plaisir :) Cependant, pour le 64 bits amorce le programme aurait besoin de plusieurs modifications et peut-être sur l'exécution distribuée nécessitent plusieurs nœuds. Se référer également aux liens suivants

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

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