Modulový provoz - Modulo operation

  Kvocient (q) a   zbytek (r) jako funkce dividendy (A), za použití různých algoritmů

v výpočetní, modulo provoz vrátí zbytek nebo podepsaný zbytek a divize, poté, co je jedno číslo rozděleno jiným (nazývá se modul operace).

Vzhledem k tomu, dvě kladná čísla A a n, A modulo n (ve zkratce A mod n) je zbývající část Euklidovské dělení z A podle n, kde A je dividenda a n je dělitel.^[1] Modulární provoz je třeba odlišit od symbolu mod, který odkazuje na modul^[2] (nebo dělitel) jeden operuje z.

Například výraz „5 mod 2“ by se vyhodnotil na 1, protože 5 dělený 2 má a kvocient 2 a zbytek 1, zatímco „9 mod 3“ by se vyhodnotil jako 0, protože dělení 9 na 3 má podíl 3 a zbytek 0; po trojnásobném vynásobení 3 není co odečíst od 9.

(Zde si všimněte, že dělení s kalkulačkou neukáže výsledek operace modulo a že podíl bude vyjádřen jako desetinný zlomek, pokud se jedná o nenulový zbytek.)

Ačkoli se obvykle provádí s A a n oba jsou celá čísla, mnoho výpočetních systémů nyní umožňuje jiné typy numerických operandů. Rozsah čísel pro celé číslo modulo z n je 0 až n − 1 včetně (A mod 1 je vždy 0; A mod 0 není definováno, což může mít za následek a dělení nulou chyba v některých programovacích jazycích). Vidět modulární aritmetika pro starší a související konvenci použitou v teorie čísel.

Když přesně jeden z A nebo n je negativní, naivní definice se rozpadá a programovací jazyky se liší v tom, jak jsou tyto hodnoty definovány.

Varianty definice

v matematika, výsledek modulo provoz je třída ekvivalence, a kterýkoli člen třídy může být vybrán jako reprezentativní; obvyklým zástupcem je však nejméně pozitivní rezidua, nejmenší nezáporné celé číslo, které patří do dané třídy (tj. zbytek Euklidovské dělení ).^[3] Jsou však možné i jiné konvence. Počítače a kalkulačky mají různé způsoby ukládání a reprezentace čísel; tedy jejich definice činnosti modulo závisí na programovací jazyk nebo podkladový Hardware.

Téměř ve všech výpočetních systémech kvocient q a zbytek r z A děleno n splňují následující podmínky:

${ displaystyle { begin {zarovnáno} q , & in mathbb {Z} a , & = nq + r | r | , & <| n | end {zarovnáno}}}$

(1)

To však stále ponechává nejednoznačnost znaménka, pokud je zbytek nenulový: nastanou dvě možné volby pro zbytek, jedna negativní a druhá pozitivní a dvě možné volby pro kvocient. V teorii čísel je vždy kladný zbytek zvolen, ale ve výpočetní technice si programovací jazyky vybírají v závislosti na jazyku a znakech A nebo n.^[1] Standard Pascal a ALGOL 68 například dejte kladný zbytek (nebo 0) i pro záporné dělitele a některé programovací jazyky, například C90, to nechají na implementaci, když některý z n nebo A je záporné (viz tabulka níže) § V programovacích jazycích pro detaily). A modulo 0 je ve většině systémů nedefinováno, i když některé jej definují jako A.

Jak popsal Leijen,

Boute tvrdí, že euklidovské dělení je lepší než ostatní, pokud jde o pravidelnost a užitečné matematické vlastnosti, ačkoli podlahové dělení podporované Knuthem je také dobrou definicí. Přes jeho široké použití se ukázalo, že zkrácené rozdělení je horší než ostatní definice.

— Daan Leijen, Divize a modul pro počítačové vědce^[6]

Běžné úskalí

Pokud má výsledek operace modulo známky dividendy, může to vést k překvapivým chybám.

Chcete-li například otestovat, zda je celé číslo liché, můžete chtít otestovat, zda se zbytek o 2 rovná 1:

bool is_odd(int n) {    vrátit se n % 2 == 1;}

Ale v jazyce, kde má modulo znak dividendy, je to nesprávné, protože kdy n (dividenda) je záporná a lichá, n mod 2 vrátí -1 a funkce vrátí false.

Jedna správná alternativa je otestovat, že zbytek není 0 (protože zbytek 0 je stejný bez ohledu na znaky):

bool is_odd(int n) {    vrátit se n % 2 != 0;}

Jinou alternativou je použití skutečnosti, že u libovolného lichého čísla může být zbytek buď 1 nebo -1:

bool is_odd(int n) {    vrátit se n % 2 == 1 || n % 2 == -1;}

Zápis

Některé kalkulačky mají a mod () funkční tlačítko a mnoho programovacích jazyků má podobnou funkci vyjádřenou jako mod (A, n), například. Některé také podporují výrazy, které používají "%", "mod" nebo "Mod" jako modulo nebo zbytek operátor, jako

a% n

nebo

mod n

nebo ekvivalent, pro prostředí bez a mod () function ('int' inherentně produkuje zkrácenou hodnotu A/n)

a - (n * int (a / n))

Problémy s výkonem

Modulové operace mohou být implementovány tak, že se pokaždé vypočítá rozdělení se zbytkem. Ve zvláštních případech existují na určitém hardwaru rychlejší alternativy. Například modulo mocnin 2 lze alternativně vyjádřit jako a bitový Provoz AND:

x% 2n == x & (2n - 1)

Příklady (za předpokladu X je kladné celé číslo):

x% 2 == x & 1

x% 4 == x & 3

x% 8 == x & 7

V zařízeních a softwaru, které implementují bitové operace efektivněji než modulo, mohou tyto alternativní formy vést k rychlejším výpočtům.^[7]

Optimalizace překladače může rozpoznat výrazy formuláře výraz% konstanta kde konstantní je síla dvou a automaticky je implementuje jako výraz & (konstanta-1), což umožňuje programátorovi psát jasnější kód bez snížení výkonu. Tato jednoduchá optimalizace není možná pro jazyky, ve kterých má výsledek operace modulo znak dividendy (včetně C), pokud není dividenda nepodepsaný celočíselný typ. Je to proto, že pokud je dividenda záporná, modulo bude záporné, zatímco výraz & (konstanta-1) bude vždy pozitivní. U těchto jazyků rovnocennost x% 2n == x <0? x | ~ (2n - 1): x & (2n - 1) místo toho musí být použito, vyjádřeno bitovými operacemi OR, NOT a AND.

Vlastnosti (identity)

Některé modulo operace lze započítat nebo rozšířit podobně jako jiné matematické operace. To může být užitečné v kryptografie důkazy, například Výměna klíčů Diffie – Hellman.

• Identita:
  • (A mod n) mod n = A mod n.
  • n^X mod n = 0 pro všechny kladné celočíselné hodnoty X.
  • Li str je prvočíslo což není a dělitel z b, pak ab^str−1 mod str = A mod str, kvůli Fermatova malá věta.
• Inverzní:
  • [(−A mod n) + (A mod n)] mod n = 0.
  • b⁻¹ mod n označuje modulární multiplikativní inverzní, který je definován právě tehdy b a n jsou relativně prime, což je případ, kdy je definována levá strana: [(b⁻¹ mod n)(b mod n)] mod n = 1.
• Distribuční:
  • (A + b) mod n = [(A mod n) + (b mod n)] mod n.
  • ab mod n = [(A mod n)(b mod n)] mod n.
• Rozdělení (definice): A/b mod n = [(A mod n)(b⁻¹ mod n)] mod n, když je definována pravá strana (tj b a n jsou coprime ). Nedefinováno jinak.
• Inverzní násobení: [(ab mod n)(b⁻¹ mod n)] mod n = A mod n.

V programovacích jazycích

Zobecnění

Modulo s offsetem

Někdy je to užitečné pro výsledek A modulo n ležet ne mezi 0 a n−1, ale mezi nějakým číslem d a d+n−1. V tom případě, d se nazývá offset. Nezdá se, že by pro tuto operaci existoval standardní notový zápis, takže pokusně použijeme A mod_d n. Máme tedy následující definici:^[15] X = A mod_d n jen pro případ d ≤ X ≤ d+n−1 a X mod n = A mod n. Je zřejmé, že obvyklá modulo operace odpovídá nulovému offsetu: A mod n = A mod₀ n. Provoz modulo s offsetem souvisí s funkce podlahy jak následuje:

A mod_d n = ${ displaystyle a-n left lfloor { frac {a-d} {n}} right rfloor}$.

(To je snadno vidět ${ displaystyle x = a-n levá lfloor { frac {a-d} {n}} pravá rfloor}$. Nejprve to ukážeme X mod n = A mod n. Obecně platí, že (A+bn) mod n = A mod n pro všechna celá čísla b; to tedy platí i v konkrétním případě, kdy b = ${ displaystyle - left lfloor { frac {a-d} {n}} right rfloor}$; ale to znamená, že ${ displaystyle x ; { text {mod}} ; n = left ( left lfloor { frac {ad} {n}} right rfloor right) ; { text {mod} } ; n = a ; { text {mod}} ; n}$, což jsme chtěli dokázat. Zbývá ukázat, že d ≤ X ≤ d+n−1. Nechat k a r být taková celá čísla A − d = kn + r s 0 ≤ r ≤ n-1 (vidět Euklidovské dělení ). Pak ${ displaystyle left lfloor { frac {a-d} {n}} right rfloor = k}$, tím pádem ${ displaystyle x = a-n vlevo lfloor { frac {a-d} {n}} doprava rfloor = a-nk = d + r}$. Nyní vezměte 0 ≤ r ≤ n−1 a přidat d na obě strany, získání d ≤ d + r ≤ d+n−1. Ale viděli jsme to X = d + r, takže jsme hotovi. □)

Modulo s offsetem A mod_d n je implementováno v Mathematica tak jako^[15] Mod [a, n, d].

Viz také

• Modulo (disambiguation) a modulo (žargon) - mnoho použití slova modulo, z nichž všechny vyrostly Carl F. Gauss Úvod do modulární aritmetika v roce 1801.
• Modulo (matematika), obecné použití termínu v matematice
• Modulární umocňování
• Turn (jednotka)

Poznámky

• ^ Perl obvykle používá aritmetický modulo operátor, který je nezávislý na stroji. Příklady a výjimky najdete v dokumentaci Perl o multiplikativních operátorech.^[16]
• ^ Matematicky jsou tyto dvě možnosti pouze dvěma z nekonečného počtu možností, které jsou k dispozici nerovnost uspokojena zbytkem.
• ^ Dělitel musí být kladný, jinak nedefinovaný.
• ^ Jak je implementováno v ACUCOBOL, Micro Focus COBOL a dalších možných.
• ^ ^ Pořadí argumentů se obrací, tj. α | ω počítá ${ displaystyle omega { bmod { alfa}}}$, zbytek při dělení ω podle α.
• ^ Jak popisuje Boute, definice ISO Pascal div a mod neposlouchejte identitu divize, a jsou tedy zásadně rozbití.

Reference

externí odkazy

• Modulorama, animace cyklické reprezentace multiplikačních tabulek (vysvětlení ve francouzštině)