a nice exercise to do can be this problem : http://www.codechef.com/MARCH09/problems/A4/ , it deals with both cases, first and last k digits and can be performed within O(log n)
On Sun, Feb 7, 2010 at 3:58 AM, Shashwat Anand <anand.shash...@gmail.com>wrote: > 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
