Write a modulo function using only addition / subtraction

Question

I am writing a library for MIPS which I can't use floating point calculations I.E. modulos, division, multiplication.

I've written division and multiplication functions in C and then I translated that code to MIPS.

However I am lost on how to go about writing a function to calculate modulo via C using only addition or subtraction.

How can I write a function to calculate modulo using ONLY addition and subtraction?

Answer 1

Note: The following code snippets only work when both operands are positive. I have omitted any handling of negative values because the results of x % y when one or both operands are negative vary between different languages and platforms. In general you can just calculate abs(x) % abs(y) and then perform some transformation on the result.

---

The simplest way to calculate x % y using only only addition and subtraction is to just repeatedly subtract y until the remaining value is less than y:

/* Compute x mod y naively. */
int mod_basic(int x, int y) {
    int result = x;   
    while (result >= y)
        result -= y;

    return result;
}

However, this approach is fairly inefficient. A more complex but faster method is to use binary long division. This is similar to regular long division except in binary the result at each step is either 0 or 1 instead of 0..9. A basic approach to calculating x % y with BLD looks like this:

/* Compute x mod y using binary long division. */
int mod_bld(int x, int y)
{
    int modulus = x, divisor = y;

    while (divisor <= modulus && divisor <= INT_MAX/2)
        divisor <<= 1;

    while (modulus >= y) {
        while (divisor > modulus)
            divisor >>= 1;
        modulus -= divisor;
    }

    return modulus;
}

One gotcha in the above: the divisor <= INT_MAX/2 is necessary to stop overflow in divisor <<= 1 when x > MAX_INT/2.

Additionally divmod, which gives you both the quotient and the modulus in one calculation, looks almost exactly the same:

/* Compute divmod(x, y) using binary long division. */
void divmod(int x, int y, int *div, int *mod) {
    int quotient = 0, modulus = x, divisor = y;

    while (divisor <= modulus && divisor <= INT_MAX/2)
        divisor <<= 1;

    while (modulus >= y) {
        while (divisor > modulus) {
            divisor >>= 1;
            quotient <<= 1;
        }

        modulus -= divisor;
        quotient++;
    }

    while (divisor != y) {
        quotient <<= 1;
        divisor >>= 1;
    }

    *div = quotient;
    *mod = modulus;
}

Finally, note that if y is a power of 2, you can cheat. In this case x % y is just x & (y - 1).

Answer 2

Binary long division can solve the problem:

Example of 16 / 3 (in binary 10000₂ / 11₂):

 10000 | Quotient
 1     | 0         // 1 < 11 (append 0 to quotient, no effect)
 10    | 0         // 10 < 11 (append 0 to quotient, no effect)
 100   | 1         // 100 > 11, append 1 to quotient
- 11   | 
----   |
   1   |
   10  | 10        // 10 < 11, append 0 to quotient
   100 | 101       // 100 > 11, append 1 to quotient
 -  11 | 101
 ----- |
     1 | 101       // Quotient = 101, Remainder = 1

Since the result is in binary, you can immediately tell when to append 0 or 1 to the quotient: when the fragment from previous calculation is less than divisor, then append 0; when the fragment is larger than the divisor, append 1.