Last M digits of expression A^N

[Shashwat Anand]

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.shashwat at 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 <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/c68d4b23/attachment-0001.html>