C # 정수 산술에서 a / b / c는 항상 a / (b * c)와 같습니까?

C # 정수 산술에서 a / b / c는 항상 a / (b * c)와 같습니까?

---

a, b 및 c를 크지 않은 양의 정수라고합시다. a / b / c는 C # 정수 산술에서 항상 a / (b * c)와 같습니까? 나를 위해 C #에서는 다음과 같이 보입니다.

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

그래서 내 질문은 : x1 == x2모든 a, b 및 c에 대해합니까?

---

하자 \나타낸다 정수 나누기 (는 C #의 /둘 사이의 운영자 int들) 및하자 /나타낸다 보통 수학 부문. 그런 경우 x,y,z입니다 양의 정수가 우리가하는 오버 플로우를 무시하고 ,

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

어디

a \ b = floor(a / b)

라인에서 점프 [1]라인은 [2]다음과 같이 위의 설명. 범위에 두 개의 정수 a와 b소수 가 있다고 가정합니다 . 그것을 보는 것은 간단합니다f[0, 1)

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

줄 경우 [1]를 식별 a = floor(x / y), f = (x / y) - floor(x / y)그리고 b = z, 다음 [3]것을 의미 [1]와 [2]동일하다.

이 증명을 음의 정수로 일반화 할 수 있지만 (여전히 overflow 무시 ), 요점을 간단하게 유지하기 위해 독자에게 맡기겠습니다.

---

오버플로 문제에 대해 -좋은 설명은 Eric Lippert의 답변을 참조하십시오! 그는 또한 그의 블로그 게시물 과 답변 에서 훨씬 더 엄격한 접근 방식을 취합니다 .

---

이 질문이 너무 마음 에 들어 2013 년 6 월 4 일 블로그 의 주제로 삼았습니다 . 좋은 질문에 감사드립니다!

---

큰 케이스는 쉽게 구할 수 있습니다. 예를 들면 :

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

b * c음수로 넘치기 때문 입니다.

나는에이 사실 것을 추가 할 산술 검사가 , 차이 a / (b * c)와이 (a / b) / c프로그램의 차이가 될 수있는 작품과 프로그램 충돌이. 의 제품 경우 b와는 c정수의 경계를 오버 플로우 한 후 전자는 확인 맥락에서 충돌합니다.

작은 양의 정수, 예를 들어 짧은 값에 들어갈만큼 작은 경우, 동일성은 유지되어야합니다.

---

Timothy Shields는 방금 증거를 게시했습니다. 여기에 대체 증거를 제시합니다. 여기에있는 모든 숫자가 음이 아닌 정수이고 작업이 오버플로되지 않는다고 가정합니다.

정수 분할 x / y찾은 값이 q되도록 q * y + r == x, 여기서 0 <= r < y.

따라서 부서 a / (b * c)는 다음 q1과 같은 값을 찾습니다.

q1 * b * c + r1 == a

어디 0 <= r1 < b * c

부서는 ( a / b ) / c먼저 다음 qt과 같은 값을 찾습니다.

qt * b + r3 == a

그런 다음 다음 q2과 같은 값을 찾습니다.

q2 * c + r2 == qt

그래서 그것을로 대체 qt하면 다음과 같이됩니다.

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

어디 0 <= r2 < c와 0 <= r3 < b.

동일한 두 가지가 서로 동일하므로

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

q1 == q2 + x정수 라고 가정 합니다 x. 그것을 대체하고 다음을 해결하십시오 x.

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

어디

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

x0보다 클 수 있습니까 ? 아닙니다. 우리에게는 불평등이 있습니다.

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

그래서 분수의 분자보다 항상 작은 b * c때문에, x0보다 클 수 없습니다.

x0보다 작을 수 있습니까 ? 아니, 비슷한 주장으로 독자에게 맡겼다.

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

---

If the absolute values of b and c are below about sqrt(2^31) (approx. 46 300), so that b * c will never overflow, the values will always match. If b * c overflows, then an error can be thrown in a checked context, or you can get an incorrect value in an unchecked context.

---

Avoiding the overflow errors noticed by others, they always match.

Let's 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.
In order 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, as required, and the two operations match.

This doesn't work if b or c are negative, but I don't know how integer division works in that case either.

---

I'll offer my own proof for fun. This also ignores overflow and only handles positives unfortunately, but I think the proof is clean and clear.

The goal is to show that

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

where / is normal division (throughout this proof).

We represent the quotient and remainder of a/b uniquely as a = kb + r (by that we mean that k,r are unique and also 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 just to show that k1 == k2. Well we have:

k1*z + r1 = floor(x/y) = k = (x-r)/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 observe from (2) that r1 is an integer (for k1*z is an integer by definition) and r1 < z (also by definition). Furthermore from (1) we know that r < y => r/y < 1. Now consider the sum r1 + r/y from (4). The claim is that r1 + r/y < z and this is clear from the previous claims (because 0 <= r1 < z and r1 is an integer so we have 0 <= r1 <= z-1. Therefore 0 <= r1 + r/y < z). Thus r1 + r/y = r2 by definition of r2 (otherwise there would be two remainders from x/y which contradicts the definition of remainder). Hence 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 except for a couple steps that you'd need to check an extra case(s)... but I didn't check.

---

counter example: INT_MIN / -1 / 2

참고URL : https://stackoverflow.com/questions/16837854/in-c-sharp-integer-arithmetic-does-a-b-c-always-equal-a-bc