python эффективное двоичное возведение в степень по модулю

Question

Каков наиболее эффективный способ реализации двоичного возведения в степень в python? Это мой подход

    def quad_pow(base, exponent, modul): 
        alpha = (bin(exponent).replace('0b', ''))[::-1]
        a = 1
        b = base

        for i in range(0, len(alpha)):
            if int(alpha[i]) == 1:
                a = (a * b) % modul
            b = (b*b) % modul
        return a

Это лучший способ сделать это?

Answer 1

Метод, который в 2 раза быстрее OP и сравним со встроенной функцией

Код

def power_mod(b, e, m):
  x = 1
  while e > 0:
    if e % 2:
      b, e, x = (b * b) % m, e // 2, (b * x) % m
    else:
      b, e, x = (b * b) % m, e // 2, x

  return x

Сводка по времени

Обычные целые числа 1. В 2 раза быстрее, чем quad_pow 2. Только на ~ 20% медленнее, чем встроенная функция

Большие целые числа

1. power_mod и quad_power сопоставимы по скорости
2. pow (Native) работает примерно в 2 раза быстрее

Подробности синхронизации

Нормальные целые числа (т.е. int64)

a = 1234
b = 15
c = 1000000007

Timing: quad_pow 
%timeit quad_pow(a, b, c)
4.69 µs ± 167 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Timing: power_mod
%timeit power_mod(a, b, c)
2.05 µs ± 39.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Timing: pow (Python builtin function)
power(a, b, c)
1.73 µs ± 37 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Большие целые числа (т.е. требуется произвольная точность)

a = 2988348162058574136915891421498819466320163312926952423791023078876139
b = 2351399303373464486466122544523690094744975233415544072992656881240319
m = 10 ** 40

Timing: quad_pow 
%timeit quad_pow(a, b, c)
263 µs ± 5.86 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Timing: power_mod
%timeit power_mod(a, b, c)
263 µs ± 8.05 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Timing: pow (Python builtin function)
power(a, b, c)
144 µs ± 2.05 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)