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

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

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

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

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

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

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

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

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

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

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

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

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

Without profiling we cannot tell which bit of the program needs optimizing.

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

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

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

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

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

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

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

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

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

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

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

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