szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 5 cze 2015, o 11:55 
Użytkownik

Posty: 4
a mod n
Artykuł na angielskiej Wikipedii opisuje różne sposoby definiowania operacji modulo. Wśród nich trzy najważniejsze to:

1.) Iloraz "przycinający" w stronę zera (ang. truncating division). Najczęściej spotykany w językach programowania i kompilatorach. Reszta ma ten sam znak co dzielna.
2.) Iloraz z podłogą (ang. floored division). Wersja stosowana przez D. Knutha w TAOCP i Matematyce konkretnej, a także przez mojego wykładowcę matematyki dyskretnej. Reszta ma ten sam znak co dzielnik.
3.) Iloraz euklidejski (?). Dla mnie najbardziej egzotyczny sposób. Potencjalnie ten najbardziej "poprawny" w matematyce (teoria liczb). Reszta jest zawsze nieujemna.

Oznaczenia:
a\hbox{ -- dzielna}\\n\hbox{ -- dzielnik}\\q \hbox{ -- iloraz}\\r\hbox{ -- reszta}

Niezależnie od przyjętej definicji ilorazu mamy:

q \in \mathbb Z \\
a = nq+r \\
|r| < |n|

Interesuje mnie wykazanie właściwości (znaku) reszty w poszczególnych sposobach. Autor artykułu twierdzi, że przyjmując q = \mathrm{trunc}\,(a/n), na podstawie powyższych właściwości ogólnych możemy stwierdzić, że reszta ma ten sam znak co dzielna. Podobnie, z q = \lfloor a/n \rfloor ma wynikać, że reszta ma ten sam znak co dzielnik.

Czy ktoś z Was mógłby to wykazać?
Góra
Mężczyzna Offline
PostNapisane: 15 cze 2015, o 13:37 
Użytkownik

Posty: 4
A nie jednak proste.

2.) q=\left\lfloor\frac{a}{n}\right\rfloor

Teza:

\text{sgn}(a\,\hbox{mod}\,n) = \mathrm{sgn}(n)\ \ \hbox{dla }a\,\hbox{mod}\,n  \neq 0

Dowód:

\begin{cases}a-n\left\lfloor\frac{a}{n}\right\rfloor > 0\ \ \hbox{dla }n>0 \right\\
a-n\left\lfloor\frac{a}{n}\right\rfloor < 0\ \ \hbox{dla }n<0\end{cases}\implies
\quad\frac{a}{n}>\left\lfloor\frac{a}{n}\right\rfloor\ \ \text{dla } n \neq 0

co wynika z własności podłogi

0 \le x - \lfloor x \rfloor < 1

i tego, że reszta jest niezerowa.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Modulo, krótszy zapis  Tetriando  1
 Wyznaczanie dzielnika i reszty  Starling  1
 różne reszty przy dzieleniu przez 3, iloczyn liczb  agusSia  1
 dzielenie przez 5,6,60 i reszty  ooolllaaa8883  6
 Znak "|" w działaniach  adri@n  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl