Самый быстрый способ вычисления простых чисел в C #?

Question

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

int Until = 20000000;
BitArray PrimeBits = new BitArray(Until, true);

/*
 * Sieve of Eratosthenes
 * PrimeBits is a simple BitArray where all bit is an integer
 * and we mark composite numbers as false
 */

PrimeBits.Set(0, false); // You don't actually need this, just
PrimeBits.Set(1, false); // remindig you that 2 is the smallest prime

for (int P = 2; P < (int)Math.Sqrt(Until) + 1; P++)
    if (PrimeBits.Get(P))
        // These are going to be the multiples of P if it is a prime
        for (int PMultiply = P * 2; PMultiply < Until; PMultiply += P)
            PrimeBits.Set(PMultiply, false);

// We use this to store the actual prime numbers
List<int> Primes = new List<int>();

for (int i = 2; i < Until; i++)
    if (PrimeBits.Get(i))
        Primes.Add(i);

Может быть, я мог бы использовать несколько BitArray с и BitArray.And () их вместе?

Answer 1

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

Кроме того, при удалении более поздних композитов, когда вы впервые нажмете новое простое число p - первым оставшимся составным кратным p будет p * p, так как все, что до этого было уже удалено На самом деле, вам нужно только умножить p на все оставшиеся потенциальные простые числа, которые остались после него в списке, и остановится, как только ваш продукт выйдет за пределы диапазона (больше, чем до).

Есть также несколько хороших вероятностных алгоритмов, таких как тест Миллера-Рабина. Страница Википедии - хорошее введение.

Answer 2

Помимо параллелизации, вы не хотите вычислять sqrt (До) на каждой итерации. Вы также можете принять множители 2, 3 и 5 и рассчитать только для N% 6 в {1,5} или N% 30 в {1,7,11,13,17,19,23,29}.

Вы сможете легко распараллелить алгоритм факторинга, поскольку N-й этап зависит только от sqrt (n) -го результата, поэтому через некоторое время не будет никаких конфликтов. Но это не очень хороший алгоритм, поскольку он требует большого деления.

Вы также должны иметь возможность распараллеливать алгоритмы просеивания, если у вас есть рабочие пакеты средства записи, которые гарантированно завершаются перед чтением. В основном, авторы не должны конфликтовать с читателем - по крайней мере, после того, как вы сделали несколько записей, они должны работать по крайней мере на N выше читателя, поэтому вам нужно только синхронизированное чтение довольно редко (когда N превышает последнее синхронизированное чтение значение). Вам не нужно синхронизировать массив bool с любым количеством потоков записи, поскольку конфликты записи не возникают (в худшем случае более одного потока записывают значение true в одно и то же место).

Основная проблема заключается в том, чтобы обеспечить завершение работы любого работника, ожидающего записи. В C ++ вы использовали бы сравнение и набор для переключения на работника, которого ожидают в любой момент. Я не C # Wonk, поэтому не знаю, как сделать это на этом языке, но функция Win32 InterlockedCompareExchange должна быть доступна.

Вы также можете попробовать подход, основанный на актерах, так как таким образом вы можете планировать актеров, работающих с наименьшими значениями, что может быть легче гарантировать, что вы читаете действительные части решета без необходимости блокировки шины каждый шаг N.

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

Answer 3

Без профилирования мы не можем сказать, какой бит программы нужно оптимизировать.

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

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

Answer 4

    void PrimeNumber(long number)
    {
        bool IsprimeNumber = true;
        long  value = Convert.ToInt32(Math.Sqrt(number));
        if (number % 2 == 0)
        {
            IsprimeNumber = false;
            MessageBox.Show("No It is not a Prime NUmber");
            return;
        }
        for (long i = 3; i <= value; i=i+2)
        {             
           if (number % i == 0)
            {

                MessageBox.Show("It is divisible by" + i);
                IsprimeNumber = false;
                break;
            }

        }
        if (IsprimeNumber)
        {
            MessageBox.Show("Yes Prime NUmber");
        }
        else
        {
            MessageBox.Show("No It is not a Prime NUmber");
        }
    }

Answer 5

Есть очень хорошая статья о Сите Эратосфена: Подлинное Сито Эратосфена

Это в функциональной настройке, но большая часть оптимизации также применима к процедурной реализации в C #.

Две наиболее важные оптимизации - начать вычеркивать с P ^ 2 вместо 2 * P и использовать колесо для следующих простых чисел.

Для параллелизма вы можете обрабатывать все числа до P ^ 2 параллельно с P, не выполняя никакой ненужной работы.

Answer 6

Вы пытаетесь найти новые простые числа? Это может звучать глупо, но вы можете загрузить какую-то структуру данных с известными простыми числами. Я уверен, что у кого-то есть список. Это может быть гораздо проще найти существующие числа для расчета новых.

Вы также можете обратиться к Microsoft Parallel FX Library , чтобы сделать существующий код многопоточным для использования преимуществ многоядерных систем. С минимальными изменениями кода вы можете сделать циклы многопоточными.

Answer 7

Вам также следует рассмотреть возможное изменение алгоритмов .

Учтите, что может быть дешевле просто добавить элементы в список по мере их нахождения.

Возможно, предварительное выделение места для вашего списка сделает сбор / заполнение дешевле.

Answer 8

@ DrPizza Profiling только действительно помогает улучшить реализацию, не раскрывает возможности параллельного выполнения и не предлагает более совершенные алгоритмы (если только у вас нет опыта, в противном случае мне бы очень хотелось увидеть ваш профилировщик) .

У меня дома только одноядерные машины, но я запускал Java-эквивалент вашего сита BitArray и однопоточную версию инверсии сита - удержание простых чисел разметки в массиве и использование колеса чтобы уменьшить пространство поиска в пять раз, а затем разметить битовый массив с шагом колеса, используя каждый маркировочный штрих. Это также уменьшает объем памяти до O (sqrt (N)) вместо O (N), что помогает как с точки зрения наибольшего N, подкачки и пропускной способности.

Для средних значений N (от 1e8 до 1e12) простые числа до sqrt (N) могут быть найдены довольно быстро, и после этого вы сможете довольно легко распараллелить последующий поиск в ЦП. На моей одноядерной машине подход с колесом находит простые числа до 1e9 в 28 с, тогда как ваше сито (после перемещения sqrt из цикла) занимает 86 с - улучшение за счет колеса; инверсия означает, что вы можете обрабатывать N больше, чем 2 ^ 32, но делает это медленнее. Код можно найти здесь . Вы можете распараллелить вывод результатов из наивного сита после того, как вы пройдете и через sqrt (N), так как битовый массив не изменяется после этой точки; но если вы имеете дело с N, достаточно большим, чтобы он имел значение, размер массива слишком велик для целых чисел.