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:

• `.` is a nop for timing purposes on Chuck's chips.
• `-` is a bitwise inversion, rather than subtraction.
• `or` is exclusive or instead of inclusive or

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.