GCD

The Factor IRC channel (#concatenative) can be a helpful resource when trying to learn how to code in Factor. Today, someone asked for help implementing the Greatest Common Denominator algorithm in Factor. There are a variety of algorithms for solving for the GCD of two numbers (and many are documented on the Wikipedia entry).

One possible solution uses the Euclidean Algorithm, which is implemented like so:

def gcd(a, b):
    if b = 0:
        return a
    else:
        return gcd(b, a % b)

We can translate that fairly directly to a recursive Factor word:

: gcd ( a b -- c )
    dup zero?
    [ drop ]
    [ [ mod ] keep swap gcd ]
    if ;

It's worth noting that Factor has a builtin word gcd in the math vocabulary calculating this problem.

To learn how it works:

( scratchpad ) USE: math

( scratchpad ) \ gcd help

To see how it is implemented:

( scratchpad ) USE: math

( scratchpad ) \ gcd see