monkeys paw wrote:
<div class="moz-text-flowed" style="font-family: -moz-fixed">mukesh
tiwari wrote:
Hello everyone. I am kind of new to python so pardon me if i sound
stupid.
I have to find out the last M digits of expression.One thing i can do
is (A**N)%M but my A and N are too large (10^100) and M is less than
10^5. The other approach was repeated squaring and taking mod of
expression. Is there any other way to do this in python more faster
than log N.
How do you arrive at log N as the performance number?
def power(A,N,M):
ret=1
while(N):
if(N%2!=0):ret=(ret*A)%M
A=(A*A)%M
N=N//2
return ret
Because the N= N/2 operation in the loop means that the number of loops
is equal to the number of bits in N, or the log-base-2 of N.
DaveA
--
http://mail.python.org/mailman/listinfo/python-list
