Czy w arytmetyce liczb całkowitych w języku C # a / b / c zawsze równa się a / (b * c)?

81

Niech a, b i c będą niedużymi dodatnimi liczbami całkowitymi. Czy a / b / c zawsze równa się a / (b * c) z arytmetyką całkowitoliczbową C #? U mnie w C # wygląda to tak:

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

Więc moje pytanie brzmi: czy x1 == x2dla wszystkich a, bi c?

Jason Crease
źródło
3
To jest pytanie matematyczne, a nie programistyczne. Czy możesz wyjaśnić, na czym polega programowanie konkretnej części tego pytania?
Oded
38
@Oded w zakresie dowolnej liczby wymiernej, jasne, ale dotyczy to konkretnie arytmetyki liczb całkowitych (w C #). IMO, która sprawia, że ​​jest to związane z programowaniem. Może reguła, którą a / b / c == a / (b * c) obowiązuje w arytmetyce liczb całkowitych, może obowiązuje tylko w arytmetyce liczb wymiernych.
Tim S.
43
To całkiem rozsądne pytanie dotyczące języka C #, na które łatwo odpowiedzieć.
Eric Lippert
12
@Oded To jest pytanie dotyczące arytmetyki komputerowej i tego, czy zachowuje się tak samo jak czysta matematyka. Nie powinno być zamknięte.
Jeffrey Sax
4
Byłbym całkiem zainteresowany matematycznym dowodem na to, dlaczego (lub rzeczywiście), ignorując przepełnienia, oba są w rzeczywistości równoważne, ale nie udało mi się jeszcze połączyć jednego.
Rawling

Odpowiedzi:

71

Niech \oznaczają dzielenia całkowitego (C # /operatora pomiędzy dwoma intS) i pozwolić /oznaczają zwykły podział matematycznej. Następnie, jeśli x,y,zdodatnimi liczbami całkowitymi i ignorujemy przepełnienie ,

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

gdzie

a \ b = floor(a / b)

Skok od wiersza [1]do wiersza [2]powyżej wyjaśniono w następujący sposób. Załóżmy, że masz dwie liczby całkowite ai boraz liczbę ułamkową fw przedziale [0, 1). Łatwo to zobaczyć

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

Jeśli w linii [1]identyfikujesz a = floor(x / y), f = (x / y) - floor(x / y)i b = z, to [3]implikuje to [1]i [2]jesteś równy.

Możesz uogólnić ten dowód na ujemne liczby całkowite (nadal ignorując przepełnienie ), ale zostawię to czytelnikowi, aby zachować prostotę.


Jeśli chodzi o kwestię przepełnienia - zobacz odpowiedź Erica Lipperta, aby uzyskać dobre wyjaśnienie! W swoim wpisie na blogu i odpowiedziach przyjmuje również znacznie bardziej rygorystyczne podejście , na co powinieneś zwrócić uwagę, jeśli uważasz, że jestem zbyt falujący.

Timothy Shields
źródło
1
Hah, o to mi chodziło :)
Rawling
Podoba mi się, jak używasz \ i / do tego. Sprawia, że ​​wszystko jest znacznie jaśniejsze.
Justin Morgan
@JustinMorgan Notacja jest faktycznie używana w niektórych innych językach programowania (chociaż nie pamiętam w tej chwili).
Timothy Shields
1
@TimothyShields VB.net robi.
Arie Xiao
Myślę, że to twierdzenie jest prawdziwe, ale wydaje się, że w Twoim dowodzie brakuje kluczowego kroku. Możliwe, że źle zrozumiałem twoje uzasadnienie dla linii 2 => linii 3. Sposób, w jaki to zinterpretowałem, był floor(x / y) - (x / y)mały, z >= 1więc przyjmowanie floortego wynosi 0 i możemy to zignorować. To tak naprawdę nie następuje, ponieważ w rzeczywistości jest to dodatek w ramach floor()(tj. Rozważ floor(1/2)vs floor(1/2 + 1/2)).
rliu
77

To pytanie tak mi się spodobało, że 4 czerwca 2013 r . Uczyniłem je tematem mojego bloga . Dzięki za świetne pytanie!


Duże skrzynie są łatwe do zdobycia. Na przykład:

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

ponieważ b * cprzepełnia do liczby ujemnej.

Dodałbym do tego fakt, że w sprawdzonej arytmetyce różnica między a / (b * c)i (a / b) / cmoże być różnicą między działającym programem a programem, który ulega awarii. Jeśli iloczyn liczby całkowitej bi cprzekracza granice liczby całkowitej, poprzednia ulegnie awarii w sprawdzonym kontekście.

W przypadku małych dodatnich liczb całkowitych, powiedzmy, dostatecznie małych, aby pasowały do ​​skrótu, należy zachować tożsamość.


Timothy Shields właśnie przesłał dowód; Przedstawiam tutaj alternatywny dowód. Załóżmy, że wszystkie liczby są nieujemnymi liczbami całkowitymi i żadna z operacji nie przepełnia się.

Dzielenie liczb całkowitych x / yznajduje wartość qtaką, że q * y + r == x, gdzie 0 <= r < y.

Więc podział a / (b * c)znajduje taką wartość q1, że

q1 * b * c + r1 == a

gdzie 0 <= r1 < b * c

dzielenie ( a / b ) / cnajpierw znajduje wartość qttaką, że

qt * b + r3 == a

a następnie stwierdza wartość q2w taki sposób,

q2 * c + r2 == qt

Więc zastąp to w for qti otrzymamy:

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

gdzie 0 <= r2 < ci 0 <= r3 < b.

Dwie równe sobie rzeczy są sobie równe, więc mamy

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

Załóżmy, że q1 == q2 + xdla jakiejś liczby całkowitej x. Zastąp to w i rozwiąż x:

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

gdzie

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

Czy może xbyć większe niż zero? Nie. Mamy nierówności:

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

Zatem licznik tego ułamka jest zawsze mniejszy niż b * c, więc xnie może być większy od zera.

Czy może xbyć mniejsze niż zero? Nie, za pomocą podobnego argumentu pozostawiono czytelnikowi.

Dlatego liczba całkowita xjest równa zero, a zatem q1 == q2.

Eric Lippert
źródło
7
@JoseRuiSantos tak, ale zarówno x1 ix2 operacja padnie identycznie w tym przypadku
Marc Gravell
@JoseRuiSantos, czy to nie jest prawda w obu przypadkach?
Jodrell
Odpowiedź vc 74 została usunięta, więc większość ludzi nie widzi już przykładu, do którego się odnosisz.
Gabe
Zgadza się, oba x1i x2ulegną awarii, jeśli blub csą równe zero. Dla innych wartości, x1ekspresja jest lepszy, ponieważ pozwoli uniknąć ewentualnego przepełnienia całkowitą ( b * c)że x2ma.
Jose Rui Santos
Ciekawa uwaga na temat przepełnień i sprawdzonej arytmetyki, dzięki!
Jason Crease
4

Jeśli wartości bezwzględne bi csą poniżej około sqrt(2^31)(ok. 46 300), tak aby b * cnigdy się nie przepełniły, wartości zawsze będą zgodne. W przypadku b * cprzepełnienia można zgłosić błąd w checkedkontekście lub uzyskać niepoprawną wartość w uncheckedkontekście.

Tim S.
źródło
2

Unikając błędów przepełnienia zauważonych przez innych, zawsze pasują.

Załóżmy, że to a/b=q1znaczy, że a=b*q1+r1, gdzie 0<=r1<b.
Teraz przypuśćmy, że to a/b/c=q2znaczy, że q1=c*q2+r2, gdzie 0<=r2<c.
To znaczy, że a=b(c*q2+r2)+r1=b*c*q2+br2+r1.
W tym celu a/(b*c)=a/b/c=q2musimy mieć 0<=b*r2+r1<b*c.
Ale b*r2+r1<b*r2+b=b*(r2+1)<=b*cw razie potrzeby te dwie operacje są zgodne.

To nie działa, jeśli są ujemne blub csą ujemne, ale nie wiem, jak działa dzielenie liczb całkowitych w tym przypadku.

Teepeemm
źródło
0

Dam własny dowód dla zabawy. To również ignoruje przepełnienie i niestety obsługuje tylko pozytywy, ale myślę, że dowód jest czysty i wyraźny.

Celem jest pokazanie tego

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

gdzie /jest normalny podział (w całym tym dowodzie).

Przedstawiamy iloraz i resztę z a/b unikalnie as a = kb + r(przez to rozumiemy, że k,rsą unikalne i również zauważalne |r| < |b|). Potem będzie:

(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

Więc naszym celem jest po prostu to pokazać k1 == k2. Cóż, mamy:

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

a zatem:

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

Teraz obserwujemy z (2), że r1jest to liczba całkowita (for k1*zjest liczbą całkowitą z definicji) i r1 < z(również z definicji). Ponadto z (1) wiemy, że r < y => r/y < 1. Rozważmy teraz sumę r1 + r/yz (4). Twierdzenie jest takie r1 + r/y < zi jest to jasne z poprzednich twierdzeń (ponieważ 0 <= r1 < zi r1jest liczbą całkowitą, więc mamy 0 <= r1 <= z-1. Dlatego 0 <= r1 + r/y < z). Zatem r1 + r/y = r2z definicji r2(w przeciwnym razie byłyby dwie reszty, z x/yktórych jest sprzeczna definicja reszty). Stąd mamy:

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

i mamy nasz upragniony wniosek k1 = k2.

Powyższy dowód powinien działać z negatywami, z wyjątkiem kilku kroków, które musiałbyś sprawdzić w dodatkowych przypadkach ... ale nie sprawdziłem.

rliu
źródło
0

Przykład licznika: INT_MIN / -1 / 2

hustwcw
źródło
„Niech a, b i c będą niedużymi dodatnimi liczbami całkowitymi”.
Pang,
To interesujący przypadek (np. -INT_MIN to przepełnienie). Dzięki!
Jason Crease,