divisioninteger-divisionforthcolor-forth

How does the colorForth /mod algorithm work?


I've been looking at Chuck Moore's colorForth recently, and I came upon this snippet of code (rendered in a traditional syntax):

: /mod for begin over over . + -if drop 2* [ swap ] next ; then over or or - 2* - next ;

With the following explanation:

   Divide operation: trial subtract and shift in either 0 or 1

I'm really confused as to how this implements the full division operation. I realize the 2* shifts in a 0, the - 2* - shifts in a 1, and over or or implements a nip operation. I also understand the mixed loops and if combo.

Here's where I am falling short.

  1. It seems to be expecting two items on the stack, the numerator and the denominator, which makes sense. However, the initial for pushes the TOS to the return stack, leaving only one item on the return stack. The over over operation works with two values present however, so I'm not sure what is happening.
  2. He mentions subtraction, but there is no inversion happening, except for the - 2* - branch, which is already mentioned as shifting in a 1.
  3. I'm not sure how you can construct the quotient bit by bit by only shifting in 1s or 0s (into the divisor?).

Some thoughts:

  1. Maybe it depends on the particular word size of the chip Chuck was programming and the rollover after adding enough times
  2. Maybe there is a preamble missing that inverts the denominator, resulting in the subtraction that is mentioned on every loop.

Some idiosyncrasies between colorForth and other Forths:

For additional information, Here's the source: Description of function and use of colorForth opcodes


Solution

  • Just for reference: the excellent answer on this question was posted in comp.lang.forth by Ulrich Hoffmann.


    Please edit this post to make it more detailed.