Modular Arithmetic
মডুলার গণিত
ঘড়ির গণিত — একটা নির্দিষ্ট modulus-এ পৌঁছে সংখ্যা আবার শূন্যে ফেরে। `a ≡ b (mod n)` মানে `n`, `a−b` কে ভাগ করে।
also: clock arithmetic, mod
(a + b) mod n আর (a · b) mod n — যোগ ও গুণ modulus-এর ভেতরে
ভালোভাবে সংজ্ঞায়িত, তাই মাঝপথে বারবার mod নেওয়া যায়:
(a * b) % n == ((a % n) * (b % n)) % nবড় সংখ্যার গণনায় এটাই overflow ঠেকায়।
CS-এ সবচেয়ে গুরুত্বপূর্ণ ঘটনা: two’s complement আসলে
arithmetic mod 2ⁿ। একটা uint8_t-এ 255 + 1 = 0 কোনো bug নয় —
এটা mod 256 গণিত, ঠিক যেমন ঘড়িতে ১২-এর পর ১।
অন্য যেখানে:
- Hash bucket:
h % m(primemকেন ভালো — কম pattern) - Cyclic buffer:
(head + 1) % capacity, বা& (n−1)যদিnদুইয়ের ঘাত হয় - TCP sequence number wraparound (PAWS)
- Checksum — Luhn, ISBN, IBAN
- CRC = polynomial arithmetic mod 2
Modular bias: rand() % n সমান বণ্টন দেয় না যদি RAND_MAX+1
n-এর গুণিতক না হয়। Cryptographic প্রসঙ্গে rejection sampling
ব্যবহার করুন।