Zbytek po dělení

Z Wikipedie, otevřené encyklopedie

Skočit na: Navigace, Hledání

Zbytek po dělení nebo také modulo je početní operace související s operací celočíselného dělení. Například 7 / 3 = 2 se zbytkem 1. Také můžeme říci, že 7 modulo 3 = 1, zkráceně 7 mod 3 = 1. Je-li zbytek po dělení a/n nula, říkáme že a je dělitelné n.

Obsah

[editovat] Záporná čísla

Protože není intuitivně jasné, jak by se měla operace zbytku po dělení chovat u záporných čísel, používají se přinejmenším dvě definice této operace:

  • "Matematická varianta":
(a\;\bmod\;m)= a - \left \lfloor \frac{a}{m} \right \rfloor \cdot m
Závorky \lfloor \cdot \rfloor zde označují nejbližší celé číslo menší než podíl a:m. Pro tuto variantu platí:
(a + km)\;\bmod\;m = a\;\bmod\;m\quad(k\in\mathbb Z),
ale nastávají případy, kdy
(-a)\;\bmod\;m \ne-(a\;\bmod\;m), např. (-2)\;\bmod3=1\ne-2=-(2\;\bmod\;3).
Je-li m kladné, pak a\;\bmod\;m\geq0 pro všechna a.
  • "Symetrická varianta":
(a\;\bmod\;m) = a - m\cdot (a\,\operatorname{div}\,m);
kde a\,\operatorname{div}\,m označuje směrem k nule zaokrouhlený podíl a / m. Pro tuto variantu platí
( − a)mod m = − (amod m),
ale nastávají případy, kdy
(a + km)\;\bmod\;m\ne a\;\bmod\;m, např. (1 - 3)\;\bmod\;3=(-2)\;\bmod\;3=-2\ne 1=1\;\bmod\;3.
a\;\bmod\;m zde má stejné znaménko jako a, pokud není a\;\bmod\;m = 0.

V programovacích jazycích je častěji implemntována druhá varianta. Pokud je a\geq 0 a současně m > 0, dávají obě varianty stejné výsledky.

[editovat] Použití

V praktickém životě se modulo někdy používá jako prostředek pro kontrolu úplnosti a správnosti. Například většina rodných čísel osob narozených po roce 1953 je dělitelných číslem 11.[1]

Operace modulo se hojně využívá v programování a návrhu algoritmů, např. při testu sudosti čísla nebo výpočtu dne v týdnu. Také se často používá při generování kontrolních součtů, které bývají součástí komunikačních protokolů.

Je také důležitou součástí algebry, kde se při konstrukci konečných celočíselných algeber využívá modulární aritmetika.

[editovat] Operace modulo

Některé kalkulačky mají tlačítko s funkcí mod a mnoho programovacích jazyků má funkci mod nebo přímo operátor mod nebo %. Zápis operace modulo může být

a % n

nebo

a mod n

nebo

mod(a, n)

[editovat] Modulo a číselné soustavy

Platí, že v číselné soustavě o radixu N představuje zbytek po dělení číslem N, N², N³, N4, …, Ni, … poslední jednu, dvě, tři, čtyři, …, respektive i číslic z dělence.

Toho se někdy využívá ve výpočetní technice (kde se v drtivé většině případů používá binární soustava). V případech, kdy je třeba zjistit zbytek po dělení dvěma, čtyřmi, osmi, …, 2i, … se místo (na výpočetní výkon náročnější) operace dělení provádí bitový součin (též bitová konjunkce, operace AND), kde druhým operandem je 2i − 1.

[editovat] Příklad

170 mod 64

Zbytek po dělení je 42. Druhý operand, 64, je 26, lze tedy použít bitový součin s číslem 26-1. Pokud bychom tedy spočítali 170 and 63, dostaneme:

číslo binárně číslo dekadicky
10101010 170
and 00111111 63
= 00101010 42

[editovat] Související články

[editovat] Reference

  1. ↑ Katalog datových prvků ISVS
Citováno z „http://cs.wikipedia.org/wiki/Zbytek_po_d%C4%9Blen%C3%AD“