Yes, it can be done. Have a look at : <a href="http://en.wikipedia.org/wiki/Modular_exponentiation">http://en.wikipedia.org/wiki/Modular_exponentiation</a><br>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.<br>
Have a look at this problem : <a href="https://www.spoj.pl/problems/LASTDIG/">https://www.spoj.pl/problems/LASTDIG/</a><br>as you can see ( <a href="https://www.spoj.pl/status/LASTDIG,l0nwlf/">https://www.spoj.pl/status/LASTDIG,l0nwlf/</a> )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.<br>
<br>here are my solutions :<br>first one (hand-coded):<br><br><pre class="py"><ol><li><div class="de1"><span class="kw1">def</span> <span class="kw1">pow</span><span class="br0">(</span>a, b<span class="br0">)</span>:</div>
</li><li><div class="de1"> <span class="kw1">if</span><span class="br0">(</span> <span class="kw1">not</span> b<span class="br0">)</span>:</div></li><li><div class="de1"> <span class="kw1">return</span> <span class="nu0">1</span></div>
</li><li><div class="de1"> <span class="kw1">if</span><span class="br0">(</span> b & <span class="nu0">1</span> <span class="br0">)</span>:</div></li><li class="li2"><div class="de2"> <span class="kw1">return</span> <span class="br0">(</span> <span class="kw1">pow</span><span class="br0">(</span> a, b - <span class="nu0">1</span> <span class="br0">)</span> * a <span class="br0">)</span> % <span class="nu0">10</span></div>
</li><li> </li><li><div class="de1"> tmp = <span class="kw1">pow</span><span class="br0">(</span> a, b / <span class="nu0">2</span> <span class="br0">)</span></div></li><li><div class="de1"> <span class="kw1">return</span> <span class="br0">(</span> tmp * tmp <span class="br0">)</span> % <span class="nu0">10</span>;</div>
</li><li><div class="de1"> </div></li><li class="li2"><div class="de2"><span class="kw1">for</span> i <span class="kw1">in</span> <span class="kw1">xrange</span><span class="br0">(</span><span class="kw1">input</span><span class="br0">(</span><span class="br0">)</span><span class="br0">)</span>:</div>
</li><li><div class="de1"> a,b = <span class="br0">[</span> <span class="kw1">int</span><span class="br0">(</span>x<span class="br0">)</span> <span class="kw1">for</span> x <span class="kw1">in</span> <span class="kw1">raw_input</span><span class="br0">(</span><span class="br0">)</span>.<span class="me1">split</span><span class="br0">(</span>' '<span class="br0">)</span><span class="br0">]</span></div>
</li><li><div class="de1"> <span class="kw1">print</span><span class="br0">(</span> <span class="kw1">pow</span><span class="br0">(</span> a % <span class="nu0">10</span>, b <span class="br0">)</span> <span class="br0">)</span> <br>
</div></li></ol></pre><br>second one (pow()):<br><br><pre class="py"><ol><li><div class="de1"><span class="kw1">for</span> i <span class="kw1">in</span> <span class="kw1">range</span><span class="br0">(</span><span class="kw1">int</span><span class="br0">(</span><span class="kw1">raw_input</span><span class="br0">(</span><span class="br0">)</span><span class="br0">)</span><span class="br0">)</span>:</div>
</li><li><div class="de1"> a,b = <span class="br0">[</span><span class="kw1">int</span><span class="br0">(</span>x<span class="br0">)</span> <span class="kw1">for</span> x <span class="kw1">in</span> <span class="kw1">raw_input</span><span class="br0">(</span><span class="br0">)</span>.<span class="me1">split</span><span class="br0">(</span><span class="br0">)</span><span class="br0">]</span></div>
</li><li><div class="de1"> <span class="kw1">print</span> <span class="kw1">pow</span> <span class="br0">(</span>a,b,<span class="nu0">10</span><span class="br0">)</span></div></li><li> </li></ol></pre><br>HTH<br>
~l0nwlf<br>
<br>On Sun, Feb 7, 2010 at 2:32 AM, monkeys paw <span dir="ltr"><<a href="mailto:user@example.net">user@example.net</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div class="im">mukesh tiwari wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Hello everyone. I am kind of new to python so pardon me if i sound<br>
stupid.<br>
I have to find out the last M digits of expression.One thing i can do<br>
is (A**N)%M but my A and N are too large (10^100) and M is less than<br>
10^5. The other approach was repeated squaring and taking mod of<br>
expression. Is there any other way to do this in python more faster<br>
than log N.<br>
</blockquote>
<br></div>
How do you arrive at log N as the performance number?<div><div></div><div class="h5"><br>
<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br>
def power(A,N,M):<br>
ret=1<br>
while(N):<br>
if(N%2!=0):ret=(ret*A)%M<br>
A=(A*A)%M<br>
N=N//2<br>
return ret<br>
</blockquote>
-- <br>
<a href="http://mail.python.org/mailman/listinfo/python-list" target="_blank">http://mail.python.org/mailman/listinfo/python-list</a><br>
</div></div></blockquote></div><br>