\ gcd.fs -- Compute greatest common divisor (for Gforth manual
\ General Loops Tutorial)
\ David Meyer <
[email protected]> 2010-03-17
: gcd ( n1 n2 -- n3 )
assert( 2dup 0<> swap 0<> and ) \ Parameters are non-zero
2dup < if swap then \ Put parameters in descending order
dup 1+ \ Initialize candidate divisor
begin
1- \ Decrement candidate divisor
2dup mod 0= \ n2 divisible by nc
2over drop 2over nip mod 0= and \ n1 div. by nc
over 1 = or \ nc = 1
until
nip nip
\ dup 1 = if \ Result is 0 for mutual primes
\ drop 0
\ then
;
: euclid ( n1 n2 -- n3 ) \ Calculate GCD with Euclid's
\ method
assert( 2dup 0<> swap 0<> and ) \ Parameters are non-zero
2dup < if swap then \ Put parameters in descending order
begin
dup 0<>
while
tuck mod
repeat
drop \ Simple!
;
