Metode linear kongruen

Linear Congruent Method (LCM) merupakan metode pembangkit bilangan acak yang banyak digunakan dalam program komputer. LCM memanfaatkan model linier untuk membangkitkan bilangan acak yang didefinisikan dengan :

Berkas:Rumus lcm umum.jpg

Dimana :

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

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 :

Jika terdapat soal ujian sebanyak 20 buah dan belum diacak, di mana proses pengacakan soal dapat dilakukan dengan menentukan nilai a = 1, c = 7, m = 20 dan x(0) = 2 adalah sebagai berikut, dengan rumus xi = ( a * xi + c ) mod m xi adalah bilangan acak ke n a dan c adalah konstanta LCM m adalah batas maksimum bilangan acak Agar nilai X(i) tidak menghasilkan 0, maka dalam simulasi pengacakan soal ini, setiap kali X(i) telah ditambahkan dengan 1, maka diperoleh :

1. x(1) = ( 1 (2) + 7 ) mod 20 = 10
2. x(2) = ( 1 (9) + 7 ) mod 20 = 17
3. x(3) = ( 1 (16) + 7 ) mod 20 = 4
4. x(4) = ( 1 (3) + 7 ) mod 20 = 11
5. x(5) = ( 1 (10) + 7 ) mod 20 = 18
6. x(6) = ( 1 (17) + 7 ) mod 20 = 5
7. x(7) = ( 1 (4) + 7 ) mod 20 = 12
8. x(8) = ( 1 (11) + 7 ) mod 20 = 19
9. x(9) = ( 1 (18) + 7 ) mod 20 = 6
10. x(10) = ( 1 (5) + 7 ) mod 20 = 13
11. x(11) = ( 1 (12) + 7 ) mod 20 = 20
12. x(12) = ( 1 (19) + 7 ) mod 20 = 7
13. x(13) = ( 1 (6) + 7 ) mod 20 = 14
14. x(14) = ( 1 (13) + 7 ) mod 20 = 1
15. x(15) = ( 1 (0) + 7 ) mod 20 = 8
16. x(16) = ( 1 (7) + 7 ) mod 20 = 15
17. x(17) = ( 1 (14) + 7 ) mod 20 = 2
18. x(18) = ( 1 (1) + 7 ) mod 20 = 9
19. x(19) = ( 1 (8) + 7 ) mod 20 = 16
20. x(20) = ( 1 (15) + 7) mod 20 = 3

Maka, bilangan acak yang dibangkitkan adalah : 10, 17, 4, 11, 18, 5, 12, 19, 6, 13, 20, 7, 14, 1, 8, 15, 2, 9, 16, 3 Dengan keterangan, x(1) merupakan soal nomor 1 sebelum diacak.