2009-09-13:

Dzielenie całkowite i WTF

c:python:perl:ruby:php:easy
Zawsze myślałem że umiem dzielić liczby całkowite i obliczać resztę z takiego dzielenia, ale jak to zwykle bywa, życie zweryfikowało moją ocenę sytuacji, i powiedziało mi "nie umiesz dzielić!". Otóż wziąłem do ręki pewien podręcznik do matematyki (do liceum) w którym definicja dzielenia całkowitego i reszty z dzielenia kapkę odbiegała od mojej. Ofc będąc programistą od razu rzuciłem się do kompa żeby sprawdzić "jak to tam wygląda", i okazało się że nie ma jednej spójnej wersji...

Nie przedłużając, problem wygląda tak:
Jaki jest wynik z dzielenia i ile wynosi reszta z dzielenia następujących liczb:
-12 przez 5
12 przez -5

Wg mojej, bądź co bądź pozyskanej w szkole podstawowej, wiedzy wyniki powinny być takie:
-12 przez 5 = -2 i reszty -2
12 przez -5 = -2 i reszty  2

Natomiast podręcznik Krzysztofa Kłaczkowa, Marcina Kurczaba i Elżbiety Świda "matematyka; podręcznik do liceów i techników, klasa I, zakres podstawowy i rozszerzony" (wydanie I, 2002) twierdzi że wyniki są takie:
-12 przez 5 = -3 i reszty 3
12 przez -5 = -2 i reszty 2

Autorzy przy okazji przywołują definicję:
Liczba całkowita a przy dzieleniu przez liczbę całkowitą b != 0 daje resztę r (r należy do N) wtedy i tylko wtedy, gdy istnieje taka liczba k należąca do C, że a = k * b + r, gdzie 0 <= r < |b|. Symbol |b| oznacza wartość bezwzględną liczby b.

Nasza polska Wiki (polecam ten art btw) ma odrobinę różną definicję reszty z dzielenia liczb całkowitych:
Jeżeli a i d są liczbami całkowitymi, gdzie d nie jest zerem, wtedy reszta jest liczbą całkowitą taką, że a = qd + r dla pewnego q i przy 0 <= |r| < |d|. Kiedy definiujemy w ten sposób istnieją dwie możliwe reszty. Na przykład, dzielenie -42 przez -5 może być wyrażone jako
   -42 = 9*(-5) + 3
albo
   -42 = 8*(-5) + (-2).
Tak więc resztą jest 3 lub -2.

Więc OK, rozumiem że w podręczniku do liceum używają uproszczonej definicji tak aby nie mieszać ludziom w głowie od początku mówiąc że "istnieją dwie reszty z dzielenia".

Ale w przypadku języków programowania nie można mówić o dwóch różnych wynikach dzielenia czy dwóch różnych resztach z dzielenia, więc powstaje pytanie - jak to jest w przypadku różnych języków? W przypadku języków kompilowanych jest dodatkowe pytanie: jak to wygląda na różnych architekturach?

Podczas moich testów otrzymałem następujące wyniki (wyniki w formacie A Br, C Dr, gdzie -12 / 5 = A i reszty B i 12 / -5 = C i reszty D):
Podręcznik    : -3  3r, -2 2r
Intuicja      : -2 -2r, -2 2r
C, gcc, x86-64: -2 -2r, -2 2r
C, gcc, sparc : -2 -2r, -2 2r
PHP, x86-64   : -2 -2r, -2 2r
Python, x86-64: -3  3r, -3 -3r
Ruby, x86     : -3  3r, -3 -3r
Perl, x86-64  : -2 -2r, -2 2r

Jak widać wyniki są bardzo podobne, ale jednak różne (Python, Ruby). Natomiast niewątpliwie ciekawe.

By the way...
On 22nd Nov'24 we're running a webinar called "CVEs of SSH" – it's free, but requires sign up: https://hexarcana.ch/workshops/cves-of-ssh (Dan from HexArcana is the speaker).


A kto ma rację? Cóż, to zależy od definicji, więc zapewne każdy ma własną ;>

Zachęcam do przetestowania innych języków / architektur i podzielenia się wynikami!

UPDATE: Warto rzucić okiem tutaj, jest tam rozpiska jaki język programowania którą wersje wyników poda (bardziej ogólnie ofc) (via kross12 z komentarzy na wykopie)

UPDATE 2: W czym jest napisany "kalkulator" w wyszukiwarce Google? No idea, ale pewna podpowiedź już jest:
(-12) % 5 w Google (spoiler: 3)
12 % (-5) w Google (spoiler: -3)

UPDATE 3: Bardzo ciekawy i warty przeczytania wpis nawiązujący do powyższego tematu: "Na ogólne życzenie publiczności"

Comments:

2009-09-13 21:47:54 = grn
{
Resztą z dzielenia nazywamy liczbę 0 <= r < |b|. Ujemne reszty to tzw. bezwzględnie najmniejsze reszty z dzielenia. Algorytm wyznaczania obu jest nazywany dzieleniem z resztą, stąd niejednoznaczność. Dobrze jest je rozróżniać, aby uniknąć pomyłek.
}
2009-09-13 22:43:23 = TeMPOraL
{
Nie dziwię się frustracji - pomyśl, że ja z tym problemem zetknąłem się... w trakcie korków z matematyki! Tłumaczyłem resztę z dzielenia i - suprise suprise - jak liczymy resztę dla liczb ujemnych? Włączyłem komputer, odpaliłem Octave i po pół godziny dalej nie wiedziałem ;)

Dzisiaj rano przypadkiem trafiłem w pewnej książce na wyjaśnienie:

http://gigamonkeys.com/book/numbers-characters-and-strings.html - przypis 10
Wynika z tego, że w C nie było ustalonej wersji aż do C'99, a w różnych językach operator % robi zupełnie co innego. Tłumacząc z tamtej książki definicje dwóch reszt (rem i mod):

floor(x/y)*y + mod (x,y) == x
truncate(x/y)*y + rem(x,y) == x

Gdzie floor to zaokrąglanie w stronę minus nieskończoności, a truncate - zaokrąglanie w stronę zera.
}
2009-09-14 00:08:39 = Plan_B
{
Też miałem z tym problem. Budowałem na studiach program w FORTRANie i bufor cykliczny za cholerę nie działał, jak sobie umyśliłem. W programie wychodziła ujemna reszta, czego z początku nie byłem świadom. Bardzo się zdziwiłem, że to tak działa.

Korzystałem z funkcji MOD(X,Y). Moje intuicyjne pojęcie reszty, zwłaszcza pojęcie modulo, "od zawsze" obejmowało okresowość funkcji (przy ustalonym dzielniku). To pewnie z tego powodu, iż okresowość jawiła i nadal jawi mi się ogólnie potrzebniejsza niż reszty różnych znaków. Poza tym definicja reszty zawsze nieujemnej prostsza jest od definicji zacytowanej z Wikipedii, a na dodatek daje jednoznaczny wynik; dla zwolennika brzytwy Ockhama to wystarczy. KISS!

Byłem ciekaw, jak zapatruje się na to prowadzący zajęcia i czy kiedyś miał podobny problem. Otóż nie miał, bo przecież "wiadomo, że modulo to reszta z dzielenia, a ta może być ujemna". Mieliśmy całkowicie odmienne intuicje.
}
2009-09-14 08:57:54 = Yelonek
{
Ja od razu pomyślałem, że 12 / -5 = -2 r 2, a -12 / 5 = -3 r 3. W liceum usłyszałem, że reszta z dzielenia może być tylko dodatnia i tego będę się trzymał. Tak jak kolega wyżej uważam, że ta definicja jest prosta i jednoznaczna, więc najlepsza.
}
2009-09-14 09:04:34 = G
{
To ja dorzucę jeszcze 3 grosze:
http://codepad.org/g1CnuMv8

+ man fmod:
"if y is non-zero, the result has the same sign as x and magnitude less than the magnitude of y"

w pythonie też jest fmod, a co do wbudowanego operatora:
"The modulo operator always yields a result with the same sign as its second operand (or zero); the absolute value of the result is strictly smaller than the absolute value of the second operand"
http://codepad.org/4B1qKZkT

Zastanawiające natomiast jest zachowanie haskella:
http://codepad.org/HXBAy2xk
}
2009-09-14 09:39:18 = TeMPOraL
{
Odnośnie mojego poprzedniego komentarza, przykłady w CommonLisp:

http://nopaste.gamedev.pl/?id=4378
}
2009-09-14 12:34:20 = diabel
{
Gyn, jeszcze troche i udowodnisz, że -2+2=3 czytajac Twoją stronę zawsze stwierdzam, że nic nie umiem z matmy :P :P a propo to przypomina mi ta sprawe co badales z kolejnoscia wykonywania dzialan gdzie na roznych kompilatorach rozne wychodzily wyniki ;)
}
2009-09-14 13:03:23 = Kalesanty
{
Działanie modulo n w liczbach całkowitych tworzy relację równoważności. Każdy zbiór liczb równych sobie modulo n tworzy klasę abstrakcji i tak np. Wszystkie liczby podzielne przez 3 należą do jednej klasy abstrakcji (dla działania modulo 3). Podstawowym twierdzeniem o klasach abstrakcji jest, że wszystkie klasy abstrakcji są rozłączne, czyli nie istnieje taki element, który należy do dwóch różnych klas abstrakcji
Dla pierwszej definicji (książkowej) mamy:
-12 przez 5 = -3 i reszty 3 czyli -12 należy do jednej klasy abstrakcji.
Działając wg definicji Wikipedii mamy:
42 = 9(-5) + 3
albo
-42 = 8(-5) + (-2)
Czyli 42 należy do dwóch różnych klas abstrakcji, co oczywiście nie może być prawdą. Czyli druga definicja jest błędna.
}
2009-09-14 14:18:48 = baranowb
{
@Yelonek
-12 / 5 = -3 r 3
12 / 5 = 2 r 2

?? Gdzie tutaj logika?
}
2009-09-14 14:24:53 = G
{
@Kalesanty

Drogi kolego, druga część twojego rozumowania jest ciut błędna.
Tam nie ma definicji, tam są dwie alternatywne możliwości.

Niech a equiv b (mod n).

Wszystko zależy od przyjętej definicji reszty.
Jeśli przyjmiemy, że b ma mieć ten sam znak co a, to
cytowaną przez Ciebie definicję drugą i 9 rozłącznych klas abstrakcji.

Jeśli przyjmiemy że b ma być zawsze >= 0, to
mamy pięc rozłącznych klas abstrakcji.
}
2009-09-14 15:54:26 = Tobi
{
a wiecie, jak brzmią pierwsze dwie zasady internetu? (w wolnym tłumaczniu)

1. Nie rozmawiać o |b|
2. NIE rozmawiać o |b|

}
2009-09-14 16:15:15 = IS
{
W pierścieniu (tutaj liczb całkowitych) reszta z dzielenia wyznaczona jest z dokładnością do przywiedlności - NIE jest jednoznaczna. Patrz "Algebra ogólna" A. Białynicki-Birula. Tego nie nauczą w liceum, ale najlepsi specjaliści muszą mieć to na uwadze.
}
2009-09-14 16:41:06 = Krzyś
{
$ echo 'import decimal as d;print( "%d %dr, %d %dr" % (d.Decimal("-12") / d.Decimal("5"), d.Decimal("-12") % d.Decimal("5"), d.Decimal("12") / d.Decimal("-5"), d.Decimal("12") % d.Decimal("-5")) )' | python

-2 -2r, -2 2

:-D
}
2009-09-14 19:34:23 = prs
{
Jak widać z Waszych wywodów, rzeczywiście z matematyki nic nie umiecie.
Skoro nie znacie podstaw, to już jakiekolwiek wywody na bardziej zaawansowane zagadnienia mijają się w Waszym przypadku z celem. :P

W matematyce są definicje (prawa) lub aksjomaty działań.
W dzieleniu z resztą definicja jest JEDNOZNACZNA!!!

RESZTA należy do zbioru liczb NATURALNYCH, dla tych co nie wiedzą co to za zbór liczb....
..są to liczby WIĘKSZE od ZERA i CAŁKOWITE!!

Czyli reszta MUSI być większa od ZERA!

koniec kropka. :P
}
2009-09-14 19:44:59 = prs
{
Czytając swój post stwierdziłem, że jest trochę infantylny i nie za wiele wyjaśnia dlaczego tak, a nie inaczej.

Otóż...
W matematyce odnosi się za pomocą liczb rzeczywistość. (upraszczając)
I dzieląc np. linę długość powiedzmy 14 metrów na 4 odcinki. (zakładając, że mają do być odcinki o stałych wielkościach i zawierać się w zbiorze liczb całkowitych)
Dostaniemy ZAWSZE 4 odcinki po 3 metry i 2 metry 'reszty'.
Nie ma możliwości, aby dostać 4 metrowe odcinki i 'pożyczyć' skądś 2 metry liny.

Dlatego dzielenie liczb całkowitych z resztą, daje zawsze resztę dodatnią.
}
2009-09-15 08:09:08 = Jurgi Filodendryta
{
Jako że ja się z matematyką pożegnałem dawno temu, poprosiłem o wykład znajomego (internetowo) matematyka. Efekt tutaj: http://andsol.blox.pl/2009/09/Na-ogolne-zyczenie-publicznosci.html
}
2009-09-15 08:48:49 = G
{
@prs: tak i na pewno twoje rozumowanie wyjaśnia jak podzielić odcinek o długości -14 metrów, gratuluję ignorancji
}
2009-09-15 10:14:38 = Gynvael Coldwind
{
@prs, G (ostatni post)
Prosiłbym bez osobistych wjazdów, trzymajmy dyskusje na poziomie ;>

@Tobi
Hehe dobree ;> (btw chyba w oryginale /b/ było ne ?;>)

@Jurgi
Chyba chwilę przed tobą dorzuciłem to do postu jako update 3 ;> (tak, nadal przeglądam referery ;>)
Świetny post btw gość napisał ;>

@all
Sporo się dowiedziałem z komentarzy ;>
}
2009-09-15 11:12:56 = Leming
{
@Gynvael
Mimo, że pracujesz na Windowsie, to nigdy nie widziałem ani linijki kodu w np. C# (jakieś uprzedzenia?) ;> Tak mnie to zaciekawiło jakoś, szkoda, że nie mam tu VS'a, bo bym sprawdził co on na to.
}
2009-09-15 12:09:09 = Gynvael Coldwind
{
@Leming
Małe sprostowanie: pracuje w pracy na Windowsie ;> W domu na głównym kompie mam Kubuntu, a na lapku OSX'a ;> Raczej staram się nie ograniczać jeśli o OS chodzi ;>
Co do czemu nie widziałeś C#. Cóż, akurat ten język cały czas na liście "ToDo" u mnie leży hehe ;>
Natomiast to good idea żeby sprawdzić i C# i Jave. Zrobię to potem ;>
}
2009-09-15 13:10:05 = Neonek
{
Co C# na to ? To mi VS pod Vistą 32bit Home Premium pokazało:
-12 / 5: -2 r -2
12 / -5: -2 r 2
BTW bardzo ciekawy problem, zapytam się jutro matematyczki co o tym sądzi, jak będzie miała czas :)
}
2009-09-21 13:47:51 = Jurgi Filodendryta
{
@Gynvael — Nie zauważyłem, że jest update. Szybko reagujesz. ;) I tak, mr Andrzej Solecki nie tylko świetnie zna się na matmie (w końcu ją wykłada), ale i świetnie o niej pisze. Nawet taki humanista jak ja daje się wciągnąć. Polecam jego wpisy matematyczne.
}
2009-09-24 12:13:29 = puchaty
{
Nie rozumiem problemu, przeciez -2 i reszty -2 to dokladnie tyle samo co -3 i reszty 3. IMHO nie warto wdawac sie w rozwazania ktora reszta jest prawidlowa (bo to tylko kwestja definicji), trzeba po prostu uzyc ta ktora jest nam potrzebna.
}
2009-09-25 12:42:52 = Sobol
{
@prs
Wybacz, ale głupoty wypisujesz, po pierwsze bzdura ideowa:
"W matematyce odnosi się za pomocą liczb rzeczywistość. (upraszczając)"
Pomijając poprawność językową tego zdania, matematyka jest narzędziem, opis "rzeczywistości", czyli jak mniemam fizycznego jej modelu to tylko jedno z zastosowań matematyki, a zastosowania są nieograniczone.

Po drugie
"RESZTA należy do zbioru liczb NATURALNYCH, dla tych co nie wiedzą co to za zbór liczb...."
To ciekawe co mówisz, bo wg. algebry abstrakcyjnej reszta jest tylko operatorem matematycznym, a te mogą być określone na każdym zbiorze tworząc razem z nim i innymi operatorami strukturę - czy to będzie pierścień czy kraty czy whatever, zawsze (jak w programowaniu) chodzi o dane + operacje, a operacje można przeciążać :P (jak tłumaczyć matmę koderowi? :D)

Na czym polega problem z resztą - właśnie na określeniu na jakich danych operujemy, ale obie przytoczone definicje są poprawne :)
}
2009-09-26 17:14:49 = puchaty
{
Sobol: zalezy co sie rozumie przez slowo rzeczywistosc, jesli mowimi o "calej" rzeczywistosci (uniwersum) to matematyka poza nia nie wykracza - jest narzedziem do poprawnego operowania na jej czesciach. Jesli rzeczywsitosc to jakis uproszczony (np. fizyczny) model swiata to j.w. czyli ok ;p
}
2009-09-27 21:30:50 = Sobol
{
Przez rzeczywistość rozumiem przyrodę - czy to tą bliską nam, opisywaną przez klasyczną fizykę, chemię, biologię, czy tą mikroskopijną, opisywaną przez fizykę kwantową i statystyczną, mikrobiologię, czy choćby astronomia. Oczywistym jest, że wszystko, co człowiek wymyśli, można wrzucić w szufladkę "rzeczywiste", w takim podejściu nie ma rzeczy, których w tej szufladce nie umieścimy :P Ale czy np. teoria chaosu z dziwnymi atraktorami na czele jest opisem rzeczywistości, czy tylko narzędziem do opisu pewnego modelu? :) Chciałem tylko uświadomić koledze prs, że nie wszystko jest takie proste i oczywiste jak to uczą w liceum na matmie ;) Peace
}
2016-06-03 11:27:41 = exu
{
W go:
(-12) % 5 = -2
12 % (-5) = 2
}
2016-06-03 11:29:24 = exu
{
(-12) % 5 = -2
(-12) / 5 = -2
12 % (-5) = 2
12 / (-5) = -2
}
2018-02-06 15:50:54 = Arrrr
{
Uczyli mnie że reszta jest zawsze nieujemna, bo to ponoć takie naturalne. Z drugiej strony nadal czekam aż otrzymam od pewnego osobnika "resztę" długu :)
Więc w sumie to kwestia założeń. Wynik jest zawsze taki sam i można go dalej używać choćby w rachunkach modulo.
}
2021-10-10 16:10:25 = Maveius
{
Ha! wiem w czym rzecz, zgodnie z definicją matematyczną reszta z dzielenia skoro musi znajdować się w przedziale <0, d) to oznacza, że zarówno intuicja jak i języki oprogramowania nie sprawdzają ostatniego warunku.
-12 / 5 = -2,4
12 / 5 = 2,4
to oznacza, że 4/10 = 2/5 stąd zawsze reszta będzie dodatnia a znak ustalany jest na końcu więc chcąc być bardziej poprawnym o ile znajdujemy równanie -12 == (-2 * 5) - 2 to brakuje tu ostatniego etapu (wyciągnięcia wspólnego czynnika przed nawias) czyli wartość bezwzglęna z -2 to 2 :D więc naszą resztą zawsze jest wartość dodania r = |r'| gdzie r' to pozostała część równania. Po wyciągnięciu czynnika przed nawias (-1) otrzymamy:
-12 = -((2*5) + 2)

Kolejny przypadek 12 / -5
12 == (-2 * -5) + 2 - w tym przypadku r = |r'| więc r = 2 bo r' = 2 => tu nie ma potrzeby wyciągać -1 bo znajduje się tylko po jednej stronie równania (przed znakiem "+") czyli mamy dokładnie pełną i zgodną formę i po przemnożeniu -2*-5 > 0
tak samo jak (2*5) > 0.

Taka moja hipoteza.
}

Add a comment:

Nick:
URL (optional):
Math captcha: 5 ∗ 5 ＋ 8 =