Common subexpression elemination (CSE)

[Christian Maeder]

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