Home > database >  Efficient/portable signed integer mod positive integer returning nonnegative?
Efficient/portable signed integer mod positive integer returning nonnegative?

Time:06-13

In C and C , I want to divide and mod a signed integer by a positive integer such that the div rounds towards negative infinity and the mod always returns nonnegative.

For the division I have:

int64_t SignedDiv(int64_t A_signed, int64_t B_positive) {
    return A_signed / B_positive - (A_signed % B_positive < 0);
}

which is taken from this answer to a similar question.

For the mod I have:

int64_t SignedMod(int64_t A_signed, int64_t B_positive) {
   return A_signed - B_positive * SignedDiv(A_signed, B_positive);
}

which seems terrible. Is there a way to rewrite SignedMod such that it will return the same thing (and is equally portable) but is more efficient?

Here is the compilation output on godbolt:

https://godbolt.org/z/eeG93xh5f

CodePudding user response:

This saves 2 opcodes on x86_64 with clang -O3:

int64_t SignedMod2(int64_t A_signed, int64_t B_positive) {
   int64_t t = A_signed % B_positive;
   if (t < 0) t  = B_positive;
   return t;
}

Using gcc or clang -Os eliminates all the jumps in the output which is probably a fair bit faster. I have no idea what clang is doing there blowing up the code length with needless jumps.

CodePudding user response:

mod always returns nonnegative.

Pulled from this answer: What's the difference between “mod” and “remainder”?. Also handles b < 0 corner cases - even though OP says b > 0.

int modulo_Euclidean2(int a, int b) {
  if (b == 0) TBD_Code(); // perhaps return -1 to indicate failure?
  if (b == -1) return 0; // This test needed to prevent UB of `INT_MIN % -1`.
  int m = a % b;
  if (m < 0) {
    // m  = (b < 0) ? -b : b; // avoid this form: it is UB when b == INT_MIN
    m = (b < 0) ? m - b : m   b;
  }
  return m;
}

Like @Goswin von Brederlow when b > 0.

  • Related