Оптимальный алгоритм возведения в степень по модулю. Как улучшить?

Question

[Yura Khlyan]

Доброго времени суток.
Есть задание:
Вычислить последние 12 знаков следующего выражения(** - возведение в степень):A * B**C + D
Где, 1 <= A, B, C, D <= 10**9
Вот моя реализация на Python:

n = int(input()) #number of test cases
module = 10 ** 12

def pow_l(x, n):
    result = 1
    while n != 0:
        if n % 2 != 0:
            result *= x
            result %= module
            n -= 1
        else:
            x *= x
            x %= module
            n /= 2
    return result

for i in range(n):
    a, b, c, d = (int(num) for num in input().split())
    prod = (a * pow_l(b, c) + d) % module
    print (str(prod).zfill(12))

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

Answer 1

[Виталий]

В Python уже есть функция для возведения в степень по модулю: pow(b, c, module). Вряд ли встроенными средствами языка вы напишите более быструю функцию.

Comments

[h8nor]

+1. Пробовал писать нахождение квадратного корня из натурального числа на VB через сложение и вычитание https://gist.github.com/bopoh13/, - в среднем медленнее встроенных функций в 4 раза. Видимо, моё представление о выполнении математических операций не соответствовало действительным операциям с функциями. Думается, Майкл Доусон вводит в заблуждение, что свои функции могут работать быстрее встроенных.

[Dimonchik]

https://www.youtube.com/watch?v=zOuxxnUY4lg не вводит, они __могут__, но не обязаны, вряд ли быстрее будут обычные а-ля корень, на которых интерпретатор собаку съел

[h8nor]

dimonchik2013: не обязаны - это понятно. Вот бы пример посмотреть, где "могут"... Благодарю за разъяснения. Как можно дизассемблировать код, чтобы посмотреть работу интерпретатора, как на слайде 10:02?

[Виталий]

Дѣаволъ: модуль dis https://docs.python.org/3.4/library/dis.html

[h8nor]

Виталий: Премного благодарен!

Answer 2

[Владимир Мартьянов]

Посмотрите, например, реализацию в openSSL. Можно еще в MIRACL глянуть, тоже сорцы открыты.

Answer 3

[⚡ Kotobotov ⚡]

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

лучше вобще избавиться от условных операций, заменив их на безусловные -> тк у вас везде происходит операция х*х -> эту часть операций можно объединить
a оставшуюся операцию с N можно заменить на двойную (где битовый остаток - это последний бит в числе N будет равен или 1 или 0 в зависимости от чётности числа).
пример: n= (n>>1)*(битовый остаток) + (n--)*(!битовый остаток)
такая оптимизация гарантированно ускорит работу.