modular exponentiation(python)- memory overflow

below is the code for modular expone

ntiation with two different approaches. in below code expo1() function is the optimal or correct method

and expo2() function is alternative approach for same

QUESTION: why expo2() function does give incorrect results for larger values of base and exponant, at which line of code memory overflows and why expo1() function does not have this problem.

note : i have also added plot of expo1() and expo2() for base 2 and exponent values upto 300, it can be seen in graph that expo1() and expo2() go hand in hand upto exponent 220 with base 2 and after that expo2() starts giving incorrect answers. ##########################code below########################

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.

here i have also added a new plot for camparing above two functions with integer and float type mod(1e9 +7) -> comparison of expo1() and expo2() for int and float mod value , and it seems expo1() is the one which was giving wrong output.

Solution

By no means any of the functions should result into "memory overflow".

The second function expo2() will cause a Time limit exceeded (if the environment is enforced to raise an exception when the function does not execute in nearly 1.5-2 seconds) for larger values of the variable exponent. For example, when exponent >= 10^7.

You can observe this on online coding portals like Hackerrank/Codechef/Codeforces.

So the process (expo2()) will be killed because it is taking too much time to execute and SIGTSTP will be returned.

IMPORTANT:

Correct the value of variable mod, i.e., mod = int(1e9 + 7) and check the results.

Both the functions return same values.

Why you got the difference?

The variable mod in your code is a floating point value that must have caused floating point rounding issues. Change it to int as suggested.