Taking a number to a power and taking its mod
Hello, I've been trying to do a problem from SPOJ which requires me to find prime numbers in a range. I've been battling with several possibility, so far I have had no luck. I remember primality tests from college. So I looked up the one I knew: fermat's little theorem. It requires me to do this check: a^(p-1) `mod` p == 1 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? []'s Rafael
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
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
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
participants (2)
-
Herbert Valerio Riedel -
Rafael Almeida