Euclidean integer modulo in C++

Question

Where can I find an implementation or library that computes the remainder of an integer Euclidean division, 0 <= r < |n|?

score 9 · Accepted Answer · edited Jan 04 '20 at 20:39

In C++98 and C++03 versions of C++ language the built-in division (bit / and % operators) might be Euclidean and might be non-Euclidean - it is implementation defined. However, most implementations truncate the quotient towards zero, which is unfortunately non-Euclidean.

In most implementations 5 / -3 = -1 and 5 % -3 = -2. In Euclidean division 5 / -3 = -2 and 5 % -3 = 1.

C++11 requires integer division to be non-Euclidean: it requires an implementation that truncates towards zero.

The issue, as you can see, arises with negative numbers only. So, you can easily implement Euclidean division yourself by using operator % and post-correcting negative remainders

int euclidean_remainder(int a, int b)
{
  assert(b != 0);
  int r = a % b;
  return r >= 0 ? r : r + std::abs(b);
}

score 5 · Answer 2 · edited May 23 '17 at 12:17

5

Try (x%m + m)%m if the result must be positive.

Write your own function around this, or any of the variants, and don't get hung up on a library - you've spent more time asking than you would to just do it. Start your own library (toolbox) for simple functions you need.

edited May 23 '17 at 12:17

Community

1
1

answered Jul 30 '12 at 02:02

Richard Sitze

8,262
3
36
48

1

Yes that works, thanks. Is there no library that implements this function ? It seems fairly common... – NaomiJO Jul 30 '12 at 02:05
1

This method is unnecessary slow due to the two `%` operations, which involve integer divisions. It is possible to construct a branchless version of @AnT's answer, which will only use a single `%` operation. – plasmacel Dec 27 '19 at 20:00

Brandon · Answer 3 · 2012-07-30T02:29:26.520

3

It's a simple operator. %.

5 % 4 is 1, etc.

Edit: As has been pointed out, depending on your implementation this isn't necessarily a euclidean mod.

#define EUCMOD(a, b)  (a < 0 ? (((a % b) + b) % b) : (a % b))

edited Jul 30 '12 at 02:29

answered Jul 30 '12 at 01:54

Brandon

3,174
1
16
7

1

Note this only works with integers. If you want floating-point modulus, use the `fmod` function. `fmod (3.3, 2.4) is 0.9` – chris Jul 30 '12 at 01:55
No, I said an euclidian division. (-5)%4 is -1 but should be 3. As I said in the question, the remainder r should be between 0 and n, and in my example it's negative. – NaomiJO Jul 30 '12 at 01:58
@NaomiJO, If you really need to, you can just add the `b` from `a % b` onto the result if it's negative. – chris Jul 30 '12 at 02:02
That's actually incorrect. In most implementations division truncates the result towards zero - this is non-Euclidean division. This means that the result of `%` can be negative: this is non-Euclidean already. – AnT stands with Russia Jul 30 '12 at 02:04
1

This method is unnecessary slow due to the two `%` operations, which involve integer divisions. It is possible to construct a branchless version of @AnT's answer, which will only use a single `%` operation. – plasmacel Dec 27 '19 at 20:01

score 0 · Answer 4 · answered Aug 22 '19 at 20:43

I really liked Brandon's answer, but I started having some strange bugs. After some testing I found that the expansion of the EUCMOD macro was messing with the precedence of operations.

So I'd suggest using it as a function instead of a macro

int eucmod(const int a, const int b)
{
    return (a < 0 ? (((a % b) + b) % b) : (a % b));
}

Or adding a few parenthesis

#define EUCMOD(a,b) ((a) < 0 ? ((((a) % (b)) + (b)) % (b)) : ((a) % (b)))

Euclidean integer modulo in C++

4 Answers4