快速模指数，帮我找错误

Question

我正在尝试实现一种快速指数方案。度数以二进制形式表示：

def pow_h(base, degree, module):
    degree = bin(degree)[2:]
    r = 1

    for i in range(len(degree) - 1, -1, -1):
        r = (r ** 2) % module
        r = (r * base ** int(degree[i])) % module

    return r

但是函数没有正常工作，错在哪里？

- Andrii Matiiash

---

在函数中添加 print() 以查看您得到的值，并将其与纸上的计算进行比较。 - furas

顺便提一下，内置的 pow 函数接受一个模数作为可选的第三个参数。 - PM 2Ring

Answer 1

正如我在评论中所说，内置的pow函数已经实现了快速模指数，但是我认为自己实现它是一个合理的编码练习。

你的算法很接近，但是你平方的是错误的东西。你需要平方base而不是r，并且你应该在乘法步骤之后进行平方。

def pow_h(base, degree, module):
    degree = bin(degree)[2:]
    r = 1
    for i in range(len(degree) - 1, -1, -1):
        r = (r * base ** int(degree[i])) % module
        base = (base ** 2) % module
    return r

#test

for i in range(16):
    print(i, 2**i, pow_h(2, i, 100))

输出

0 1 1
1 2 2
2 4 4
3 8 8
4 16 16
5 32 32
6 64 64
7 128 28
8 256 56
9 512 12
10 1024 24
11 2048 48
12 4096 96
13 8192 92
14 16384 84
15 32768 68

使用r * base ** int(degree[i])是一个巧妙的技巧，但使用if语句可能更有效率，而且可以使用算术来获取degree的位，而不是使用字符串，尽管bin非常高效。无论如何，这是我的版本：

def pow_h(base, power, modulus):
    a = 1
    while power:
        power, d = power // 2, power % 2
        if d:
            a = a * base % modulus
        base = base * base % modulus
    return a

- PM 2Ring

---

我可能会使用 power, d = divmod(power, 2) 来代替。 - chepner

@chepner：我偶尔使用divmod是因为它的优雅性，但在我的timeit测试中，我发现divmod(a, b)比仅使用a // b, a % b稍微慢一些。但那是在Python 2.6上，在一台相当老的机器上进行的测试，所以你的情况可能会有所不同。 - PM 2Ring

同意；我先测试了几次，结果差异很大，使用 //-% 的速度是 divmod 的 1-15 倍。这个范围以及 divmod 时间保持稳定的事实表明可能存在缓存或测试设置不佳的情况，因此我选择了一个更中立的评论。 - chepner

Answer 2

快速幂运算如果指数是奇数或偶数，操作是不同的，但你的代码中没有这样的检查。下面是一些提示：

为了计算 x 的 y 次方，你需要一个累加器变量来保存到目前为止计算出的值。我们使用 a 来表示。因此，你正在计算 a*(x**y)，并使用代码逐渐递减 y 并递增 a 和/或 x，直到 y 变为零，a 即为最终答案。

如果 y 是偶数，如 y==2*k，则 a*x**(2*k) == a*(x**2)**k。这将把 y 减少到 y//2，并将 x 增加到 x**2。

如果 y 是奇数，如 y==2k+1，则 a*x**(2*k+1) == (a*x)*x**(2*k)。这将把 y 减少到 y-1，并将 a 增加到 a*x。

从这里开始，你应该能够推导出算法。我没有包括使用模数的内容：那应该很容易。

- Rory Daulton