Metode linear kongruen

Metode linear kongruen (linear congruent method, bisa disingkat LCM) merupakan metode pembangkit bilangan acak yang banyak digunakan dalam program komputer. LCM memanfaatkan model linier untuk membangkitkan bilangan acak yang didefinisikan dengan :

$X_{n+1}=\left(aX_{n}+c\right)~~{\bmod {~}}~m$

Di mana :

• xn = adalah bil. acak ke n
• a dan c adalah konstanta LCM
• m adalah batas maksimum bilangan acak

Ketentuan-ketentuan pemilihan setiap parameter pada persamaan di atas adalah sebagai berikut:
a. m = modulus, 0 < m
b. a = multiplier (pengganda), 0 < a < m
c. c = Increment (pertambahan nilai), 0 ≤ c < m
d. X0 = nilai awal, 0 ≤ X0 < m
e. c dan m merupakan bilangan prima relatif
f. a – 1 dapat dibagi oleh faktor prima dari m
g. a – 1 merupakan kelipatan 4 jika m juga kelipatan 4
h. a harus sangat besar

Ciri khas dari LCM adalah terjadi pengulangan pada periode waktu tertentu atau setelah sekian kali pembangkitan, hal ini adalah salah satu sifat dari metode ini, dan pseudo random generator pada umumnya. Penentuan konstanta LCM (a, c dan m) sangat menentukan baik tidaknya bilangan acak yang diperoleh dalam arti memperoleh bilangan acak yang seakan-akan tidak terjadi pengulangan. Dapat dilihat dari contoh seperti di bawah ini :

jumlah soal yang telah disimpan pada database sebanyak 50 soal di mana setiap ujian memiliki 4 pilihan jumlah soal yaitu 10 - 40 soal. Pada setiap soal nomor soal digunakan sebagai kode soal untuk mempermudah pengacakan soal. Agar tidak mengalami pengulangan saat dilakukan pengacakan soal sebanyak 10, 20, 30 atau 40 kali, telah ditentukan nilai konstanta a =11, c=7, X0 (nilai awal diambil acak di mana 0 ≤, X0 < m ) = 1 dan m = 50. Sehingga diperoleh hasil : X[1]= (11*1+7) mod 50. Berikut ini merupakan penerapan metode LCM pada pengacakan urutan soal :

1. x(1) = ( 11 (1) + 7 ) mod 50 = 18
2. x(2) = ( 11 (18) + 7 ) mod 50 = 5
3. x(3) = ( 11 (5) + 7 ) mod 50 = 12
4. x(4) = ( 11 (12) + 7 ) mod 50 = 39
5. x(5) = ( 11 (39) + 7 ) mod 50 = 36
6. x(6) = ( 11 (36) + 7 ) mod 50 = 3
7. x(7) = ( 11 (3) + 7 ) mod 50 = 40
8. x(8) = ( 11 (40) + 7 ) mod 50 = 47
9. x(9) = ( 11 (47) + 7 ) mod 50 = 24
10. x(10) = ( 11 (24) + 7 ) mod 50 = 21
11. x(11) = ( 11 (21) + 7 ) mod 50 = 38
12. x(12) = ( 11 (38) + 7 ) mod 50 = 25
13. x(13) = ( 11 (25) + 7 ) mod 50 = 32
14. x(14) = ( 11 (32) + 7 ) mod 50 = 9
15. x(15) = ( 11 (9) + 7 ) mod 50 = 6
16. x(16) = ( 11 (6) + 7 ) mod 50 = 23
17. x(17) = ( 11 (23) + 7 ) mod 50 = 10
18. x(18) = ( 11 (10) + 7 ) mod 50 = 17
19. x(19) = ( 11 (17) + 7 ) mod 50 = 44
20. x(20) = ( 11 (44) + 7) mod 50 = 42

Maka, bilangan acak yang dibangkitkan adalah : 18, 5, 12, 39, 36, 3, 40, 47, 24, 21, 38, 25, 32, 9, 6, 23, 10, 17, 44, 42.

Berdasarkan perhitungan di atas dapat disimpulkan bahwa dalam pemilihan nilai konstanta pada a, c dan m telah sesuai dan tidak terjadi perulangan dalam menampilkan soal pada saat melakukan ujian. Untuk nilai Xn atau nilai awal akan selalu berubah sesuai dengan jumlah berapa kali pengguna menjawab soal. Jika saat melakukan ujian pertama kali maka nilai Xn = 1, namun jika dia melakukan ujian yang kedua kalinya nilai Xn = 1 + 1

Jumlah soal yang tersedia di dalam database atau jumlah nilai m adalah 50, sehingga hasil bilangan acak/nomor soal yang dihasilkan merupakan rentang dari angka 0-49. Pada nomor soal tidak terdapat nomor soal 0 sehingga apabila terdapat angkat 0 dalam salah satu nomor soal yang dihasilkan maka akan diganti menjadi angka 50.