模幂运算（python）- 内存溢出

Question

下面是 modular expone

的代码

采用两种不同的方法。在下面的代码中，expo1() 函数是最佳或正确的方法

和 expo2() 函数是相同的替代方法

问题：为什么 expo2() 函数对于较大的底数和指数值会给出不正确的结果，此时代码行内存溢出以及为什么 expo1() 函数没有这个问题。

注意：我还添加了 expo1() 和 expo2() 的图，以 2 为底，指数值高达 300，从图中可以看出 expo1() 和 expo2() 齐头并进到指数 220以 2 为基数，之后 expo2() 开始给出不正确的答案。 ##########################下面的代码###################### ##

mod = 1e9 + 7

# Function to return 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# % mod

# Function to return base^exponent mod m
def expo2(base, exponent):
    ans=1
    for i in range(exponent):
        ans *= base
        ans%=mod
    return ans

plot of expo1() and expo2() for base 2 and exponent values upto 300.

在这里，我还添加了一个新的绘图，用于比较整数和浮点类型的两个函数 mod(1e9 +7) -> comparison of expo1() and expo2() for int and float mod value ，似乎 expo1() 是那个这给出了错误的输出。

Answer 1

任何函数都不应导致“内存溢出”。

第二个函数expo2()会导致超时（如果环境强制在近1.5-2函数没有执行时引发异常秒）对于较大的变量值 exponent。例如，当 exponent >= 10^7.

您可以在 Hackerrank/Codechef/Codeforces 等在线编码门户网站上观察到这一点。

因此进程 (expo2()) 将被终止，因为它执行时间太长，SIGTSTP 将被 returned。

重要提示：

修正变量mod的值，即mod = int(1e9 + 7)并检查结果。

两个函数 return 相同的值。

为什么你得到了不同？

您代码中的变量 mod 是一个浮点值，一定会导致浮点舍入问题。按照建议将其更改为 int。

模幂运算（python）- 内存溢出

modular exponentiation(python)- memory overflow

algorithm

math

modular-arithmetic