C # primeiro-Generator, Atingir o máximo de matriz de bits

Question

(C #, gerador prime) Heres algum código para um amigo e eu estávamos bisbilhotando em:

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

No meu idiota AMD x64 1800+ (dual core), para todos os números primos abaixo de 1 bilhão em 34546.875ms. Problema parece estar armazenando mais na matriz bit. Tentando manivela mais de ~ 2 bilhões é mais do que o bitarray quer armazenar. Todas as ideias sobre como contornar isso?

Answer 1

Eu gostaria de "swap" partes da série para o disco. Por isso, quero dizer, dividir sua matriz de bits em bits pedaços meio bilhão e armazená-los no disco.

A tem apenas alguns pedaços na memória a qualquer momento. Com C # (ou qualquer outra linguagem OO), que deve ser fácil para encapsular a enorme variedade dentro desta classe chunking.

Você vai pagar por isso com um tempo de geração mais lento, mas eu não vejo qualquer maneira de contornar isso até chegarmos maiores espaços de endereço e compiladores de 128 bits.

Answer 2

Ou como uma abordagem alternativa à sugerida pela Pax, fazer uso das novas classes arquivo de memória mapeada em .NET 4.0 e deixar o OS decidir qual pedaços precisa estar na memória a qualquer momento.

Note, porém, que você vai querer experimentar e otimizar o algoritmo para aumentar a localidade para que você não desnecessariamente acabam trocando páginas dentro e fora de memória (mais complicado do que isso uma frase faz parecer).

Answer 3

Usar vários BitArrays para aumentar o tamanho máximo. Se um número é grande bit shift-lo e armazenar o resultado em um array bit para armazenar 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];

Claro que seria bom se BitArray apoiaria tamanho até System.Numerics.BigInteger.
Trocando para o disco vai tornar seu código muito lento.
Eu tenho um sistema operacional de 64 bits, e minha BitArray também é limitado a 32-bits.

PS: seu auge cálculos número parece estranho, meu parecido com este:

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

O algoritmo Sieve seria melhor desempenho. I pode determinar todos os números primos de 32 bits (total de cerca de 105 milhões) para a gama int em menos de 4 minutos, com que. Claro retornando a lista de números primos é uma coisa diferente, como o requisito de memória haveria um pouco mais de 400 MB (1 int = 4 bytes). Usando um loop os números foram impressas em um arquivo e, em seguida, importados para um DB para mais diversão :) No entanto, para o 64 bit prepara o programa iria precisar de várias modificações e talvez exigem distribuído execução sobre vários nós. Além disso, consulte os links a seguir

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

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