Project Euler 188 (0.3 s)

pr188.hs

moddule = 10 ^ 8
lastDigits x = x `mod` moddule

fastPow :: Integer -> Integer -> Integer -> Integer
fastPow base 1 m = mod base m 
fastPow base pow m | even pow = mod ((fastPow base (div pow 2) m) ^ 2) m
                   | odd  pow = mod ((fastPow base (div (pow-1) 2) m) ^ 2 * base) m
                   
tetration a 1 = lastDigits a
tetration a k = lastDigits ( fastPow a' (tetration a' k') moddule)
    where a' = lastDigits a
          k' = lastDigits k - 1

main = print $ tetration 1777 1855