' Greatest common divisor
PROGRAM "gcddemo"
VERSION "0.001"

DECLARE FUNCTION Entry()
DECLARE FUNCTION GcdRecursive(u&, v&)
DECLARE FUNCTION GcdIterative(u&, v&)
DECLARE FUNCTION GcdBinary(u&, v&)

FUNCTION Entry()
  m& = 49865
  n& = 69811
  PRINT "GCD("; LTRIM$(STR$(m&)); ","; n&; "):"; GcdIterative(m&, n&); " (iterative)"
  PRINT "GCD("; LTRIM$(STR$(m&)); ","; n&; "):"; GcdRecursive(m&, n&); " (recursive)"
  PRINT "GCD("; LTRIM$(STR$(m&)); ","; n&; "):"; GcdBinary (m&, n&); " (binary)"
END FUNCTION

FUNCTION GcdRecursive(u&, v&)
  IF u& MOD v& <> 0 THEN
    RETURN GcdRecursive(v&, u& MOD v&)
  ELSE
    RETURN v&
  END IF
END FUNCTION

FUNCTION GcdIterative(u&, v&)
  DO WHILE v& <> 0
    t& = u&
    u& = v&
    v& = t& MOD v&
  LOOP
  RETURN ABS(u&)
END FUNCTION

FUNCTION GcdBinary(u&, v&)
  u& = ABS(u&)
  v& = ABS(v&)
  IF u& < v& THEN
    t& = u&
    u& = v&
    v& = t&
  END IF
  IF v& = 0 THEN
    RETURN u&
  ELSE
    k& = 1
    DO WHILE (u& MOD 2 = 0) && (v& MOD 2 = 0)
      u& = u& >> 1
      v& = v& >> 1
      k& = k& << 1
    LOOP
    IF u& MOD 2 = 0 THEN
      t& = u&
    ELSE
      t& = -v&
    END IF
    DO WHILE t& <> 0
      DO WHILE t& MOD 2 = 0
        t& = t& \ 2
      LOOP
      IF t& > 0 THEN
        u& = t&
      ELSE
        v& = -t&
      END IF
      t& = u& - v&
    LOOP
    RETURN u& * k&
  END IF
END FUNCTION

END PROGRAM