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-... HTH, hvr