如何在Golang中实现整数模幂运算

当计算a^b % m且a^b超出常规整数范围时，直接计算幂会导致数值溢出或性能极差，这时候要用到快速幂（模幂算法），核心是利用模运算的分配性质：

(x * y) % m = [(x % m) * (y % m)] % m

通过这个性质，我们可以在每一步计算中都对中间结果取模，避免数值变得过大，同时通过二进制分解指数b来减少计算次数。

手动实现快速幂 #

下面是Python的手动实现代码，逻辑清晰且高效：

def mod_pow(a, b, m):
    result = 1
    a = a % m  # 先对a取模，缩小初始值
    while b > 0:
        # 如果b是奇数，将当前a乘入结果并取模
        if b % 2 == 1:
            result = (result * a) % m
        # b右移一位（等价于整除2），处理下一位二进制位
        b = b // 2
        # a平方后取模，为下一次乘法做准备
        a = (a * a) % m
    return result

举个例子：计算3^1000000 % 7，用这个函数调用mod_pow(3, 1000000, 7)，结果是1，和直接用Python内置函数pow(3, 1000000, 7)的结果一致。

Python内置的最优解 #

Python自带的pow(a, b, m)就是专门为这个场景设计的，它底层用了优化过的快速幂算法，比手动实现的代码更快更稳定，所以实际开发中直接调用这个函数就行，不用自己重复造轮子。

比如你要计算a**b % m，直接写pow(a, b, m)就搞定，完全不用考虑大数溢出的问题。

内容的提问来源于stack exchange，提问作者Finesse