Reputation: 4197

how to get elements of euclidean division in C (no the remainder)

alright. I have the Euclidean division like this : a = b * q + r

I know that to get r, I can do the modulo : a % b

but how do I get q ? // doesn't seem to work.

Upvotes: 0

Answers (4)

Mingye Wang

Reputation: 1374

chux's answer is a good one, as it's the one that correctly understands the question (unlike the accepted one). Daan Leijen's Division and Modulus for Computer Scientists also provides an algorithm with proof:

/* Euclidean quotient */
long quoE(long numer, long denom) {
  /* The C99 and C++11 languages define both of these as truncating. */
  long q = numer / denom;
  long r = numer % denom;
  if (r < 0) {
    if (denom > 0)
      q = q - 1; // r = r + denom;
    else {
      q = q + 1; // r = r - denom;
  }
  return q;
}

This one is trivially equivalent to chux's algorithm. It looks a bit more verbose, but it might take one fewer div instruction on x86, as the instruction performs a "divmod" -- returning q and r at the same time.

Upvotes: 1

chux

Reputation: 153660

Using Euclidean division

If a = 7 and b = 3, then q = 2 and r = 1, since 7 = 3 × 2 + 1.
If a = 7 and b = −3, then q = −2 and r = 1, since 7 = −3 × (−2) + 1.
If a = −7 and b = 3, then q = −3 and r = 2, since −7 = 3 × (−3) + 2.
If a = −7 and b = −3, then q = 3 and r = 2, since −7 = −3 × 3 + 2.

Likely a more simple solution is available.

int Ediv(int a, int b) {
  printf("a:%2d / b:%2d = ", a,b);
  int r = a % b;
  if (r < 0) r += abs(b);
  printf("r:%2d ", r);
  return (a - r) / b;
}

void Etest() {
  printf("q:%2d\n", Ediv(7,3));
  printf("q:%2d\n", Ediv(7,-3));
  printf("q:%2d\n", Ediv(-7,3));
  printf("q:%2d\n", Ediv(-7,-3));
}

a: 7 / b: 3 = r: 1 q: 2
a: 7 / b:-3 = r: 1 q:-2
a:-7 / b: 3 = r: 2 q:-3
a:-7 / b:-3 = r: 2 q: 3

OP asserts "I know that to get r, I can do the modulo : a % b". This fails when a is negative.

Further, % is the "remainder operator". In C, the difference between Euclidean remainder and modulo occurs when a is negative. Remainder calculation for the modulo operation

Upvotes: 3