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 == x2
für alle a, b und c?
c#
math
integer
integer-arithmetic
Jason Crease
quelle
quelle
Antworten:
Lassen Sie
\
bezeichnen Integer - Division (der C #/
Operator zwischen zweiint
s) und lassen Sie/
bezeichnen übliche mathematische Division. Wennx,y,z
dann positive ganze Zahlen sind und wir den Überlauf ignorieren ,wo
Der Sprung von Zeile
[1]
zu Zeile[2]
oben wird wie folgt erklärt. Angenommen, Sie haben zwei Ganzzahlena
undb
eine Bruchzahlf
im Bereich[0, 1)
. Es ist einfach, das zu sehenWenn in Zeile
[1]
Sie identifizierena = floor(x / y)
,f = (x / y) - floor(x / y)
undb = 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.
quelle
floor(x / y) - (x / y)
und Weise, wie ich sie interpretiert habe, ist klein, undz >= 1
daherfloor
ist es 0, und wir können sie ignorieren. Das folgt eigentlich nicht, da es tatsächlich ein Addend innerhalb von a istfloor()
(dhfloor(1/2)
vs berücksichtigenfloor(1/2 + 1/2)
).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:
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) / c
ein Unterschied zwischen einem funktionierenden Programm und einem abstürzenden Programm sein kann. Wenn das Produkt vonb
undc
die 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 / y
findet den Wertq
so, dassq * y + r == x
, wo0 <= r < y
.Die Division
a / (b * c)
findet also den Wertq1
so, dasswo
0 <= r1 < b * c
Die Division
( a / b ) / c
findet zuerst den Wertqt
so, dassund findet dann den Wert
q2
so, dassErsetzen Sie das durch
qt
und wir erhalten:wo
0 <= r2 < c
und0 <= r3 < b
.Zwei Dinge, die gleich sind, sind einander gleich, also haben wir
Angenommen,
q1 == q2 + x
eine ganze Zahlx
. Ersetzen Sie das in und lösen Sie fürx
:wo
Kann
x
größer als Null sein? Nein, wir haben die Ungleichungen:Der Zähler dieses Bruchs ist also immer kleiner als
b * c
undx
kann daher nicht größer als Null sein.Kann
x
kleiner als Null sein? Nein, durch ein ähnliches Argument dem Leser überlassen.Daher ist die Ganzzahl
x
Null und daherq1 == q2
.quelle
x1
als auch diex2
Operation werden in diesem Fall identisch abstürzenx1
undx2
stürzt ab, wennb
oderc
sind Null. Für andere Werte ist derx1
Ausdruck besser, da der mögliche ganzzahlige Überlauf davon( b * c)
vermiedenx2
wird.Wenn die absoluten Werte von
b
undc
unter ungefährsqrt(2^31)
(ca. 46 300) liegen, so dassb * c
sie niemals überlaufen, stimmen die Werte immer überein. Wenn esb * c
überläuft, kann ein Fehler in einemchecked
Kontext ausgelöst werden oder Sie können einen falschen Wert in einemunchecked
Kontext erhalten.quelle
Um die von anderen bemerkten Überlauffehler zu vermeiden, stimmen sie immer überein.
Nehmen wir an
a/b=q1
, das heißta=b*q1+r1
, wo0<=r1<b
.Nehmen wir nun an
a/b/c=q2
, was bedeutet, dassq1=c*q2+r2
, wo0<=r2<c
.Das bedeutet das
a=b(c*q2+r2)+r1=b*c*q2+br2+r1
.Damit
a/(b*c)=a/b/c=q2
müssen wir haben0<=b*r2+r1<b*c
.Aber
b*r2+r1<b*r2+b=b*(r2+1)<=b*c
nach Bedarf und die beiden Operationen stimmen überein.Dies funktioniert nicht, wenn
b
oderc
sind negativ, aber ich weiß auch nicht, wie die Ganzzahldivision in diesem Fall funktioniert.quelle
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 dara = kb + r
(damit meinen wir, dass siek,r
einzigartig sind und auch notieren|r| < |b|
). Dann haben wir:Unser Ziel ist es also, dies zu zeigen
k1 == k2
. Nun haben wir:und somit:
Beobachten Sie nun aus (2), dass
r1
es sich um eine Ganzzahl handelt (dennk1*z
per Definition ist eine Ganzzahl) undr1 < z
(auch per Definition). Außerdem wissen wir aus (1), dassr < y => r/y < 1
. Betrachten Sie nun die Summer1 + r/y
aus (4). Die Behauptung ist dasr1 + r/y < z
und dies geht aus den vorherigen Behauptungen hervor (weil0 <= r1 < z
undr1
ist eine ganze Zahl, die wir haben0 <= r1 <= z-1
. Deshalb0 <= r1 + r/y < z
). Alsor1 + r/y = r2
per Definition vonr2
(sonst gäbe es zwei Reste, vonx/y
denen die Definition des Restes widerspricht). Daher haben wir: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.
quelle
Zähler Beispiel: INT_MIN / -1 / 2
quelle