Я пытался реализовать критерий примирения Миллера-Рабина и был озадачен тем, почему он занимал так много времени ( > 20 секунд) для средних чисел (~ 7 цифр)). В конце концов я нашел следующую строку кода источником проблемы:
x = a**d % n
(где a, d и n все одинаковы, но неравные, средние числа, ** - оператор экспоненции, а % - оператор по модулю)
Затем я попытался заменить его следующим:
x = pow(a, d, n)
и это сравнение почти мгновенно.
В контексте контекстная функция:
from random import randint
def primalityTest(n, k):
if n < 2:
return False
if n % 2 == 0:
return False
s = 0
d = n - 1
while d % 2 == 0:
s += 1
d >>= 1
for i in range(k):
rand = randint(2, n - 2)
x = rand**d % n # offending line
if x == 1 or x == n - 1:
continue
for r in range(s):
toReturn = True
x = pow(x, 2, n)
if x == 1:
return False
if x == n - 1:
toReturn = False
break
if toReturn:
return False
return True
print(primalityTest(2700643,1))
Пример расчетного времени:
from timeit import timeit
a = 2505626
d = 1520321
n = 2700643
def testA():
print(a**d % n)
def testB():
print(pow(a, d, n))
print("time: %(time)fs" % {"time":timeit("testA()", setup="from __main__ import testA", number=1)})
print("time: %(time)fs" % {"time":timeit("testB()", setup="from __main__ import testB", number=1)})
Выход (выполняется с PyPy 1.9.0):
2642565
time: 23.785543s
2642565
time: 0.000030s
Выход (запуск с Python 3.3.0, 2.7.2 возвращает очень похожие времена):
2642565
time: 14.426975s
2642565
time: 0.000021s
И связанный с этим вопрос, почему этот расчет почти в два раза быстрее при запуске с Python 2 или 3, чем с PyPy, когда обычно PyPy намного быстрее?
См. статью в Википедии о модульном экспонировании. В основном, когда вы делаете a**d % n, вам действительно нужно вычислить a**d, который может быть довольно большим. Но есть способы вычисления a**d % n без необходимости вычислять a**d, и это то, что делает pow. Оператор ** не может этого сделать, потому что он не может "видеть в будущем", чтобы знать, что вы немедленно примете модуль.
BrenBarn ответил на ваш главный вопрос. Для вашего внимания:
почему он работает почти в два раза быстрее при запуске с Python 2 или 3, чем PyPy, когда обычно PyPy работает намного быстрее?
Если вы читаете PyPy страницу производительности, это именно то, что PyPy не очень хорошо - на самом деле, в самом первом примере они дают:
Теоретически, превращение огромного возведения в степень, за которым следует мода в модульное возведение в степень (по крайней мере, после первого прохода), является преобразование, которое JIT может сделать... но не PyPy JIT.Плохие примеры включают в себя выполнение вычислений с большими длинами - что выполняется неоптимизированным кодом поддержки.
В качестве примечания, если вам нужно делать вычисления с огромными целыми числами, вы можете посмотреть сторонние модули, например gmpy, который иногда может быть намного быстрее, чем реализация на языке CPython, в некоторых случаях вне основного использования, а также имеет много дополнительных функций, которые вам пришлось бы написать самому, ценой менее удобной.
Быстрые сокращения для модульного возведения в степень: например, вы можете найти a**(2i) mod n для каждого i от 1 до log(d) и умножить вместе (mod n) промежуточные результаты, которые вам нужны. Специальная функция модульной экспоненции, такая как 3-аргумент pow(), может использовать такие трюки, потому что знает, что вы выполняете модульную арифметику. Парсер Python не может распознать это с учетом открытого выражения a**d % n, поэтому он выполнит полный расчет (который займет гораздо больше времени).
Вычисляется способ x = a**d % n - поднять a до уровня d, а затем по модулю, что с n. Во-первых, если a велико, это создает огромное количество, которое затем усекается. Тем не менее, x = pow(a, d, n), скорее всего, оптимизирован так, что отслеживаются только последние цифры n, которые являются обязательными для вычисления умножения по модулю числа.