In C # integer arithmetic, a / b / c is always equal to a / (b * c)?

Question

Let a, b, and c be small, positive integers. Is a / b / c always equal to a / (b * c) with C # integer arithmetic? For me in C #, it looks like this:

int a = 5126, b = 76, c = 14; int x1 = a / b / c; int x2 = a / (b * c); 

So my question is: does x1 == x2 for all a, b and c?

Answer 1

Let \ denote integer division (C # / operator between two int s), and / denote ordinary mathematical division. Then, if x,y,z positive integers , and we ignore the overflow ,

 (x \ y) \ z = floor(floor(x / y) / z) [1] = floor((x / y) / z) [2] = floor(x / (y * z)) = x \ (y * z) 

Where

 a \ b = floor(a / b) 

The transition from line [1] to line [2] above is explained as follows. Suppose you have two integers a and b and a fractional number f in the range [0, 1) . It is easy to see that

 floor(a / b) = floor((a + f) / b) [3] 

If in line [1] you identify a = floor(x / y) , f = (x / y) - floor(x / y) and b = z , then [3] means that [1] and [2] are equal.

You can generalize this proof to negative integers (still ignoring overflow ), but I will leave it for reading to make the point simple.

---

On the issue of overflow - see Eric Lippert's answer for a good explanation! He also takes a much stricter approach in his blog post and responds with something that you should pay attention to if you feel that I'm too exciting.

Answer 2

I liked this question so much, I made it the subject of my blog on June 4, 2013 . Thanks for the great question!

---

Big cases are easy to find. For example:

 a = 1073741823; b = 134217727; c = 134217727; 

because b * c overflows to a negative number.

I would add that the fact that in proven arithmetic the difference between a / (b * c) and (a / b) / c may be the difference between a program that works and a program that crashes. If the product of b and c overflows the bounds of an integer, then the first will fail in a verified context.

For small positive integers, say small enough to fit short, identification must be supported.

---

Timothy Shields has just published a proof; I present here an alternative evidence. Suppose all the numbers here are non-negative integers and none of the overflow operations.

Integer division x / y finds a value q such that q * y + r == x , where 0 <= r < y .

So, the division a / (b * c) finds the value q1 such that

 q1 * b * c + r1 == a 

where 0 <= r1 < b * c

division ( a / b ) / c first finds a qt such that

 qt * b + r3 == a 

and then finds a q2 value such that

 q2 * c + r2 == qt 

So, replace that for qt and get:

 q2 * b * c + b * r2 + r3 == a 

where 0 <= r2 < c and 0 <= r3 < b .

Two identical things are equal to each other, so we have

 q1 * b * c + r1 == q2 * b * c + b * r2 + r3 

Suppose q1 == q2 + x for some integer x . Replace this and solve for x :

 q2 * b * c + x * b * c + r1 = q2 * b * c + b * r2 + r3 x = (b * r2 + r3 - r1) / (b * c) 

Where

  0 <= r1 < b * c 0 <= r2 < c 0 <= r3 < b 

Could x be greater than zero? No. We have the inequalities:

  b * r2 + r3 - r1 <= b * r2 + r3 <= b * (c - 1) + r3 < b * (c - 1) + b == b * c 

So, the numerator of this fraction is always less than b * c , so x cannot be greater than zero.

Could x be less than zero? No, for a similar argument, left to the reader.

Therefore, the integer x is equal to zero, and therefore q1 == q2 .

Answer 3

If the absolute values ​​of b and c below about sqrt(2^31) (about 46,300), so that b * c will never overflow, the values ​​will always match. If b * c overflows, then the error may be caused in the checked context, or you may get the wrong value in the unchecked context.

Answer 4

Avoiding overflow errors noticed by others, they always match.

Suppose that a/b=q1 , which means that a=b*q1+r1 , where 0<=r1<b .
Now suppose that a/b/c=q2 , which means that q1=c*q2+r2 , where 0<=r2<c .
This means that a=b(c*q2+r2)+r1=b*c*q2+br2+r1 .
For a/(b*c)=a/b/c=q2 we need to have 0<=b*r2+r1<b*c .
But b*r2+r1<b*r2+b=b*(r2+1)<=b*c , if required, and the two operations coincide.

This does not work if b or c are negative, but I do not know how integer division works in this case.

Answer 5

I will offer my own evidence for pleasure. It also ignores overflow and, unfortunately, only handles positive results, but I believe the evidence is clean and clear.

The goal is to show that

floor(floor(x/y)/z) = floor(x/y/z)

where / is the normal division (in all this proof).

We represent the quotient and the rest a/b uniquely as a = kb + r (this implies that k,r are unique, as well as the note |r| < |b| ). Then we have:

 (1) floor(x/y) = k => x = ky + r (2) floor(floor(x/y)/r) = k1 => floor(x/y) = k1*z + r1 (3) floor(x/y/z) = k2 => x/y = k2*z + r2 

So, our goal is to show that k1 == k2 . Well, we have:

 k1*z + r1 = floor(x/y) = k = (xr)/y (from lines 1 and 2) => x/y - r/y = k1*z + r1 => x/y = k1*z + r1 + r/y 

and thus:

 (4) x/y = k1*z + r1 + r/y (from above) x/y = k2*z + r2 (from line 3) 

Now we note from (2) that r1 is an integer (for k1*z is integer by definition) and r1 < z (also by definition). In addition, it is known from (1) that r < y => r/y < 1 . Now consider the sum r1 + r/y from (4). The statement is that r1 + r/y < z and this is clear from the previous statements (because 0 <= r1 < z and r1 is an integer, therefore we have 0 <= r1 <= z-1 . Therefore, 0 <= r1 + r/y < z ). Thus r1 + r/y = r2 by the definition of r2 (otherwise there would be two residues from x/y , which contradicts the definition of the remainder). Therefore, we have:

 x/y = k1*z + r2 x/y = k2*z + r2 

and we have our desired conclusion that k1 = k2 .

The above proof should work with negatives, with the exception of a few steps that you will need to check for the extra case (s) ... but I did not check.

Answer 6

counter example: INT_MIN / -1 / 2