[Haskell-cafe] Taking a number to a power and taking its mod

[Rafael Almeida]

Interesting. I had a read on this wikipedia article as well:
http://en.wikipedia.org/wiki/Modular_exponentiation

It gives us one important theorem: a*b `mod` m == (a*(b `mod` m)) `mod` m

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:

powMod :: Integral a => a -> a -> a -> a
powMod _ _ 0 = 1
powMod m x 1 = x `mod` m
powMod m x n
    | even n = powMod m modSquare (n`div`2)
    | otherwise = (x * powMod m modSquare ((n-1)`div`2)) `mod` m
    where modSquare = x * (x `mod` m)

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

I mostly gave it up, already. I liked learning those things, though :)

On Sun, Jun 15, 2014 at 12:34 PM, Herbert Valerio Riedel <hvr at gnu.org>
wrote:

> Hello Rafael,
>
> On 2014-06-15 at 17:10:26 +0200, Rafael Almeida wrote:
>
> [...]
>
> > However, taking a number to a large power is very slow. So it was even
> > worse than the solution I was already trying.
> >
> > I'm not here for your guys to give me the solution. But I'm here to
> > understand how can I do that operation quickly. This wiki entry
> implements
> > powMod
> >
> >     http://www.haskell.org/haskellwiki/Testing_primality
> >
> > Calling that funcion with powMod 999999527 2 (999999527-1) is very fast.
> > What's going on? Can someone shed me some light?
>
> One of the reason that powMod is very fast is because it avoids
> allocating large integer bignums by
>
>   http://en.wikipedia.org/wiki/Exponentiation_by_squaring
>
>
> Just for the record (should you want an even more optimized powMod
> implementation): integer-gmp now exposes a few highly optimized Integer
> primitives, including a powMod:
>
>
> http://hackage.haskell.org/package/integer-gmp-0.5.1.0/docs/GHC-Integer-GMP-Internals.html#v:powModInteger
>
>
> HTH,
>   hvr
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140615/bf87c483/attachment.html>