Last M digits of expression A^N

[Shashwat Anand]

Yes, it can be done. Have a look at :
http://en.wikipedia.org/wiki/Modular_exponentiation
The algorithm is also mentioned in CLRS.I tried writing my own
modular-exponentiation code following CLRS but observed that python pow()
function is much more efficient.
Have a look at this problem : https://www.spoj.pl/problems/LASTDIG/
as you can see ( https://www.spoj.pl/status/LASTDIG,l0nwlf/ )my first
solution used algorithm hard-coded from CLRS which took 0.04 sec however
using pow() function directly improved the efficiency to 0.0 So I would
suggest to go for pow() unless you intend to learn modular exponentiation
algorithm for which hand-coding is a must.

here are my solutions :
first one (hand-coded):


   1. def pow(a, b):
   2.     if( not b):
   3. 	 return 1
   4.     if( b & 1 ):
   5. 	 return ( pow( a, b - 1 ) * a ) % 10
   6.
   7.     tmp = pow( a, b / 2 )
   8.     return ( tmp * tmp ) % 10;
   9.
   10. for i in xrange(input()):
   11.          a,b = [ int(x) for x in raw_input().split(' ')]
   12.          print( pow( a % 10, b ) )


second one (pow()):


   1. for i in range(int(raw_input())):
   2.         a,b = [int(x) for x in raw_input().split()]
   3.         print pow (a,b,10)
   4.


HTH
~l0nwlf

On Sun, Feb 7, 2010 at 2:32 AM, monkeys paw <user at example.net> wrote:

> 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
>>
> --
> http://mail.python.org/mailman/listinfo/python-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20100207/7c79bd7b/attachment-0001.html>