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.
: GCD ( n n--n) BEGIN DUP WHILE TUCK MOD REPEAT DROP ;
n!/r!(n-r)!and Vandermonde's theorem;
nCr = nC(r-1) + (n-1)CrThe 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)/rThis 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) ;
Or, if you prefer, you may return to the contents page.