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.
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.