快速模幂，帮我找到错误

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

但是功能不能正常工作，哪里有错误？

​

​

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

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。

你应该能从这里算出算法。我没有包括使用模数:那应该很容易。