# Entering the Third Dimension

Colon definitions typically contain both control flow operators and stack flow
operators. In order to represent both these aspects of a program graphically we
need to move from two dimensional flowcharts to three dimensions. This is
illustrated here with two examples.

### Euclid's Algorithm

In his seminal work "The Art of Computer Programming" D E Knuth devotes a
great deal of space to analysing this algorithm. In volume 1, page 2 he describes
it thus;

**Algorithm E.** *(Euclid's algorithm). *given two positive integers
*m *and *n *, find their greatest common divisor, i.e., the largest
positive integer which evenly divides both *m *and *n*.
** E1.** [Find remainder.] Divide *m *by *n *and let *r * be
the remainder. (We will have 0<=*r*<*n*.)

**E2.** [Is it zero?] if *r *= 0, the algorithm terminates; *n *
is the answer.

**E3.** [Interchange.] Set *m *<- *n*, *n *<- *r *,
and go back to step E1.

And here is the Forth code to do this; (the test for zero has been placed before
the division, so that it handles an argument of zero predictably).
: GCD ( n n--n) BEGIN DUP WHILE TUCK MOD REPEAT DROP ;

### Combinations

There are many possible algorithms to find the number of combinations of r
items from n objects ( nCr). The two most commonly quoted are
n!/r!(n-r)!

and Vandermonde's theorem;
nCr = nC(r-1) + (n-1)Cr

The former has a problem in that very large intermediate results can occur, even
when the result is very small. The latter does not suffer from this, but is
computationally very inefficient.
Therefore we choose to use the following recurrance, which suffers from neither
of those setbacks;

r=0 --> nCr = 1
r>0 --> nCr = nC(r-1)(n-r+1)/r

This translates in Forth into;
: (COMBS) ( n r--c) DUP IF 2DUP 1- RECURSE
-ROT TUCK - 1+
SWAP */
ELSE 2DROP 1
THEN ;

Where the word `RECURSE` indicates that the definition is called
recursively.
One refinement we can make to this is to note that the function is symmetrical,
i.e. that nCr = nC(n-r), so we can reduce the amount of work that the word may
do by choosing to compute the smaller of r and (n-r). To do this we can call
`(COMBS)`from another word that does the test. (Having interactively
tested `(COMBS)` first, naturally.)

: COMBS ( n r--c) 2DUP - MIN (COMBS) ;

This concludes the body of this introduction to Forth. In the
last section we will mention some of the aspects of
Forth not covered here, and give some pointers to other information about Forth.
Or, if you prefer, you may return to the
contents page.