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|?

Answer 1

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);
}

Answer 2

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.