<div dir="ltr">Interesting. I had a read on this wikipedia article as well: <a href="http://en.wikipedia.org/wiki/Modular_exponentiation">http://en.wikipedia.org/wiki/Modular_exponentiation</a><div><br></div><div>It gives us one important theorem: a*b `mod` m == (a*(b `mod` m)) `mod` m</div>

<div><br></div><div>That's what makes exponentiation by squaring so appealing. I wrote the function in a way that I found it easier to understand. Take a look:</div><div><br></div><div><div>powMod :: Integral a => a -> a -> a -> a</div>

<div>powMod _ _ 0 = 1 </div><div>powMod m x 1 = x `mod` m</div><div>powMod m x n </div><div>    | even n = powMod m modSquare (n`div`2)</div><div>    | otherwise = (x * powMod m modSquare ((n-1)`div`2)) `mod` m</div><div>

    where modSquare = x * (x `mod` m)</div></div><div class="gmail_extra"><br></div><div class="gmail_extra">That funcion does the pow-mod operation much quickier than doing n^k `mod` m. Unfortunately, nothing of those things actually solved the prime1 SPOJ problem :P</div>

<div class="gmail_extra"><br></div><div class="gmail_extra">I mostly gave it up, already. I liked learning those things, though :)<br><br><div class="gmail_quote">On Sun, Jun 15, 2014 at 12:34 PM, Herbert Valerio Riedel <span dir="ltr"><<a href="mailto:hvr@gnu.org" target="_blank">hvr@gnu.org</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Hello Rafael,<br>
<br>
On 2014-06-15 at 17:10:26 +0200, Rafael Almeida wrote:<br>
<br>
[...]<br>
<div class=""><br>
> However, taking a number to a large power is very slow. So it was even<br>
> worse than the solution I was already trying.<br>
><br>
> I'm not here for your guys to give me the solution. But I'm here to<br>
> understand how can I do that operation quickly. This wiki entry implements<br>
> powMod<br>
><br>
>     <a href="http://www.haskell.org/haskellwiki/Testing_primality" target="_blank">http://www.haskell.org/haskellwiki/Testing_primality</a><br>
><br>
> Calling that funcion with powMod 999999527 2 (999999527-1) is very fast.<br>
> What's going on? Can someone shed me some light?<br>
<br>
</div>One of the reason that powMod is very fast is because it avoids<br>
allocating large integer bignums by<br>
<br>
  <a href="http://en.wikipedia.org/wiki/Exponentiation_by_squaring" target="_blank">http://en.wikipedia.org/wiki/Exponentiation_by_squaring</a><br>
<br>
<br>
Just for the record (should you want an even more optimized powMod<br>
implementation): integer-gmp now exposes a few highly optimized Integer<br>
primitives, including a powMod:<br>
<br>
  <a href="http://hackage.haskell.org/package/integer-gmp-0.5.1.0/docs/GHC-Integer-GMP-Internals.html#v:powModInteger" target="_blank">http://hackage.haskell.org/package/integer-gmp-0.5.1.0/docs/GHC-Integer-GMP-Internals.html#v:powModInteger</a><br>


<br>
<br>
HTH,<br>
  hvr<br>
</blockquote></div><br></div></div>