## GCD

Tuesday, December 23, 2008

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:

```
IN: scratchpad USE: math
IN: scratchpad \ gcd help
```

To see how it is implemented:

```
IN: scratchpad USE: math
IN: scratchpad \ gcd see
```