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

Herbert Valerio Riedel hvr at gnu.org
Sun Jun 15 15:34:31 UTC 2014

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


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:



More information about the Haskell-Cafe mailing list