Write a function modulo using only addition / subtraction

Question

I am writing a library for MIPS , which I can not use IE's floating point module, division, multiplication.

I wrote separation and multiplication functions in C, and then transferred the code to MIPS .

However, I get lost on how to write a function to calculate modulo via C , using only addition or subtraction.

How to write a function to calculate a module using ONLY addition and subtraction?

Answer 1

Note. The following code snippets only work when both operands are positive. I omitted any handling of negative values, because the results of x % y , when one or both operands are negative, differ between different languages ​​and platforms. In the general case, you can simply calculate abs(x) % abs(y) and then do some conversion of the result.

---

The easiest way to calculate x % y using only addition and subtraction is to simply 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 rather inefficient. A more complex but faster method is to use binary long division . This is similar to regular long division, with the exception of the binary result, at each step - 0 or 1 instead of 0..9 . The basic approach to computing x % y with BLD is as follows:

 /* 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 of those found above: divisor <= INT_MAX/2 must stop the overflow in divisor <<= 1 when x > MAX_INT/2 .

Additionally, divmod , which gives you both a factor and a module in one calculation, looks almost accurate:

 /* 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 16/3 (in binary format 10000 2/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 say when to add 0 or 1 to the quotient: when the fragment from the previous calculation is less than divisor, then add 0; when the fragment is larger than the divisor, add 1.

Answer 3

I wrote separation and multiplication functions in C, and then I translated this code into MIPS.

I would suggest that the separation function you wrote might already compute the module x% N by the end of the algorithm. For this reason, higher-level architectures such as x86 provide assembly instructions (e.g. divl) that return x / N and x% N at the same time: often any algorithm you use to calculate automatically gives another, so you can kill two birds with one stone if both are needed at the same time.

In addition, if you wrote the separation and multiplication functions, then you have everything you need to calculate the module, because x%N == x - N*( x/N ) . Therefore, in the worst case scenario, if you want to calculate x% N using only addition and subtraction, and you know how to multiply and divide using only addition and subtraction, you can use the above formula to get x% N. However, you can do it better than this, for example, through a long division, as has already been suggested.

Answer 4

Although not as effective as the implementation above, here is a short recursive solution in JavaScript that you can give if you ever asked this question during an interview. Please note that 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