@MAGistr_MTM
Учусь программировать

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

Доброго времени суток.
Есть задание:
Вычислить последние 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))

Но, увы, этот алгоритм слишком медленный. Что можете посоветовать?
Буду очень благодарен за помощь.
  • Вопрос задан
  • 2832 просмотра
Пригласить эксперта
Ответы на вопрос 3
В Python уже есть функция для возведения в степень по модулю: pow(b, c, module). Вряд ли встроенными средствами языка вы напишите более быструю функцию.
Ответ написан
@vilgeforce
Раздолбай и программист
Посмотрите, например, реализацию в openSSL. Можно еще в MIRACL глянуть, тоже сорцы открыты.
Ответ написан
angrySCV
@angrySCV
machine learning, programming, startuping
у вас уже быстрая реализация, единственно вам нужно оптимизировать долгие операции (такие как условный переход - одна из самых затратных операций), ну и по возможности избавиться от лишних операций.
например вместо проверки (деления на 2 без остатка), достаточно проверять последний бит числа равный нулю.
деление на 2 тоже можно заменить сдвигом.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы