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

[Herbert Valerio Riedel]

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