Here’s an interesting question that came up on StackOverflow the other day: we know in “real” algebra that the equation
(a / b) / c = a / (b * c) is an “identity”; it is true for any values of
c.[1. Assuming of course that both sides have a well-defined value.] Does this identity hold for integer arithmetic in C#?
In general, no, because of overflow. In a checked context the right side can overflow and produce an exception but the left side cannot. In an unchecked context two large positive values for
c can overflow to a negative number on the right hand side, thereby producing a different result than the left hand side.
Moreover, commenter “Peter” points out that if
(a/b) can overflow too; I hadn’t thought about that case, so good catch.
But what about the specific case where
c are positive numbers and there are no overflows in either expression? Can we rely on this identity under those circumstances?
Let’s find out!
We begin by going back to the definition of integer division; as I’ve described before, there are two operators: the division operator and the remainder operator. Suppose we have (again supposing that
y are positive integers):
r = x % y
q = x / y
The relationship between those values is:
x = q * y + r
0 <= r < y
Let’s break our suspected identity apart into left and right sides. Let’s say that the first division on the left side is:
qab = a / b
rab = a % b
b * qab + rab = a
0 <= rab < b
So our left hand side is
qab / c. The quotient and remainder of that are:
qleft = qab / c
rleft = qab % c
c * qleft + rleft = qab
0 <= rleft < c
We can eliminate
qab through substitution to get the equation:
b * c * qleft + b * rleft + rab = a
OK, that will do for the left hand side. For the right hand side we have just one division:
qright = a / (b * c)
rright = a % (b * c)
b * c * qright + rright = a
0 <= rright < b * c
We now have two equations that equal the same thing,
a, so let’s set them equal to each other:
b * c * qleft + b * rleft + rab = b * c * qright + rright
We know that
qright are both integers. Therefore there is an integer
d, their difference, such that
qleft + d = qright. Let's eliminate
qright from our equation:
b * c * qleft + b * rleft + rab = b * c * qleft + b * c * d + rright
And solve for
d = (b * rleft + rab - rright) / (b * c)
d is an integer. Is possibly positive? Let’s make some inequalities. We know that
rright is non-negative, so the numerator of that fraction:
b * rleft + rab - rright <= b * rleft + rab
We know that
rleft < c and
c > 0 so
b * rleft + rab <= b * (c - 1) + rab
We know that
rab < b, so:
b * (c - 1) + rab < b * (c - 1) + b
b * c. Therefore the numerator of this fraction is strictly less than its denominator, and therefore the fraction must be strictly less than one. Since the fraction is an integer,
d must be zero or negative; it cannot be positive.
The proof that
d also cannot be negative and therefore must be zero is similar and is left as an exercise.
d is zero,
qleft = qright, which establishes the identity — again, provided that all the operands are positive numbers and the multiplication does not overflow.
Proving that the identity works for negative
c is also left as an exercise.