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