gcd.ml

(* compute GCD. playing with OCaml *)

let rec gcd n m = 
    if m = 0 then 
        n 
    else 
        if n > m 
        then 
            gcd (n-m) m
        else 
            gcd n (m-n)
;;

let rec ogcd n m = match n,m with 
      _,0 -> n
    | n,m when n > m -> ogcd (n-m) m 
    | n,m -> ogcd n (m-n) 
;;

let rec rgcd a b = 
    let r = a mod b in 
    if r = 0 then 
        b 
    else 
        rgcd b r
;;

let reduce n m = 
    let f = gcd n m in 
    (n/f, m/f)
;;