Ist a / b / c in der C # -Integer-Arithmetik immer gleich a / (b * c)?

81

Sei a, b und c nicht große positive ganze Zahlen. Ist a / b / c immer gleich a / (b * c) mit C # Integer-Arithmetik? Für mich sieht es in C # so aus:

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

Meine Frage lautet also: gilt x1 == x2für alle a, b und c?

Jason Crease
quelle
3
Dies ist eine mathematische Frage, keine Programmierfrage. Können Sie erklären, was der programmierspezifische Teil dieser Frage ist?
Oded
38
@Oded im Bereich jeder rationalen Zahl, sicher, aber dies bezieht sich speziell auf Ganzzahlarithmetik (in C #). IMO, die es programmierungsbezogen macht. Vielleicht gilt die Regel, dass a / b / c == a / (b * c) in der Ganzzahlarithmetik gilt, vielleicht nur in der Rationalzahlarithmetik.
Tim S.
43
Dies ist eine durchaus vernünftige Frage zu C # und leicht zu beantworten.
Eric Lippert
12
@Oded Dies ist eine Frage zur Computerarithmetik und ob sie sich genauso verhält wie reine Mathematik. Es sollte nicht geschlossen werden.
Jeffrey Sax
4
Ich wäre sehr an einem mathematischen Beweis interessiert, warum (oder ob) die Überläufe ignoriert werden, obwohl sie Überläufe ignorieren, aber ich habe es noch nicht geschafft, einen zusammenzustellen.
Rawling

Antworten:

71

Lassen Sie \bezeichnen Integer - Division (der C # /Operator zwischen zwei ints) und lassen Sie /bezeichnen übliche mathematische Division. Wenn x,y,zdann positive ganze Zahlen sind und wir den Überlauf ignorieren ,

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

wo

a \ b = floor(a / b)

Der Sprung von Zeile [1]zu Zeile [2]oben wird wie folgt erklärt. Angenommen, Sie haben zwei Ganzzahlen aund beine Bruchzahl fim Bereich [0, 1). Es ist einfach, das zu sehen

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

Wenn in Zeile [1]Sie identifizieren a = floor(x / y), f = (x / y) - floor(x / y)und b = z, dann [3]bedeutet , dass [1]und [2]gleich sind.

Sie können diesen Beweis auf negative ganze Zahlen verallgemeinern ( wobei der Überlauf immer noch ignoriert wird ), aber das überlasse ich dem Leser, um den Punkt einfach zu halten.


Zum Thema Überlauf - eine gute Erklärung finden Sie in der Antwort von Eric Lippert! In seinem Blog-Beitrag geht er auch viel strenger vor und antwortet, etwas, das Sie prüfen sollten, wenn Sie das Gefühl haben, dass ich zu handgewellt bin.

Timothy Shields
quelle
1
Hah, das war es, wonach ich
gesucht habe
Ich mag deine Verwendung von \ und / oder dafür. Macht die Dinge viel klarer.
Justin Morgan
@JustinMorgan Die Notation wird tatsächlich in einigen anderen Programmiersprachen verwendet (obwohl ich mich momentan nicht daran erinnere, welche).
Timothy Shields
1
@ TimothyShields VB.net tut.
Arie Xiao
Ich denke, die Behauptung ist wahr, aber Ihrem Beweis scheint ein wichtiger Schritt zu fehlen. Es ist möglich, dass ich Ihre Rechtfertigung für Zeile 2 falsch verstanden habe => Zeile 3. Die Art floor(x / y) - (x / y)und Weise, wie ich sie interpretiert habe, ist klein, und z >= 1daher floorist es 0, und wir können sie ignorieren. Das folgt eigentlich nicht, da es tatsächlich ein Addend innerhalb von a ist floor()(dh floor(1/2)vs berücksichtigen floor(1/2 + 1/2)).
Rliu
77

Diese Frage hat mir so gut gefallen, dass ich sie am 4. Juni 2013 zum Thema meines Blogs gemacht habe . Danke für die tolle Frage!


Große Koffer sind leicht zu bekommen. Beispielsweise:

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

weil b * c überläuft auf eine negative Zahl.

Ich würde dem die Tatsache hinzufügen, dass in der überprüften Arithmetik der Unterschied zwischen a / (b * c)und (a / b) / cein Unterschied zwischen einem funktionierenden Programm und einem abstürzenden Programm sein kann. Wenn das Produkt von bund cdie Grenzen einer Ganzzahl überschreitet, stürzt die erstere in einem überprüften Kontext ab.

Für kleine positive ganze Zahlen, die beispielsweise klein genug sind, um in einen Kurzschluss zu passen, sollte die Identität beibehalten werden.


Timothy Shields hat gerade einen Beweis veröffentlicht. Ich präsentiere hier einen alternativen Beweis. Angenommen, alle Zahlen hier sind nicht negative Ganzzahlen und keine der Operationen läuft über.

Die ganzzahlige Division von x / yfindet den Wert qso, dass q * y + r == x, wo 0 <= r < y.

Die Division a / (b * c)findet also den Wert q1so, dass

q1 * b * c + r1 == a

wo 0 <= r1 < b * c

Die Division ( a / b ) / cfindet zuerst den Wert qtso, dass

qt * b + r3 == a

und findet dann den Wert q2so, dass

q2 * c + r2 == qt

Ersetzen Sie das durch qtund wir erhalten:

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

wo 0 <= r2 < cund 0 <= r3 < b.

Zwei Dinge, die gleich sind, sind einander gleich, also haben wir

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

Angenommen, q1 == q2 + xeine 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)

wo

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

Kann xgrößer als Null sein? Nein, wir haben die Ungleichungen:

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

Der Zähler dieses Bruchs ist also immer kleiner als b * cund xkann daher nicht größer als Null sein.

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

Daher ist die Ganzzahl xNull und daher q1 == q2.

Eric Lippert
quelle
7
@ JoseRuiSantos ja, aber sowohl die x1 als auch die x2Operation werden in diesem Fall identisch abstürzen
Marc Gravell
@ JoseRuiSantos ist das nicht in beiden Fällen wahr?
Jodrell
Die Antwort von vc 74 wurde gelöscht, sodass die meisten Benutzer das Beispiel, auf das Sie verweisen, nicht mehr sehen können.
Gabe
Das ist richtig, beides x1und x2stürzt ab, wenn boder csind Null. Für andere Werte ist der x1Ausdruck besser, da der mögliche ganzzahlige Überlauf davon ( b * c)vermieden x2wird.
Jose Rui Santos
Interessanter Punkt über Überläufe und überprüfte Arithmetik, danke!
Jason Crease
4

Wenn die absoluten Werte von bund cunter ungefähr sqrt(2^31)(ca. 46 300) liegen, so dass b * csie niemals überlaufen, stimmen die Werte immer überein. Wenn es b * cüberläuft, kann ein Fehler in einem checkedKontext ausgelöst werden oder Sie können einen falschen Wert in einem uncheckedKontext erhalten.

Tim S.
quelle
2

Um die von anderen bemerkten Überlauffehler zu vermeiden, stimmen sie immer überein.

Nehmen wir an a/b=q1, das heißt a=b*q1+r1, wo 0<=r1<b.
Nehmen wir nun an a/b/c=q2, was bedeutet, dass q1=c*q2+r2, wo 0<=r2<c.
Das bedeutet das a=b(c*q2+r2)+r1=b*c*q2+br2+r1.
Damit a/(b*c)=a/b/c=q2müssen wir haben 0<=b*r2+r1<b*c.
Aber b*r2+r1<b*r2+b=b*(r2+1)<=b*cnach Bedarf und die beiden Operationen stimmen überein.

Dies funktioniert nicht, wenn boder csind negativ, aber ich weiß auch nicht, wie die Ganzzahldivision in diesem Fall funktioniert.

Teepeemm
quelle
0

Ich werde zum Spaß meinen eigenen Beweis anbieten. Dies ignoriert auch den Überlauf und behandelt leider nur Positive, aber ich denke, der Beweis ist sauber und klar.

Das Ziel ist es, das zu zeigen

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

Wo /ist normale Teilung (während dieses Beweises).

Wir stellen den Quotienten und den Rest von a/b eindeutig als dar a = kb + r(damit meinen wir, dass sie k,reinzigartig sind und auch notieren |r| < |b|). Dann haben wir:

(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

Unser Ziel ist es also, dies zu zeigen k1 == k2. Nun haben wir:

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

und somit:

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

Beobachten Sie nun aus (2), dass r1es sich um eine Ganzzahl handelt (denn k1*zper Definition ist eine Ganzzahl) und r1 < z(auch per Definition). Außerdem wissen wir aus (1), dass r < y => r/y < 1. Betrachten Sie nun die Summe r1 + r/yaus (4). Die Behauptung ist das r1 + r/y < zund dies geht aus den vorherigen Behauptungen hervor (weil 0 <= r1 < zund r1ist eine ganze Zahl, die wir haben 0 <= r1 <= z-1. Deshalb 0 <= r1 + r/y < z). Also r1 + r/y = r2per Definition von r2(sonst gäbe es zwei Reste, von x/ydenen die Definition des Restes widerspricht). Daher haben wir:

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

und wir haben unsere gewünschte Schlussfolgerung, dass k1 = k2.

Der obige Beweis sollte mit Negativen funktionieren, mit Ausnahme einiger Schritte, bei denen Sie zusätzliche Fälle prüfen müssten ... aber ich habe nicht geprüft.

rliu
quelle
0

Zähler Beispiel: INT_MIN / -1 / 2

hustwcw
quelle
"A, b und c seien nicht große positive ganze Zahlen."
Pang
Das ist ein interessanter Fall (dh -INT_MIN ist ein Überlauf). Vielen Dank!
Jason Crease