Assembly mod algorithm on processor with no division operator

Question

I need to implement a simple macro that finds the modulo of two numbers on a processor that doesn't have a division operator (think ARM). I could use division by repeated subtraction, but I don't know if this was the most efficient or easiest to work with.

Any suggestions? Code would be even more helpful. This particular class has us using a subset of SPARC, so most operations look like this: add r1, r2, rdest.

This particular assignment calls for checking that a mod b == 0 or that the remainder of the division is zero. So any hints or suggestions toward an efficient implementation would be most welcome.

Answer 1

No idea what exact operations you are limited to, but I'd think you'd do long division, something like this, in pseudo-code:

dividend = abs(dividend)
divisor = abs(divisor)
if divisor == 0,
    barf
remainder = dividend
next_multiple = divisor

do
    multiple = next_multiple
    next_multiple = left_shift(multiple, 1)
while next_multiple <= remainder && next_multiple > multiple

while multiple >= divisor,
    if multiple <= remainder,
        remainder = remainder - multiple
    multiple = right_shift(multiple, 1)

To actually calculate the quotient (or at least its absolute value), the last part would be something like:

quotient = 0
while multiple >= divisor,
    quotient = left_shift(quotient, 1);
    if multiple <= remainder,
        remainder = remainder - multiple
        quotient = quotient + 1
    multiple = right_shift(multiple, 1)

None of this is tested, and it is probably riddled with errors.