Python两种modular exponentiation实现的结果错误与内存溢出问题分析

两种模幂运算的Python实现代码如下：

mod = 1e9 + 7

# 计算 base^exponent mod m 的函数
def expo1(base, exponent):
    cp = base
    cp1 = exponent
    ans = 1
    while (exponent != 0):
        if ((exponent & 1) == 1):
            ans = ans * base
            ans = ans % mod
 
        base = base * base
        base %= mod
        exponent >>= 1
 
    return ans

# 计算 base^exponent mod m 的函数
def expo2(base, exponent):
    ans=1
    for i in range(exponent):
        ans *= base
        ans%=mod
    return ans

问题1：expo2()在底数、指数取值较大时输出错误结果的原因是什么？内存溢出发生在哪一行代码？ #

• 错误原因分为两类：
  1. 时间复杂度过高：expo2是暴力迭代实现，时间复杂度为O(n)（n为指数大小），当指数取值极大（如10^6以上）时，循环执行次数过多，会大量占用CPU、内存资源，严重时会触发资源耗尽异常。
  2. 浮点精度丢失：当前定义的mod是1e9+7浮点类型，双精度浮点数仅能精确表示≤2^53（约9e15）的整数，以底数为2为例，当指数超过220时，ans *= base得到的中间值已经远大于2^53，浮点数无法精确存储该整数，会自动截断精度，后续取模运算也无法得到正确结果。
• 内存溢出/资源耗尽的触发行是for i in range(exponent)：当指数取值超出Python可处理的迭代范围时，range初始化或迭代过程会直接触发资源不足的问题。

问题2：为什么expo1()不存在expo2()遇到的内存溢出问题？ #

expo1是业界通用的快速幂实现，从两个维度规避了expo2的问题：

• 时间复杂度为O(log n)：仅需要对指数做二进制拆分，哪怕指数为10^18，也只需要循环60次左右，完全不会出现循环次数过多导致的资源占用问题。
• 中间值大小可控：每次乘法运算后都会立刻对mod取余，所有中间变量的数值都会被限制在mod的两倍以内，不会出现数值无限增长的情况，也不会触发大数值迭代的资源占用问题。

问题3：浮点型mod场景下expo1()输出错误的原因是什么？ #

错误的核心是浮点精度限制：
两个接近1e9+7的整数相乘时，乘积会达到(1e9+7)^2 ≈ 1e18，该数值已经远超过双精度浮点数能精确表示的整数上限2^53，此时乘法运算会自动丢失低位精度，就算后续做取模运算，得到的结果也会和正确值存在偏差。
如果将mod改为整数类型mod = 10**9 + 7，Python原生支持任意精度的大整数运算，就可以完全规避该问题。 #

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