python - 快速模幂，帮我找错

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