fun exp 0 = 1
  | exp n = 2 * exp (n-1) ;

fun square (n:int) = n*n
fun double (n:int) = n+n

fun fast_exp 0 = 1
  | fast_exp n =
    if n mod 2 = 0 then
       square (fast_exp (n div 2))
    else
       double (fast_exp (n-1)) ;

fun iterative_fast_exp (0, a) = a
  | iterative_fast_exp (n, a) =
    if n mod 2 = 0 then
       iterative_fast_exp (n div 2, iterative_fast_exp (n div 2, a))
    else
       iterative_fast_exp (n-1, 2*a) ;

fun generalized_iterative_fast_exp (b, 0, a) = a
  | generalized_iterative_fast_exp (b, n, a) =
    if n mod 2 = 0 then
       generalized_iterative_fast_exp (b*b, n div 2, a)
    else
       generalized_iterative_fast_exp (b, n-1, b*a) ;

fun gcd (m:int, 0):int = m
  | gcd (0, n:int):int = n
  | gcd (m:int, n:int):int =
    if m>n then gcd (m mod n, n) else gcd (m, n mod m) ;

fun ggcd (0, n) = (n, 0, 1)
  | ggcd (m, 0) = (m, 1, 0)
  | ggcd (m, n) =
    if m>n then
       let
           val (d, a, b) = ggcd (m mod n, n)
       in
           (d, a, b - a*(m div n))
       end
    else
       let
           val (d, a, b) = ggcd (m, n mod m)
       in
           (d, a - b*(n div m), b)
       end

exception GCD_ERROR

fun checked_gcd (m, n) =
    let
        val (d, a, b) = ggcd (m, n)
    in
        if m mod d = 0 andalso n mod d = 0 andalso d = a*m+b*n then
           d
        else
           raise GCD_ERROR
    end