Greatest common divisor

You are encouraged to solve this task according to the task description, using any language you may know.
Task

Find the greatest common divisor   (GCD)   of two integers.


Greatest common divisor   is also known as   greatest common factor (gcf)   and   greatest common measure.



Related task

   least common multiple.


See also

   MathWorld entry:   greatest common divisor.
   Wikipedia entry:     greatest common divisor.


(********************************************************************)
(*
 
  GCD of two integers, by Stein’s algorithm:
  https://en.wikipedia.org/w/index.php?title=Binary_GCD_algorithm&oldid=1072393147
 
  This is an implementation without proofs of anything.
 
  The implementations shown here require the GCC builtin functions
  for ‘count trailing zeros’. If your C compiler is GCC or another
  that supports those functions, you are fine. Otherwise, one could
  easily substitute other C code.
 
  Compile with ‘patscc -o gcd gcd.dats’.
 
*)
 
#define ATS_EXTERN_PREFIX "rosettacode_gcd_"
#define ATS_DYNLOADFLAG 0       (* No initialization is needed. *)
 
#include "share/atspre_define.hats"
#include "share/atspre_staload.hats"
 
(********************************************************************)
(*                                                                  *)
(* Declarations of the functions.                                   *)
(*                                                                  *)
 
(* g0uint_gcd_stein will be the generic template function for
   unsigned integers. *)
extern fun {tk : tkind}
g0uint_gcd_stein :
  (g0uint tk, g0uint tk) -<> g0uint tk
 
(* g0int_gcd_stein will be the generic template function for
   signed integers, giving an unsigned result. *)
extern fun {tk_signed, tk_unsigned : tkind}
g0int_gcd_stein :
  (g0int tk_signed, g0int tk_signed) -<> g0uint tk_unsigned
 
(* Let us call these functions ‘gcd_stein’ or just ‘gcd’. *)
overload gcd_stein with g0uint_gcd_stein
overload gcd_stein with g0int_gcd_stein
overload gcd with gcd_stein
 
(********************************************************************)
(*                                                                  *)
(* The implementations.                                             *)
(*                                                                  *)
 
%{^
 
/*
 
  We will need a ‘count trailing zeros of a positive number’ function,
  but this is not provided in the ATS prelude. Here are
  implementations using GCC builtin functions. For fast alternatives
  in standard C, see
  https://www.chessprogramming.org/index.php?title=BitScan&oldid=22495#Trailing_Zero_Count
 
*/
 
ATSinline() atstype_uint
rosettacode_gcd_g0uint_ctz_uint (atstype_uint x)
{
  return __builtin_ctz (x);
}
 
ATSinline() atstype_ulint
rosettacode_gcd_g0uint_ctz_ulint (atstype_ulint x)
{
  return __builtin_ctzl (x);
}
 
ATSinline() atstype_ullint
rosettacode_gcd_g0uint_ctz_ullint (atstype_ullint x)
{
  return __builtin_ctzll (x);
}
 
%}
 
extern fun g0uint_ctz_uint : uint -<> int = "mac#%"
extern fun g0uint_ctz_ulint : ulint -<> int = "mac#%"
extern fun g0uint_ctz_ullint : ullint -<> int = "mac#%"
 
(* A generic template function for ‘count trailing zeros’ of
   non-dependent unsigned integers. *)
extern fun {tk : tkind} g0uint_ctz : g0uint tk -<> int
 
(* Link the implementations to the template function. *)
implement g0uint_ctz<uint_kind> (x) = g0uint_ctz_uint x
implement g0uint_ctz<ulint_kind> (x) = g0uint_ctz_ulint x
implement g0uint_ctz<ullint_kind> (x) = g0uint_ctz_ullint x
 
(* Let one call the function simply ‘ctz’. *)
overload ctz with g0uint_ctz
 
(* Now the actual implementation of g0uint_gcd_stein, the template
   function for the gcd of two unsigned integers. *)
implement {tk}
g0uint_gcd_stein (u, v) =
  let
    (* Make ‘t’ a shorthand for the unsigned integer type. *)
    typedef t = g0uint tk
 
    (* Use this macro to fake proof that an int is non-negative. *)
    macdef nonneg (n) = $UNSAFE.cast{intGte 0} ,(n)
 
    (* Looping is done by tail recursion. There is no proof
       the function terminates; this fact is indicated by
       ‘<!ntm>’. *)
    fun {tk : tkind}
    main_loop (x_odd : t, y : t) :<!ntm> t =
      let
        (* Remove twos from y, giving an odd number.
           Note gcd(x_odd,y_odd) = gcd(x_odd,y). *)
        val y_odd = (y >> nonneg (ctz y))
      in
        if x_odd = y_odd then
          x_odd
        else
          let
            (* If y_odd < x_odd then swap x_odd and y_odd.
               This operation does not affect the gcd. *)
            val x_odd = min (x_odd, y_odd)
            and y_odd = max (x_odd, y_odd)
          in
            main_loop (x_odd, y_odd - x_odd)
          end
      end
 
    fn
    u_and_v_both_positive (u : t, v : t) :<> t =
      let
        (* n = the number of common factors of two in u and v. *)
        val n = ctz (u lor v)
 
        (* Remove the common twos from u and v, giving x and y. *)
        val x = (u >> nonneg n)
        val y = (v >> nonneg n)
 
        (* Remove twos from x, giving an odd number.
           Note gcd(x_odd,y) = gcd(x,y). *)
        val x_odd = (x >> nonneg (ctz x))
 
        (* Run the main loop, but pretend it is proven to
           terminate. Otherwise we could not write ‘<>’ above,
           telling the ATS compiler that we trust the function
           to terminate. *)
        val z = $effmask_ntm (main_loop (x_odd, y))
      in
        (* Put the common factors of two back in. *)
        (z << nonneg n)
      end
 
    (* If v < u then swap u and v. This operation does not
       affect the gcd. *)
    val u = min (u, v)
    and v = max (u, v)
  in
    if iseqz u then
      v
    else
      u_and_v_both_positive (u, v)
  end
 
(* The implementation of g0int_gcd_stein, the template function for
   the gcd of two signed integers, giving an unsigned result. *)
implement {signed_tk, unsigned_tk}
g0int_gcd_stein (u, v) =
  let
    val abs_u = $UNSAFE.cast{g0uint unsigned_tk} (abs u)
    val abs_v = $UNSAFE.cast{g0uint unsigned_tk} (abs v)
  in
    g0uint_gcd_stein<unsigned_tk> (abs_u, abs_v)
  end
 
(********************************************************************)
(* A demonstration program. *)
 
implement
main0 () =
  begin
    (* Unsigned integers. *)
    assertloc (gcd (0U, 10U) = 10U);
    assertloc (gcd (9UL, 6UL) = 3UL);
    assertloc (gcd (40902ULL, 24140ULL) = 34ULL);
 
    (* Signed integers. *)
    assertloc (gcd (0, 10) = gcd (0U, 10U));
    assertloc (gcd (~10, 0) = gcd (0U, 10U));
    assertloc (gcd (~6L, ~9L) = 3UL);
    assertloc (gcd (40902LL, 24140LL) = 34ULL);
    assertloc (gcd (40902LL, ~24140LL) = 34ULL);
    assertloc (gcd (~40902LL, 24140LL) = 34ULL);
    assertloc (gcd (~40902LL, ~24140LL) = 34ULL);
    assertloc (gcd (24140LL, 40902LL) = 34ULL);
    assertloc (gcd (~24140LL, 40902LL) = 34ULL);
    assertloc (gcd (24140LL, ~40902LL) = 34ULL);
    assertloc (gcd (~24140LL, ~40902LL) = 34ULL)
  end
 
(********************************************************************)