Last M digits of expression A^N

[mukesh tiwari]

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.

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

 

[Mark Dickinson]

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.

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

The built-in pow function does exactly this, if you give it three
arguments:
10L

(Though this won't work for negative N.)

Mark

 

[Gerald Britton]

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.

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

http://docs.python.org/3.1/library/decimal.html#decimal.Context.power

 

[Mensanator]

The built-in pow function does exactly this,

It doesn't do 'exactly' that. M is the number of digits.
If you want 17 digits, the third number should 10**17.
Using 17 directly will give you a 2-digit answer as shown.

Try this instead:

 

[Dave Angel]

How do you arrive at log N as the performance number?

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

 

[Mark Dickinson]

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.

By the way, given that your M is fairly tiny compared with A and N, a
little bit of elementary number theory (e.g., Euler's theorem) could
save you a lot of time here. For example,

pow(a, n, 10**5)

is equivalent to

pow(a, 5 + (n - 5) % 40000, 10**5)

for any n >= 5. Not sure if this is the kind of thing you're looking
for.