Common subexpression elemination (CSE)

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