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.


 
 [Greatest common divisor for Rosetta Code.
  Program for EDSAC, Initial Orders 2.]
 
 [Library subroutine R2. Reads positive integers during input of orders,
    and is then overwritten (so doesn't take up any memory).
  Negative numbers can be input by adding 2^35.
  Each integer is followed by 'F', except the last is followed by '#TZ'.]
            T   45 K [store address in location 45
                    values are then accessed by code letter H]
            P  220 F [<------ address here]
  GKT20FVDL8FA40DUDTFI40FA40FS39FG@S2FG23FA5@T5@E4@E13Z
            T     #H  [Tell R2 the storage location defined above]
 
 [Integers to be read by R2. First item is count, then pairs for GCD algo.]
  4F 1066F 2019F 1815F 1914F 103785682F 167928761F 109876463F 177777648#TZ
 
 [----------------------------------------------------------------------
  Library subroutine P7.
  Prints long strictly positive integer at 0D.
  10 characters, right justified, padded left with spaces.
  Closed, even; 35 storage locations; working position 4D.]
            T   56 K
  GKA3FT26@H28#@NDYFLDT4DS27@TFH8@S8@T1FV4DAFG31@SFLDUFOFFFSFL4F
  T4DA1FA27@G11@XFT28#ZPFT27ZP1024FP610D@524D!FO30@SFL8FE22@
 
 [---------------------------------------------------------------
  Subroutine to return GCD of two non-negative 35-bit integers.
  Input:  Integers at 4D, 6D.
  Output: GCD at 4D; changes 6D.
  41 locations; working location 0D.]
            T  100 K
            G      K
            A    3 F  [plant link]
            T   39 @
            S    4 D  [test for 4D = 0]
            E   37 @  [if so, quick exit, GCD = 6D]
            T   40 @  [clear acc]
      [5]   A    4 D  [load divisor]
      [6]   T      D  [initialize shifted divisor]
            A    6 D  [load dividend]
            R      D  [shift 1 right]
            S      D  [shifted divisor > dividend/2 yet?]
            G   15 @  [yes, start subtraction]
            T   40 @  [no, clear acc]
            A      D  [shift divisor 1 more]
            L      D
            E    6 @  [loop back (always, since acc = 0)]
     [15]   T   40 @  [clear acc]
     [16]   A    6 D  [load remainder (initially = dividend)]
            S      D  [trial subtraction]
            G   20 @  [skip if can't subtract]
            T    6 D  [update remainder]
     [20]   T   40 @  [clear acc]
            A    4 D  [load original divisor]
            S      D  [is shifted divisor back to original?]
            E   29 @  [yes, jump out with acc = 0]
            T   40 @  [no, clear acc]
            A      D  [shift divisor 1 right]
            R      D
            T      D
            E   16 @  [loop back (always, since acc = 0)]
         [Here when finished dividing 6D by 4D.
          Remainder is at 6D; acc = 0.]
     [29]   S    6 D  [test for 6D = 0]
            E   39 @  [if so, exit with GCD in 4D]
            T      D  [else swap 4D and 6D]
            A    4 D
            T    6 D
            S      D
            T    4 D
            E    5 @  [loop back]
     [37]   A    6 D  [here if 4D = 0 at start; GCD is 6D]
            T    4 D  [return in 4D as GCD]
     [39]   E      F
     [40]   P      F  [junk word, to clear accumulator]
 
 [----------------------------------------------------------------------
  Main routine]
            T  150 K
            G      K
  [Variable]
      [0]   P      F
  [Constants]
      [1]   P      D [single-word 1]
      [2]   A    2#H [order to load first number of first pair]
      [3]   P    2 F [to inc addresses by 2]
      [4]   #      F [figure shift]
      [5]   K 2048 F [letter shift]
      [6]   G      F [letters to print 'GCD']
      [7]   C      F
      [8]   D      F
      [9]   V      F [equals sign (in figures mode)]
     [10]   !      F [space]
     [11]   @      F [carriage return]
     [12]   &      F [line feed]
     [13]   K 4096 F [null char]
         [Enter here with acc = 0]
     [14]   O    4 @ [set teleprinter to figures]
            S      H [negative of number of pairs]
            T      @ [initialize counter]
            A    2 @ [initial load order]
     [18]   U   23 @ [plant order to load 1st integer]
            U   32 @
            A    3 @ [inc address by 2]
            U   28 @ [plant order to load 2nd integer]
            T   34 @
     [23]   A     #H [load 1st integer (order set up at runtime)]
            T      D [to 0D for printing]
            A   25 @ [for return from print subroutine]
            G   56 F [print 1st number]
            O   10 @ [followed by space]
     [28]   A     #H [load 2nd integer (order set up at runtime)]
            T      D [to 0D for printing]
            A   30 @ [for return from print subroutine]
            G   56 F [print 2nd number]
     [32]   A     #H [load 1st integer (order set up at runtime)]
            T    4 D [to 4D for GCD subroutine]
     [34]   A     #H [load 2nd integer (order set up at runtime)]
            T    6 D [to 6D for GCD subroutine]
     [36]   A   36 @ [for return from subroutine]
            G  100 F [call subroutine for GCD]
         [Cosmetic printing, add '  GCD = ']
            O   10 @
            O   10 @
            O    5 @
            O    6 @
            O    7 @
            O    8 @
            O    4 @
            O   10 @
            O    9 @
            O   10 @
            A    4 D [load GCD]
            T      D [to 0D for printing]
            A   50 @ [for return from print subroutine]
            G   56 F [print GCD]
            O   11 @ [followed by new line]
            O   12 @
          [On to next pair]
            A      @ [load negative count of c.f.s]
            A    1 @ [add 1]
            E   62 @ [exit if count = 0]
            T      @ [store back]
            A   23 @ [order to load first of pair]
            A    3 @ [inc address by 4 for next c.f.]
            A    3 @
            G   18 @ [loop back (always, since 'A' < 0)]
     [62]   O   13 @  [null char to flush teleprinter buffer]
            Z      F  [stop]
            E   14 Z  [define entry point]
            P      F  [acc = 0 on entry]
 