[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
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
> 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