Calculate modulo in LC3

Question

How do you calculate N mod K in LC3? N comes from mem location x3100 and K comes from mem location x3101 and you want to store the result of N mod K in x3102

Answer 1

How do you calculate N mod K in LC3?

One way to do modulo is to do division by repetitive subtraction; this will yield a quotient and a remainder (the modulo).  In the following N is the dividend and K is the divisor.

Start a tally at 0; this tally will count how many times we can subtract the divisor from the dividend.

Then loop, as long as the dividend is greater or equal to the divisor, subtract the latter from the former putting the result back into the dividend, and since we were able to do the subtraction, add one to the quotient.  Note that the dividend is updated each iteration of the loop (it gets smaller each iteration).

When this loop finishes, the tally is the quotient, and the (updated) dividend is the remainder leftover that could not be subtracted.  (The remainder will be less than the divisor.  If it is zero the division was "even"/exact.)

---

This algorithm handles unsigned numbers (dividend and divisor).  It can be adapted for signed, usually by negating negative numbers and then doing the unsigned division algorithm (and negating the answers as appropriate).

---

This is probably the simplest way to do division/modulo on a processor that doesn't have multiply or divide.  Let's note that in the pathological case (65535/1) it will iterate 65535 times, which is a lot of iteration.

The study of integer division on processors that don't have good built-in divide operations is rather large.  I believe that using the divide step operation, we can complete any division in 16 iterations (for 16 bit words), more complicated, of course, considering the LC-3 does not have right shift.  (The idea is to subtract large chunks of the divisor multiplied by ever smaller powers of 2, i.e. long division in binary.)  Further, when the divisor is known to be constant, there are lots of trick as well (e.g. dividing by, say 10, or by 3).