## 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 AlgorithmIn 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;
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 ; ## CombinationsThere 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
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 ( 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. |