Modulo (jääk): jagamisjääk matemaatikas ja programmeerimises

Matemaatikas on modulo-operatsiooni tulemus aritmeetilise jagamise jääk. Teatavasti annab kahe täisarvu aritmeetiline jagamine kvooti ja jäägi.

Võimalikud on siiski ka muud konventsioonid. Arvutitel ja kalkulaatoritel on erinevaid viise arvude salvestamiseks ja esitamiseks. Nende modulo-operatsiooni määratlus sõltub programmeerimiskeelest ja/või aluseks olevast riistvarast.

Mis on modulo (jääk)?

Kui jagame täisarvu a täisarvuga n (n ≠ 0), siis saame jagatise (kvoodi) q ja jäägi r nii, et kehtib võrrand

a = q · n + r, kus r on jääk.

Matemaatikas on tavaline eeldus (Euclid'i jagamise definitsioon), et jääk r rahuldab tingimust 0 ≤ r < |n| (kui n on positiivne, siis 0 ≤ r < n). Sellisel juhul räägitakse modulo n jäägist või a mod n-st.

Märgitused ja omadused

• Notatsioon: a mod n või a ≡ b (mod n) (viimane tähistab kongruentsust ehk seda, et n jagab arvu a−b).
• Põhiomadused:
  • (a + b) mod n = ((a mod n) + (b mod n)) mod n
  • (a − b) mod n = ((a mod n) − (b mod n)) mod n
  • (a · b) mod n = ((a mod n) · (b mod n)) mod n
• Jagamise puhul: modulo ei käitu nagu tavaline jagamine — näiteks ei ole üldjuhul (a / b) mod n tähenduslik ilma täiendavate tingimusteta (vajalik on pööratavus, st b peab olema mooduli n suhtes ühise algtegurita, et oleks olemas multiplicative inverse).

Näited

• 13 mod 5 = 3, sest 13 = 2·5 + 3 ja 0 ≤ 3 < 5.
• -7 mod 3 (matemaatilise Euclid'i definitsiooni järgi) = 2, sest -7 = (-3)·3 + 2 ja 0 ≤ 2 < 3.

Erinevused matemaatikas ja programmeerimises

Kuigi matemaatikas eelistatakse jääki r, mis on võrdne 0 ≤ r < |n|, siis programmeerimiskeelte implementatsioonid võivad jääki määrata teisiti sõltuvalt sellest, kuidas toimub täisarvu jagamine (ümmardamine alla, üles või nulli suunas). Enamlevinud erinevused:

• Python: operaator % tagab, et jääk omab sama märki kui jagaja (divisor). Näiteks:
  • 7 % 3 = 1
  • -7 % 3 = 2 (sest Python kasutab jagamisel allapoole (floor) ümardamist)
• C, C++ (C99 ja uuemad) ja Java: jäägi märk vastab jäägi allikale (dividendile), sest jagamine ümardatakse nulli suunas. Näited:
  • 7 % 3 = 1
  • -7 % 3 = -1 (kuna -7 / 3 = -2 (trunc toward zero), jääk r = -7 - (-2·3) = -1)
• Seega sama avaldis a % n võib anda eri keeltes või platvormidel eri tulemuse, kui a või n on negatiivne.

Kus modulo-d kasutatakse?

• Kellaaegade arvutused (tsükliline ehk ringiline arvutus — kell 24 tundi, minutid mod 60 jne).
• Krüptograafia ja modular arithmetic (nt RSA, Diffie–Hellman).
• Hash-tabelid ja juhuslikkus (hashi väärtuse piiramine massiivi indeksite vahemikku: index = hash(key) mod size).
• Tsüklilised andmestruktuurid (ringpuhverid) ja perioodilised mustrid.

Kokkuvõte

Modulo tähistab jagamisel ülejäänud osa ehk jääki. Matemaatikas kasutatakse tavaliselt Euclidi jääki (0 ≤ r < n), kuid arvutisüsteemides ja programmeerimiskeeltes võib jäägi märk ja väärtus sõltuda jagamise ümardamisreeglist. Seetõttu on oluline teada konkreetse keelreisiku käitumist, eriti kui töötatakse negatiivsete arvudega või porteeritakse koodi erinevate platvormide vahel.

Otsing