72 lines
1.3 KiB
Text
72 lines
1.3 KiB
Text
' 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
|