Как избавиться от переполнения в модуле math?

Question

[Sheephard]

Решаю задачу по учёбе.
Получаю ошибку OverflowError: math range error.

from math import *


def get_b(p, a):
    start_time = time.time()
    # b = math.fmod(math.pow(a, p-2), p)

    b = pow(a, p-2)
    b = b % p
    print("--- %s seconds ---" % (time.time() - start_time))
    return int(b)

print(get_b(2097151, 9))

Как решить проблему?

Без модуля math всё работает, но я не укладываюсь во время. Я пробовала написать свою реализацию возведения в степень на Python, но она не даёт выигрыша во времени.

Думаю, что ошибка в том, что модуль работает во float. Если это так, то как его заставить его работать с int?

Comments

[Сергей П]

Вы же отдаёте себе отчет, что возводите 9 в степень 2097149?
Это сильно больше, чем возраст вселенной в наносекундах от большого взрыва.
Если это число записать в десятичной форме, то оно будет больше двух мегабайт весить.
Да что там, в бинарной форме это больше 800кб

[Sheephard]

Да, я это понимаю - тестовые данные такие, без модуля math работает.

[Влад Григорьев]

Sheephard, вопрос только зачем, какую проблемы вы пытаетесь решить такими цифрами?

[Александр Маджугин]

Решаю задачу по учёбе.

ТС же начал с этого.

Answer 1

[galaxy]

powmod пишете?

pow(x, y[, z])

Return x to the power y; if z is present, return x to the power y, modulo z (computed more efficiently than pow(x, y) % z). The two-argument form pow(x, y) is equivalent to using the power operator: x**y.

Comments

[Sheephard]

Да, powmod. Спасибо, сработало.

В модуле math нет такой возможности, а то, что обычный pow станет настолько быстрее я не знала.