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?
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).
tmp > y of course. Also when the one/both of the oeprands are negative you have to use <= and/or + instead
>= not >
while becomes push(divisor); divisor += divisor; then you can replace divisor >>= 1 with divisor = pop();.Binary long division can solve the problem:
Example of 16 / 3 (in binary 100002 / 112):
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.
I've written division and multiplication functions in C and then I translated that code to MIPS.
I would guess that the division function that you wrote might already compute the modulus x%N by the end of the algorithm. For this reason high-level architectures like x86 provide assembly instructions (e.g. divl) that return both x/N and x%N at the same time: often whatever algorithm you use to calculate one automatically gives the other, so you can kill two birds with one stone if both are needed at the same time.
Also, ff you've written division and multiplication functions then you have everything you need to compute a modulus, because x%N == x - N*( x/N ). So in the worst case, if you want to compute x%N using only addition and subtraction, and you know how to multiply and divide using only addition and subtraction, then you can use the above formula to get x%N. That being said, you can do better than this e.g. via long division as already suggested.
Although not as efficient as the implementation above, here is a quick recursive solution in JavaScript that you can give if ever asked this question during an interview. Note this also supports negative and decimal inputs.
var modulo = function(x, y) {
y = Math.abs(y);
return (x < y) ? x : modulo(x - y, y);
};
console.log(modulo(12, 5)); //2
console.log(modulo(10, 2)); //0
console.log(modulo(4, 10)); //4
console.log(modulo(4, 2.4)); //1.6
console.log(modulo(-1, 10)); //-1
console.log(modulo(10, -3)); //1
console.log(modulo(10, -4)); //2
console.log(modulo(10, -3)); //1
