python — самый быстрый способ использования Factor (Prime-1) / 2 для 64-битной версии Prime?
Я пытаюсь собрать некоторую статистику по простым числам, среди которых есть распределение факторов для числа (простое число 1) / 2. Я знаю, что есть общие формулы для размера факторов равномерно выбранных чисел, но я ничего не видел о распределении факторов на единицу меньше простого.
Я написал программу для перебора простых чисел, начинающихся с первого простого числа после 2 ^ 63, а затем с учетом (простого числа — 1) / 2 с использованием пробного деления на все простые числа до 2 ^ 32. Тем не менее, это очень медленно, потому что это много простых чисел (и много памяти) для перебора. Я сохраняю простые числа как один байт каждый (сохраняя приращение от одного простого до следующего). Я также использую детерминированный вариант теста первичности Миллера-Рабина для чисел до 2 ^ 64, поэтому я могу легко определить, когда оставшееся значение (после успешного деления) является простым.
Я экспериментировал с использованием варианта факторизации по Полларду и эллиптической кривой, но трудно найти правильный баланс между пробным делением и переходом на эти более сложные методы. Также я не уверен, что реализовал их правильно, потому что иногда кажется, что они находят очень одинокое время, чтобы найти фактор, и, основываясь на их асимптотическом поведении, я ожидал бы, что они будут достаточно быстрыми для таких небольших чисел.
Я не нашел никакой информации о факторинге многих чисел (вместо того, чтобы просто вычислять одно), но, похоже, должен быть какой-то способ ускорить задачу, воспользовавшись этим.
Будем весьма благодарны за любые предложения, указания на альтернативные подходы или другие рекомендации по этой проблеме.
Редактировать:
Я сохраняю простые числа путем сохранения 8-битного смещения до следующего простого числа с неявным первым простым числом, равным 3. Таким образом, в моих алгоритмах у меня есть отдельная проверка деления на 2, затем я запускаю цикл:
factorCounts = collections.Counter()
while N % 2 == 0:
factorCounts[2] += 1
N //= 2
pp = 3
for gg in smallPrimeGaps:
if pp*pp > N:
break
if N % pp == 0:
while N % pp == 0:
factorCounts[pp] += 1
N //= pp
pp += gg
Кроме того, я использовал решетчатое колесо для вычисления простых чисел для пробного деления, и я использую алгоритм, основанный на остатке по нескольким простым числам, чтобы получить следующее простое число после заданной начальной точки.
Я использую следующее для проверки, является ли данное число простым (портирование кода на c ++ сейчас):
bool IsPrime(uint64_t n)
{
if(n < 341531)
return MillerRabinMulti(n, {9345883071009581737ull});
else if(n < 1050535501)
return MillerRabinMulti(n, {336781006125ull, 9639812373923155ull});
else if(n < 350269456337)
return MillerRabinMulti(n, {4230279247111683200ull, 14694767155120705706ull, 1664113952636775035ull});
else if(n < 55245642489451)
return MillerRabinMulti(n, {2ull, 141889084524735ull, 1199124725622454117, 11096072698276303650});
else if(n < 7999252175582851)
return MillerRabinMulti(n, {2ull, 4130806001517ull, 149795463772692060ull, 186635894390467037ull, 3967304179347715805ull});
else if(n < 585226005592931977)
return MillerRabinMulti(n, {2ull, 123635709730000ull, 9233062284813009ull, 43835965440333360ull, 761179012939631437ull, 1263739024124850375ull});
else
return MillerRabinMulti(n, {2ull, 325ull, 9375ull, 28178ull, 450775ull, 9780504ull, 1795265022ull});
}
Решение
У меня нет однозначного ответа, но у меня есть некоторые замечания и предложения.
Между 2 ^ 63 и 2 ^ 64 существует около 2 * 10 ^ 17 простых чисел, поэтому любая написанная вами программа будет работать некоторое время.
Давайте поговорим о тесте простоты для чисел в диапазоне от 2 ^ 63 до 2 ^ 64. Любой тест общего назначения сделает больше работы, чем вам нужно, поэтому вы можете ускорить процесс, написав специальный тест. Я предлагаю тесты с сильным псевдопригодностью (как в случае Миллера-Рабина) для оснований 2 и 3. Если любой из этих тестов показывает, что число составное, все готово. В противном случае ищите число (бинарный поиск) в таблице сильных псевдоприемей к базам 2 и 3 (попросите Google найти эти таблицы для вас). Два сильных теста на псевдослучайность с последующим поиском в таблице, безусловно, будут быстрее, чем детерминистический тест Миллера-Рабина, который вы выполняете в настоящее время, который, вероятно, использует шесть или семь баз.
Для факторинга пробное деление на 1000 с последующим Брент-Ро до тех пор, пока произведение известных простых факторов не превосходит кубический корень из факторизованного числа, должно быть довольно быстрым, несколько миллисекунд. Затем, если оставшийся кофактор является составным, он обязательно будет иметь только два фактора, поэтому SQUFOF будет хорошим алгоритмом для их разделения, быстрее, чем другие методы, потому что вся арифметика выполняется с числами, меньшими, чем квадратный корень из числа, являющегося факторизованный, что в вашем случае означает, что факторизация может быть выполнена с использованием 32-битной арифметики вместо 64-битной арифметики, поэтому она должна быть быстрой.
Вместо факторинга и тестов на простоту, лучший метод использует вариант сита Эратосфена для разложения больших блоков чисел. Это все еще будет медленным, так как существует 203 миллиона простых чисел сита, меньших 2 ^ 32, и вам нужно будет вести учет сегментированного сита, но, учитывая, что вы учитываете много чисел одновременно, это, вероятно, лучший подход к твое задание.
У меня есть код для всего упомянутого выше в мой блог.
Другие решения
Вот как я храню простые числа на потом:
(Я собираюсь предположить, что вы хотите, чтобы факторы числа, а не просто тест на простоту).
Скопировано с моего сайта http://chemicaldevelopment.us/programming/2016/10/03/PGS.html
Я предполагаю, что вы знаете двоичную систему счисления для этой части. Если нет, просто подумайте о 1 как «да» и 0 как «нет».
Итак, существует множество алгоритмов для генерации первых нескольких простых чисел. Я использую Сито Эратосфена, чтобы вычислить список.
Но если бы мы хранили простые числа в виде массива, например, [2, 3, 5, 7], это заняло бы слишком много места. Сколько места точно?
Ну, 32-битные целые числа, которые могут хранить до 2 ^ 32 каждого, занимают 4 байта, потому что каждый байт составляет 8 бит, а 32/8 = 4
Если бы мы хотели хранить каждое простое число менее 2 000 000 000, нам пришлось бы хранить более 98 000 000 000. Это занимает больше места и медленнее во время выполнения, чем набор битов, что объясняется ниже.
Этот подход займет 98 000 000 целых мест (каждый составляет 32 бита, что составляет 4 байта), и когда мы проверяем во время выполнения, нам нужно будет проверять каждое целое число в массиве, пока мы не найдем его, или мы не найдем число, которое больше чем это.
Например, скажем, я даю вам небольшой список простых чисел: [2, 3, 5, 7, 11, 13, 17, 19]. Я спрашиваю вас, если 15 простое число. Как ты мне скажешь?
Ну, вы бы прошли через список и сравнить каждый с 15.
2 = 15?
3 = 15?
. . .
17 = 15?
На этом этапе вы можете остановиться, потому что вы прошли, где будет 15, так что вы знаете, что это не простое число.
Теперь, скажем, мы используем список битов, чтобы сообщить вам, является ли число простым. Список выше будет выглядеть так:
001101010001010001010
Это начинается с 0 и продолжается до 19
1 означает, что индекс является простым, поэтому посчитайте слева: 0, 1, 2
001101010001010001010
Последнее число, выделенное жирным шрифтом, равно 1, что означает, что 2 — простое число.
В этом случае, если я попросил вас проверить, является ли 15 простым, вам не нужно просматривать все числа в списке; Все, что вам нужно сделать, это перейти к 0. , , 15, и проверьте этот единственный бит.
А для использования памяти первый подход использует 98000000 целых чисел, тогда как этот может хранить 32 числа в одном целом (используя список 1 и 0), поэтому нам нужно
2000000000/32 = 62500000 целых чисел.
Таким образом, он использует примерно на 60% больше памяти, чем первый подход, и намного быстрее в использовании.
Мы сохраняем массив целых чисел из второго подхода в файле, а затем читаем его при запуске.
При этом используется 250 МБ оперативной памяти для хранения данных о первых 2000000000 простых числах.
Вы можете еще больше уменьшить это с помощью просеивания колеса (например, то, что вы хранили (Prime-1) / 2)
Я пойду немного больше в сито для колес.
Вы поняли это правильно, сохранив (простое число — 1) / 2, а 2 — особый случай.
Вы можете расширить это до п# (произведение первого п простые числа)
Например, вы используете (1 #) * к + 1 для чисел К
Вы также можете использовать набор линейных уравнений (П #) * K + L,, где L множество простых чисел меньше п # и 1 за исключением первого N простые числа.
Таким образом, вы также можете просто хранить информацию для 6 * к + 1 а также 6 * к + 5, и даже более того, потому что L = {1, 2, 3, 5} {2, 3}
Эти методы должны дать вам понимание некоторых методов, стоящих за ним.
Для реализации этого набора битов вам понадобится, например, список 32-битных целых чисел или строка.
Смотреть на: https://pypi.python.org/pypi/bitarray для возможной абстракции