Doubt in modular exponentation

general
1

I am doubtful if modular exponentation is faster than regular modulo calculation.
TC of modular exponentation-O(logN)
TC of regular modulo exponentation-O(N)
I’ve compared both methods in Python, I’ve got the following results

from time import time
def mod(x,y,m):
    res=1
    x=x%m
    c=0
    if x==0:
        return 0
    while(y>0):
        if y%2==1:
            res=(res*x)%m
        y=y>>1
        x=(x*x)%m
        c+=1
    return res

x,y,m=17,100,10**9+7

t1=time()
a1=(x**y)%m
print("Time for calculating regular modulo(ms)->",time()-t1)

t2=time()
a2=mod(x,y,m)
print("Using modular exponentation(ms)->",time()-t2)

I am getting the following output:-

Time for calculating regular modulo(ms)-> 3.0994415283203125e-06
Using modular exponentation(ms)-> 4.5299530029296875e-06

Can anyone clear my doubt

2

Firstly, Formatting.

Secondly, That’s because y is small. Use y=10^7 . Also pow(x,y,m) uses modular exponentiation. You don’t need to write it yourself.

3

Thank you. This cleared my doubt.

4

You didn’t format, though…