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 <u...@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 >
-- http://mail.python.org/mailman/listinfo/python-list