the following code does not run as fast as expected:
modexp a e n = if e <= 0 then 1 else
if even e
then mod (modexp a (div e 2) n * modexp a (div e 2) n) n
else mod (a * modexp a (e - 1) n) n
it gets only fast if written as:
modexp2 a e n = if e <= 0 then 1 else
if even e
then let d = modexp2 a (div e 2) n in mod (d * d) n
else mod (a * modexp2 a (e - 1) n) n
I wonder, why the common subexpression "modexp a (div e 2) n" is not
eliminated in the first case. Does CSE work at all?
For testing the exponent "e" should have at least 10 digits.
Cheers Christian
P.S. Other alternatives are slower, too
modexp1 a e n = if e <= 0 then 1 else
mod (a * modexp1 a (e - 1) n) n
modexp3 a e n = mod (a ^ e) n
_______________________________________________
Glasgow-haskell-users mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
