Почему pow (a, d, n) намного быстрее, чем a ** d% n?

110

Я пытался реализовать тест на простоту Миллера-Рабина и был озадачен, почему это занимает так много времени (> 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 намного быстрее ?

Lyallcooper
источник

Ответы:

164

См. Статью в Википедии о модульном возведении в степень . По сути, когда вы это делаете a**d % n, вам действительно нужно вычислять a**d, что может быть довольно большим. Но есть способы вычисления a**d % nбез необходимости вычислять a**dсамого себя, и это то, что powнужно. **Оператор не может этого сделать , потому что он не может «заглянуть в будущее» , чтобы знать , что вы собираетесь немедленно принять модуль.

BrenBarn
источник
14
+1 именно это и подразумевает >>> print pow.__doc__ pow(x, y[, z]) -> number With two arguments, equivalent to x**y. With three arguments, equivalent to (x**y) % z, but may be more efficient (e.g. for longs).
строка
6
В зависимости от вашей версии Python это может быть верно только при определенных условиях. IIRC, в 3.x и 2.7 вы можете использовать форму с тремя аргументами только с целочисленными типами (и неотрицательной степенью), и вы всегда будете получать модульное возведение в степень с собственным intтипом, но не обязательно с другими целочисленными типами. Но в более старых версиях существовали правила встраивания в C long, разрешалась форма с тремя аргументами floatи т. Д. (Надеюсь, вы не используете 2.1 или более раннюю версию и не используете какие-либо пользовательские интегральные типы из модулей C, поэтому ни один это важно для вас.)
abarnert 03
13
Из вашего ответа кажется, что компилятор не может увидеть выражение и оптимизировать его, что неверно. Просто так случилось, что никакие современные компиляторы Python этого не делают.
danielkza 03
5
@danielkza: Это правда, я не имел в виду, что это теоретически невозможно. Может быть, «не смотрит в будущее» было бы точнее, чем «не смотреть в будущее». Однако обратите внимание, что оптимизация может быть чрезвычайно сложной или даже невозможной в целом. Для постоянных операндов он может быть оптимизирован, но x ** y % n, xможет быть объектом , который реализует __pow__и, основываясь на случайном числе, возвращает один из нескольких различных объектов , реализующих __mod__таким образом , что также зависит от случайных чисел и т.д.
BrenBarn
2
@danielkza: Кроме того, у функций не один и тот же домен: .3 ** .4 % .5это совершенно законно, но если компилятор преобразует это в pow(.3, .4, .5)это, вызовет файл TypeError. Компилятор должен знать, что a, dи nгарантированно будут значениями целочисленного типа (или, может быть, просто определенного типа int, потому что в противном случае преобразование не поможет), и dгарантированно будет неотрицательным. Это то, что JIT предположительно может сделать, но статический компилятор для языка с динамическими типами и без вывода просто не может.
abarnert 03
37

БренБарн ответил на ваш главный вопрос. Для вас:

почему он почти в два раза быстрее при работе с Python 2 или 3, чем PyPy, когда обычно PyPy намного быстрее?

Если вы читаете страницу производительности PyPy , это именно то, в чем PyPy не силен - по сути, самый первый пример, который они приводят:

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

Теоретически превращение огромного возведения в степень, за которым следует мод, в модульное возведение в степень (по крайней мере, после первого прохода) - это преобразование, которое JIT могла бы выполнить ... но не JIT PyPy.

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

abarnert
источник
2
исправлены лонги. попробуйте pypy 2.0 beta 1 (он не будет быстрее, чем CPython, но и не должен быть медленнее). gmpy не имеет возможности обрабатывать MemoryError :(
fijal 05
@fijal: Да, и gmpyв некоторых случаях он работает медленнее, чем быстрее, и делает многие простые вещи менее удобными. Это не всегда ответ, но иногда это так. Так что на это стоит обратить внимание, если вы имеете дело с огромными целыми числами, а собственный тип Python кажется недостаточно быстрым.
abarnert 06
1
и если вам все равно, большие ли ваши числа приводят к
сбою
1
Это фактор, который заставил PyPy долго не использовать библиотеку GMP. Это может быть нормально для вас, но не для разработчиков виртуальных машин Python. Malloc может выйти из строя без использования большого количества оперативной памяти, просто поместите туда очень большое число. С этого момента поведение GMP не определено, и Python не может этого допустить.
fijal 07
1
@fijal: Я полностью согласен с тем, что его нельзя использовать для реализации встроенного типа Python. Это не значит, что его нельзя ни для чего использовать.
abarnert
11

Есть ярлыки для выполнения модульного возведения в степень: например, вы можете найти a**(2i) mod nдля каждого iот 1до log(d)и умножить вместе (mod n) нужные вам промежуточные результаты. Специальная функция модульного возведения в степень, такая как 3-аргумент, pow()может использовать такие уловки, потому что знает, что вы выполняете модульную арифметику. Парсер Python не может распознать это по голому выражению a**d % n, поэтому он выполнит полное вычисление (что займет гораздо больше времени).

atomicinf
источник
3

x = a**d % nРассчитывается способ возвести aв dстепень, а затем по модулю n. Во-первых, если aон большой, это создает огромное число, которое затем обрезается. Однако, x = pow(a, d, n)скорее всего, оптимизирован так, что nотслеживаются только последние цифры, а это все, что требуется для вычисления умножения по модулю числа.

Юши
источник
6
"для вычисления x ** d требуется d умножений" - неверно. Вы можете сделать это за O (log d) (очень широкое) умножение. Возведение в степень возведением в квадрат можно использовать без модуля. Здесь лидирует абсолютный размер множимого.
Джон Дворжак
@JanDvorak Верно, я не уверен, почему я думал, что python не будет использовать тот же алгоритм возведения в степень, **что и для pow.
Yuushi 03
5
Не последние "n" цифр .. он просто держит расчеты в Z / nZ.
Thomas