4

Possible Duplicate:
How to code a modulo (%) operator in C/C++/Obj-C that handles negative numbers

From what I understand (see Modulo operator with negative values and Modulo operation) C & C++ have a "remainder" operator a % b but no operator that actually does modular arithmetic when the LHS is negative.

Several languages do have such a function. Is it possible to build an efficient function in C/C++ (or is there no efficient way to do it on i686/x64 CPUs)?

Currently I use (n * b + a) % b where n is picked such that I'm fairly sure the entire LHS is non-negative, but inevitably code gets changed and bugs sometimes occur.

Note: in case it's not clear, by modular arithmetic I mean an operator such that a + b % b = a % b for all integers a and all positive integers b.

4
  • 1
    stackoverflow.com/questions/4003232/…
    – Andriy
    Aug 23, 2012 at 10:23
  • Are you working with integers? Otherwise I would recommend std::fmod.
    – Ruud
    Aug 23, 2012 at 10:26
  • Integers, yes. Mostly as array indices.
    – dhardy
    Aug 23, 2012 at 12:07
  • 1
    Im really late to the party (7 years too late), but is this: (a % b + b) % b maybe what you are looking for? Jun 22, 2020 at 21:24

2 Answers 2

15

There is no simple way to do it, however it is more efficient if you create a two-line solution, and spare a multiplication plus determining n.

inline int modulo(int a, int b) {
  const int result = a % b;
  return result >= 0 ? result : result + b;
}

Also, if you need to work correctly for negative b numbers as well, add to the beginning:

          if(b < 0) return modulo(-a, -b);
2
  • 2
    "There's no simple way to do it"... Really? Your solution looks pretty simple to me. +1
    – JeremyP
    Aug 23, 2012 at 10:52
  • Wow, that was quick! I'll test performance later, but unless the jump is significant it's probably not going to be much slower than what I use ATM.
    – dhardy
    Aug 23, 2012 at 12:08
2

I would suggest a function like the one above, but using inline int modulo(int a, int b) {} (just as if the operator existed in C++). Personnally I don't use negative numbers often, and still think you should keep % whenever your code doesn't use negative numbers.

4
  • I added the inline suggestion to the answer. Thanks.
    – Lorlin
    Aug 23, 2012 at 11:21
  • The problem is code gets changed, and what was once non-negative sometimes ends up being negative. I might use % along with an assert in places though (I don't care about debug-mode performance so much).
    – dhardy
    Aug 23, 2012 at 12:10
  • @dhardy what do you mean the code gets changed? The cases I was talking about are for example array indexes (that are never <0), or incremental counters.
    – maxbc
    Aug 23, 2012 at 14:06
  • I mean new features imply old stuff gets changed, not always in a way that gives every little detail of that change the attention it deserves. Have a look at this then come help look for more bugs if you really want to know.
    – dhardy
    Aug 23, 2012 at 15:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.