Генератор простых чисел C #, Максимизирующий массив битов

Question

(C #, генератор простых чисел) Вот кое-какой код, в котором мы с другом копались:

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

На моем дурацком AMD x64 1800+ (двухъядерный) для всех простых чисел ниже 1 миллиарда за 34546,875мс.Проблема, по-видимому, заключается в хранении большего количества данных в битовом массиве.Попытка собрать более ~ 2 миллиардов - это больше, чем хочет сохранить bitarray.Есть какие-нибудь идеи о том, как это обойти?

Answer 1

Я бы "поменял местами" части массива на диск.Под этим я подразумеваю, что разделите свой битовый массив на полмиллиарда битовых блоков и сохраните их на диске.

У них есть только несколько фрагментов в памяти в любой момент времени.С помощью C # (или любого другого языка OO) должно быть легко инкапсулировать огромный массив внутри этого разделяющего класса.

Вы заплатите за это более медленным временем генерации, но я не вижу никакого способа обойти это, пока мы не получим большие адресные пространства и 128-битные компиляторы.

Answer 2

Или в качестве альтернативного подхода, предложенного Pax, используйте новые файловые классы с отображением памяти в .NET 4.0 и позвольте операционной системе решать, какие фрагменты должны находиться в памяти в любой момент времени.

Однако обратите внимание, что вам захочется попробовать оптимизировать алгоритм для увеличения локальности, чтобы вам не приходилось без необходимости загружать страницы в память и извлекать их из нее (сложнее, чем звучит в этом предложении).

Answer 3

Используйте несколько битовых массивов, чтобы увеличить максимальный размер.Если число должно быть большим, сдвиньте его на бит и сохраните результат в битовом массиве для хранения битов 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];

Конечно, было бы неплохо, если бы BitArray поддерживал размер до System.Цифры.BigInteger.
Замена на диск сделает ваш код действительно медленным.
У меня 64-разрядная ОС, и мой BitArray также ограничен 32 битами.

PS:ваши вычисления простых чисел выглядят странно, мои выглядят так:

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

Алгоритм сита был бы более эффективным.С помощью этого я мог бы определить все 32-битные простые числа (всего около 105 миллионов) для диапазона int менее чем за 4 минуты.Конечно, возвращать список простых чисел - это совсем другое дело, поскольку потребность в памяти там будет чуть более 400 МБ (1 int = 4 байта).Используя цикл for, числа были напечатаны в файл, а затем импортированы в базу данных для большего удовольствия :) Однако для 64-разрядных простых чисел программе потребуется несколько модификаций и, возможно, потребуется распределенное выполнение на нескольких узлах.Также обратитесь к следующим ссылкам

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

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