[C#] Ist a / b / c in C # Ganzzahlarithmetik immer gleich a / (b * c)?


Answers

Ich mochte diese Frage so sehr, dass ich sie am 4. Juni 2013 zum Thema meines Blogs gemacht habe . Danke für die tolle Frage!

Große Fälle sind leicht zu bekommen. Beispielsweise:

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

weil b * c zu einer negativen Zahl überläuft.

Ich würde hinzufügen, dass in der arithmetischen Überprüfung die Differenz zwischen a / (b * c) und (a / b) / c den Unterschied zwischen einem Programm, das funktioniert, und einem Programm, das abstürzt, sein kann. Wenn das Produkt von b und c die Grenzen einer ganzen Zahl übersteigt, stürzt die erstere in einem überprüften Kontext ab.

Für kleine positive ganze Zahlen, sagen wir, klein genug, um in einen kurzen zu passen, sollte die Identität beibehalten werden.

Timothy Shields hat gerade einen Beweis geschrieben; Ich präsentiere hier einen alternativen Beweis. Angenommen, alle Zahlen sind nicht negative ganze Zahlen und keine der Operationen überläuft.

Ganzzahlige Division von x / y findet den Wert q so, dass q * y + r == x , wobei 0 <= r < y .

Also findet die Division a / (b * c) den Wert q1 so, dass

q1 * b * c + r1 == a

wo 0 <= r1 < b * c

die Division ( a / b ) / c findet zuerst den Wert qt so dass

qt * b + r3 == a

und findet dann den Wert q2 so dass

q2 * c + r2 == qt

Also ersetze das für qt und wir bekommen:

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

mit 0 <= r2 < c und 0 <= r3 < b .

Zwei Dinge gleich sind einander gleich, also haben wir

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

Angenommen, q1 == q2 + x für eine ganze Zahl x . Ersetzen Sie das in und lösen Sie für x :

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

woher

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

Kann x größer als Null sein? Nein. Wir haben die Ungleichheiten:

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

Der Zähler dieses Bruchteils ist also immer kleiner als b * c , also kann x nicht größer als Null sein.

Kann x kleiner als Null sein? Nein, durch ein ähnliches Argument, dem Leser überlassen.

Daher ist die ganze Zahl x Null und daher gilt q1 == q2 .

Question

Seien a, b und c nicht große positive ganze Zahlen. Ist a / b / c immer gleich a / (b * c) mit C # Ganzzahlarithmetik? Für mich sieht es in C # folgendermaßen aus:

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

Meine Frage ist also: x1 == x2 für alle a, b und c?




Durch Vermeidung von Überlauffehlern, die von anderen bemerkt werden, stimmen sie immer überein.

Nehmen wir an, dass a/b=q1 , was bedeutet, dass a=b*q1+r1 , wobei 0<=r1<b .
Nehmen wir nun an, dass a/b/c=q2 , was bedeutet, dass q1=c*q2+r2 , wobei 0<=r2<c .
Dies bedeutet, dass a=b(c*q2+r2)+r1=b*c*q2+br2+r1 .
Damit a/(b*c)=a/b/c=q2 , müssen wir 0<=b*r2+r1<b*c .
Aber b*r2+r1<b*r2+b=b*(r2+1)<=b*c , wie erforderlich, und die beiden Operationen stimmen überein.

Dies funktioniert nicht, wenn b oder c negativ sind, aber ich weiß auch nicht, wie die Integer-Division in diesem Fall funktioniert.




Gegenbeispiel: INT_MIN / -1 / 2