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.


/* NetRexx */
options replace format comments java crossref symbols nobinary
 
numeric digits 2000
runSample(arg)
return
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- Euclid's algorithm - iterative implementation
method gcdEucidI(a_, b_) public static
  loop while b_ > 0
    c_ = a_ // b_
    a_ = b_
    b_ = c_
    end
  return a_
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- Euclid's algorithm - recursive implementation
method gcdEucidR(a_, b_) public static
  if b_ \= 0 then a_ = gcdEucidR(b_, a_ // b_)
  return a_
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method runSample(arg) private static
  -- pairs of numbers, each number in the pair separated by a colon, each pair separated by a comma
  parse arg tests
  if tests = '' then
    tests = '0:0, 6:4, 7:21, 12:36, 33:77, 41:47, 99:51, 100:5, 7:23, 1989:867, 12345:9876, 40902:24140, 49865:69811, 137438691328:2305843008139952128'
 
  -- most of what follows is for formatting
  xiterate = 0
  xrecurse = 0
  ll_ = 0
  lr_ = 0
  lgi = 0
  lgr = 0
  loop i_ = 1 until tests = ''
    xiterate[0] = i_
    xrecurse[0] = i_
    parse tests pair ',' tests
    parse pair l_ ':' r_ .
 
    -- get the GCDs
    gcdi = gcdEucidI(l_, r_)
    gcdr = gcdEucidR(l_, r_)
 
    xiterate[i_] = l_ r_ gcdi
    xrecurse[i_] = l_ r_ gcdr
    ll_ = ll_.max(l_.strip.length)
    lr_ = lr_.max(r_.strip.length)
    lgi = lgi.max(gcdi.strip.length)
    lgr = lgr.max(gcdr.strip.length)
    end i_
  -- save formatter sizes in stems
  xiterate[-1] = ll_ lr_ lgi
  xrecurse[-1] = ll_ lr_ lgr
 
  -- present results
  showResults(xiterate, 'Euclid''s algorithm - iterative')
  showResults(xrecurse, 'Euclid''s algorithm - recursive')
  say
  if verifyResults(xiterate, xrecurse) then
    say 'Success: Results of iterative and recursive methods match'
  else
    say 'Error:   Results of iterative and recursive methods do not match'
  say
  return
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method showResults(stem, title) public static
  say
  say title
  parse stem[-1] ll lr lg
  loop v_ = 1 to stem[0]
    parse stem[v_] lv rv gcd .
    say lv.right(ll)',' rv.right(lr) ':' gcd.right(lg)
    end v_
  return
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method verifyResults(stem1, stem2) public static returns boolean
  if stem1[0] \= stem2[0] then signal BadArgumentException
  T = (1 == 1)
  F = \T
  verified = T
  loop i_ = 1 to stem1[0]
    if stem1[i_] \= stem2[i_] then do
      verified = F
      leave i_
      end
    end i_
  return verified
 