Вопрос по algorithm – Сегментированное сито Аткина, возможно?

5

Мне известен тот факт, что сито Эратосфена может быть реализовано так, чтобы оно непрерывно находило простые числа без верхней границы (сегментированное сито).

Мой вопрос: может ли Сито Аткина-Бернштейна быть реализовано таким же образом?

Связанный вопрос:C #: Как сделать Сито Аткина инкрементным

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

Я изучал сито Аткина-Бернштейна в течение многих лет и никогда не думал, как сделать его сегментированным - под этим я подразумеваю, чтобы начать его с произвольно большого числа, возможно с меньшим предварительным вычислением. Мне было бы интересно узнать, есть ли у кого-нибудь. librik

Ваш Ответ

2   ответа
2

можно реализовать неограниченное Sieve of Atkin (SoA), не используя сегментацию вообще, как я сделалздесь, в F #, Следует отметить, что это чисто функциональная версия, которая даже не использует массивы для объединения решений квадратных уравнений и фильтра без квадратов и, таким образом, значительно медленнее, чем более императивный подход.

Оптимизация Берштейна с использованием справочных таблиц для оптимальных 32-битных диапазонов сделает код чрезвычайно сложным и непригодным для представления здесь, но было бы довольно легко адаптировать мой код F # так, чтобы последовательности начинались с установленного нижнего предела и используется только в диапазоне для реализации сегментированной версии и / или применения тех же методов к более императивному подходу с использованием массивов.

Следует отметить, что даже реализация SoA Берштейном на самом деле не быстрее, чем сито эратосфена со всеми возможными оптимизациями в соответствии сПримеши Кима Валиша но только быстрее чемan equivalently optimized version of the Sieve of Eratosthenes for the selected range of numbers согласно его реализации.

EDIT_ADD:  Для тех, кто не хочет пробираться через псевдокод и С-код Берштейна, я добавляю к этому ответу добавление метода псевдокода для использования SoA в диапазоне от LOW до HIGH, где дельта от LOW до HIGH + 1 может быть ограничен четным модулем 60 для использования оптимизаций по модулю (и потенциальной битовой упаковке только для записей на колесе 2,3,5).

Это основано на возможной реализации с использованием квадратиков SoA (4 * x ^ 2 + y ^), (3 * x ^ 2 + y ^ 2) и (3 * x ^ 2 -y ^ 2) для выражения как последовательности чисел со значением x для каждой последовательности, установленной на значения между одним и SQRT ((HIGH - 1) / 4), SQRT ((HIGH - 1) / 3) и решение квадратичного для 2 * x ^ 2 + 2 * x - HIGH - 1 = 0 для x = (SQRT (1 + 2 * (HIGH + 1)) - 1) / 2, соответственно, с последовательностями, выраженными в моем коде F #, согласно верхней ссылке. Оптимизация для последовательностей там использует это при просеивании только для нечетных композитов, для "4x" последовательности, значения y должны быть только нечетными, и что "3x" последовательности должны использовать нечетные значения y только тогда, когда x чётно, и наоборот. Дальнейшая оптимизация уменьшает количество решений для квадратных уравнений (= элементов в последовательностях), наблюдая, что шаблоны по модулю над вышеупомянутыми последовательностями повторяются в очень малых диапазонах x, а также повторяются в диапазонах y, равных только 30, что используется код Берштейна, но не (пока) не реализован в моем коде F #.

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

Таким образом, в целях вычисления адресов начального сегмента последовательности для «4x», «3x +» и «3x-»; (или с «3x +» и «3x-», объединенными, как я, в коде F #), и, рассчитав диапазоны x для каждого, как указано выше, псевдокод выглядит следующим образом:

Calculate the range LOW - FIRST_ELEMENT, where FIRST_ELEMENT is with the lowest applicable value of y for each given value of x or y = x - 1 for the case of the "3x-" sequence.

For the job of calculating how many elements are in this range, this boils down to the question of how many of (y1)^2 + (y2)^2 + (y3)^2... there are where each y number is separated by two, to produce even or odd 'y's as required. As usual in square sequence analysis, we observe that differences between squares have a constant increasing increment as in delta(9 - 1) is 8, delta(25 - 9) is 16 for an increase of 8, delta (49 - 25) is 24 for a further increase of 8, etcetera. so that for n elements the last increment is 8 * n for this example. Expressing the sequence of elements using this, we get it is one (or whatever one chooses as the first element) plus eight times the sequence of something like (1 + 2 + 3 + ...+ n). Now standard reduction of linear sequences applies where this sum is (n + 1) * n / 2 or n^2/2 + n/2. This we can solve for how many n elements there are in the range by solving the quadratic equation n^2/2 + n/2 - range = 0 or n = (SQRT(8*range + 1) - 1) / 2.

Now, if FIRST_ELEMENT + 4 * (n + 1) * n does not equal LOW as the starting address, add one to n and use FIRST_ELEMENT + 4 * (n + 2) * (n + 1) as the starting address. If one uses further optimizations to apply wheel factorization culling to the sequence pattern, look up table arrays can be used to look up the closest value of used n that satisfies the conditions.

The modulus 12 or 60 of the starting element can be calculated directly or can be produced by use of look up tables based on the repeating nature of the modulo sequences.

Each sequence is then used to toggle the composite states up to the HIGH limit. If the additional logic is added to the sequences to jump values between only the applicable elements per sequence, no further use of modulo conditions is necessary.

The above is done for every "4x" sequence followed by the "3x+" and "3x-" sequences (or combine "3x+" and "3x-" into just one set of "3x" sequences) up to the x limits as calculated earlier or as tested per loop.

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

4

оригинальная бумага, Предположительно БернштейнPrimeGen Программа использует этот метод.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded K.Steff

Похожие вопросы