Last M digits of expression A^N
Shashwat Anand
anand.shashwat at gmail.com
Sat Feb 6 23:28:44 CET 2010
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.html>
More information about the Python-list
mailing list