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?
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?
In what situation do you need any other means of getting the remainder than using the "%" ?
When you are asked to implement modulus without using %?
I might be wrong.
Quoted more than 1000 times (I hope).Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
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
Without division? I don't see how that's possible, but if it is I'd like to see :P.
This page shows a way for powers of 2.
In addition, div() seems to calculate both a/b and a%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.
Last edited by anon; 01-16-2008 at 09:19 AM.
I might be wrong.
Quoted more than 1000 times (I hope).Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
int a = 10 ;
int b = 3 ;
int remainder = a - ((a/b)*b) ;
You can always emulate integer division with subtraction and counting.
By doing so, you'll get the modulus automatically.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
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.Mod can then be trivially based on this, though there may be a faster way also.Code:template <unsigned char n> unsigned short div(unsigned short x) { return (int)x * ((0x10000+n-1)/n) >> 16; }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.Code:template <unsigned char n> unsigned short mod(unsigned short x) { return x - div<n>(x) * n; }
Repeated subtraction until the number is less than the divisior will also work, not that you'd want to do that of course.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"