Как я могу улучшить эффективность этого алгоритма?

Question

У меня есть следующий фрагмент кода, который не ведет себя так, как я хочу.

def cipher(plaintext, arr):
    import math
    ciphered = []
    for letter in plaintext:
        ciphered.append(math.pow(ord(letter)-65,arr[1]%arr[0]))
    return ciphered

Аргументы, которые попадают в math.pow, это 142 и 35. Затем он использует этот результат, чтобы найти модуль с 221. Однако результат, который он мне дает, равен 206.0, когда результат, который он должен дать мне, равен 12. Даже когда я найти этот результат в вольфрам альфа, результат равен 12. Я думаю, что проблема здесь связана с проблемой переполнения. Однако я не знаю, как это исправить

Answer 1

То, что вы пытаетесь построить, называется модульным возведением в степень, и для него существует оптимизированный алгоритм, который позволит избежать потери точности и, следовательно, неверного результата:

def pow_mod(b, e, m):
    """Compute (b^e) mod m."""
    c, e_ = 1, 0
    while e_ < e:
        e_ += 1
        c = (b*c) % m
    return c

---

редактировать (спасибо, @ user2357112):... или вы можете просто использовать встроенный pow, который делает это уже. Но если вы спросили, как повысить эффективность, вот как.