6. Aritmatika Modulo

Modulo atau modulus adalah operasi matematika yang menghasilkan sisa pembagian dari suatu bilangan terhadap bilangan yang lain. Modulo biasa dinotasikan sebagai:

a mod b = c (dibaca: a modulo b = c), yang berarti 

• a = n x b + c , atau a / b = c , dengan syarat: 0≼ c < b
• b disebut modulus atau modulo, dan hasil aritmetika modulo b terletak di dalam himpunan {0, 1, 2, ..., b-1}.

dimana:

a = bilangan bulat

b = bilangan asli

c = sisa pembagian

Berikut ini sifat-sifat dasar Modulo:

Contoh:

1. 23 mod 5 = c

    Jawab: 

23/5 sisa c, jadi c = 3

atau:

23 = ... x 5 + ...

23 = 4 x 5 + 3

Jadi 23 mod 5 = 3

2. 0 mod 5 = c

    Jawab: 

0 = ... x 5 + ...

0 = -1 x 5 + 5 ini tidak boleh karena c ≽ b atau 0≼ c < b 

jadi yang benar adalah: 0 = 0 x 5 + 0

Jadi 0 mod 5 = 0

3. - 41 mod 9 = c

    Jawab: 

- 41 = - 4 x 9 + c

- 41 = -36 + c

c = - 41 + 36

c = - 5 ini tidak boleh, karena syarat sisa atau c tidak boleh kurang dari 0 atau negatif, maka untuk menjadikannya bernilai positif dengan cara menjumlahkan nilai - 5 dengan 9 (- 5 + 9 = 4)

Jadi - 41 mod 9 = 4

4. 6 mod 8 = c

      Jawab:

6 = ... x 8 + c

6 = 0 x 8 + c

c = 6 - 0

c = 6

Jadi 6 mod 8 = 6

FUNGSI HASH

• Menempatkan suatu record yang mempunyai nilai kunci k pada suatu lokasi memori yang beralamat h(k).
• Data yang disimpan di dalam memori komputer perlu ditempatkan dalam suatu cara sedemikian sehingga pencariannya dapat dilakukan dengan cepat.
• Setiap data yang berupa record mempunyai field kunci yang unik yang membedakan suatu record dengan record lainnya.
• Bentuk umumnya h(k) = k mod m, m adalah jumlah lokasi memori yang tersedia (berbentuk sel-sel yang diberi indeks 0 sampai m-1)

Contoh

Tunjukkan bagaimana sekumpulan data dengan kunci-kunci sebagai berikut: 15, 558, 32, 132, 5, 102, dan 48, ditempatkan pada sel-sel sebanyak 11 alokasi memori

Penyelesaiannya

Diketahui:

Kunci 15, 558, 32, 132, 5, 102 dan 48

m = 11 (sel memori diberi indeks 0 sampai 10)

Jawab:

h(k) = k mod m, maka 

h(15) = 15 mod 11 = 4

h(558) = 558 mod 11 = 8

h(32) = 32 mod 11 = 10

h(132) = 132 mod 11 = 0

h(5) = 5 mod 11 = 5

h(102) = 102 mod 11 = 3

h(48) = 48 mod 11 = 4

Keadaan memori setelah penyimpanan keenam data record tersebut digambarkan sebagai berikut:

Pada sel memori lokasi 4 sudah terisi, sehingga terjadi bentrokan (collision) dalam penempatan suatu data record.

Perlu diterapkan kebijakan resolusi bentrokan (collusion resolution policy), suatu kebijakan resolusi bentrokan dengan mencari sel tak terisi tertinggi berikutnya (dengan 0 diasumsikan mengikuti 10)

Fungsi hash digunakan pencarian data record tertentu. Untuk mencari data record dengan kunci p, dengan menghitung h(p) = p mod 11, misalkan h(p) = q. Jika record p sama dengan isi sel pada lokasi q, maka lokasi record p ditemukan. Tetapi jika record p tidak sama dengan isi pada lokai q, maka lihat posisi tertinggi berikutnya. Jika p tidak berada pada posisi ini, maka lihat lagi posisi berikutnya. Jika mencapai sel kosong atau kembali ke posisi semula, maka record p tidak ada.

Latihan Soal:

1. 7 mod 9 = ...
2. 35 mod 8 = ...
3. 120 mod 13 = ...
4. (2011+2012+2013+ .......+2018) mod 2019 = ...
5. (7 x 9 x 10) mod 8 = ....

Kaidah dasar 2 (Linearitas penjumlahan/ pengurangan): (a+b) mod n = ((a mod n)+(b mod n)) mod n

(10+17+21) mod 9 = ....

Jawab:

(10+17+21) mod 9 

= (10 mod 9)+(17 mod 9)+(21 mod 9)

= (1+8+3) mod 9

= 12 mod 9

= 3 mod 9

= 3

Kaidah dasar 3 (Linearitas perkalian): (ab) mod n = ((a mod n)(b mod n)) mod n

(7 x 9 x 10) mod 8 = ...

Jawab:

(7 x 9 x 10) mod 8

= ((7 mod 8) x (9 mod 8) x (10 mod 8)) mod 8

= (7x1x2) mod 8

= 14 mod 8

= 6

Kaidah dasar 4 (Perpangkatan): 

Contoh soal:

Operasi pada kongruensi Modulo