# module without using %

• 01-16-2008
KIBO
module without using %
I remember there is a way to calculate the remainder without using the % operator but cant seem to find it. Anyone knows what it was?
• 01-16-2008
tabstop
Divide, and subtract (quotient*divisor)?
• 01-16-2008
PAragonxd
In what situation do you need any other means of getting the remainder than using the "%" ?
• 01-16-2008
anon
When you are asked to implement modulus without using &#37;?
• 01-16-2008
KIBO
I just read an implementation of the standard function div() and remembered there was a way without division and % to get the remainder. Was just curious what it was again
• 01-16-2008
PAragonxd
Without division? I don't see how that's possible, but if it is I'd like to see :P.
• 01-16-2008
anon

In addition, div() seems to calculate both a/b and a&#37;b. If you have done the first, the modulo can be found without doing the same division again. That is, div() is probably meant for optimizing cases where you need both results.
• 01-16-2008
Dino
int a = 10 ;
int b = 3 ;
int remainder = a - ((a/b)*b) ;
• 01-16-2008
CornedBee
You can always emulate integer division with subtraction and counting.
By doing so, you'll get the modulus automatically.
• 01-16-2008
iMalc
Quote:

Originally Posted by KIBO
I just read an implementation of the standard function div() and remembered there was a way without division and &#37; to get the remainder. Was just curious what it was again

If the number you're dividing by is small enough and is known at compile time, and the number being divided is no larger than half your register size, then to do fast division you can:
Multiply by the fixed-point inverse of the divisor, and then convert back to an integer. That's a multiply and a shift, instead of a division, making it definitely faster. You wouldn't do this for powers of two though as then you can just use a single shift.
e.g.
Code:

```template <unsigned char n> unsigned short div(unsigned short x) {     return (int)x * ((0x10000+n-1)/n) >> 16; }```
Mod can then be trivially based on this, though there may be a faster way also.
Code:

```template <unsigned char n> unsigned short mod(unsigned short x) {     return x - div<n>(x) * n; }```
Note that I'm also assuming that x is positive as I can't be bothered checking the bahviour of negatives, hence use of unsigned to make sure.

Repeated subtraction until the number is less than the divisior will also work, not that you'd want to do that of course.