Lompat ke isi

Metode linear kongruen: Perbedaan antara revisi

Ensiklopedia Pengetahuan Universitas Islam Sultan Agung
Revisi selanjutnya →

Maintenance script (bicara | kontrib)

37.956 suntingan
Maintenance script (bicara | kontrib)
37.956 suntingan
Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29301643; atribusi sumber disertakan.
 
Maintenance script (bicara | kontrib)
37.956 suntingan
Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi
Baris 1: Baris 1:
'''Metode linear kongruen''' (Inggris: ''linear congruent method'', dapat disingkat dengan LCM) merupakan algoritma yang menghasilkan barisan [[bilangan acak]] semu lewat [[persamaan linear]] bagian-demi-bagian. Metode ini juga dikenal dengan '''metode kongruen linear,''' '''pembangkit kongruensial linear''' dan '''generator kongruensial linear''' (Inggris: ''linear congruential generator'', LCG). Metode ini termasuk algoritma yang tertua dan terkenal untuk membangkitkan bilangan acak semu. Konsep metode ini relatif mudah dipahami, mudah diimplementasikan, dan memiliki waktu eksekusi yang cepat, khususnya untuk [[Perangkat keras|perangkat keras komputer]] yang mendukung [[aritmetika modular]] dengan pemotongan pada bit-bit penyimpanan. LCM memanfaatkan [[Relasi pengulangan|relasi rekursif]] linear:
'''Metode linear kongruen''' (Inggris: ''linear congruent method'', dapat disingkat dengan LCM) merupakan algoritma yang menghasilkan barisan [[bilangan acak]] semu lewat [[persamaan linear]] bagian-demi-bagian. Metode ini juga dikenal dengan '''metode kongruen linear,''' '''pembangkit kongruensial linear''' dan '''generator kongruensial linear''' (Inggris: ''linear congruential generator'', LCG). Metode ini termasuk algoritma yang tertua dan terkenal untuk membangkitkan bilangan acak semu.<ref>[https://demonstrations.wolfram.com/LinearCongruentialGenerators/ Linear Congruential Generators - Wolfram Demonstrations Project]. ''demonstrations.wolfram.com''.</ref> Konsep metode ini relatif mudah dipahami, mudah diimplementasikan, dan memiliki waktu eksekusi yang cepat, khususnya untuk [[Perangkat keras|perangkat keras komputer]] yang mendukung [[aritmetika modular]] dengan pemotongan pada bit-bit penyimpanan. LCM memanfaatkan [[Relasi pengulangan|relasi rekursif]] linear:


<math>X_{n+1} = \left( a X_n + c \right)~~\bmod~~m</math>
<math>X_{n+1} = \left( a X_n + c \right)~~\bmod~~m</math>
Baris 9: Baris 9:
: <math> c</math> dengan <math> 0 \le c < m</math> sebagai "penambah"; dan
: <math> c</math> dengan <math> 0 \le c < m</math> sebagai "penambah"; dan
: <math> X_0</math> dengan <math> 0 \le X_0 < m</math> sebagai "benih", "nilai awal", atau "kondisi awal"
: <math> X_0</math> dengan <math> 0 \le X_0 < m</math> sebagai "benih", "nilai awal", atau "kondisi awal"
sebagai parameter khas untuk LCM. Jika <math> c=0</math>, metode ini umum disebut degan '''metode kongruensial multiplikatif''' (Inggris: ''multiplicative congruential generator'', MCG) atau [[pembangkit Lehmer]]. Jika <math> c\neq0</math>, metode ini disebut '''metode kongruensial campuran'''. Ketika <math> c\neq0</math>, relasi rekursif LCM sebenarnya adalah sebuah [[transformasi affine]], bukan [[Peta linear|transformasi linear]]. Namun penggunaan istilah linear yang salah sudah sangat umum pada bidang [[ilmu komputer]].
sebagai parameter khas untuk LCM. Jika <math> c=0</math>, metode ini umum disebut degan '''metode kongruensial multiplikatif''' (Inggris: ''multiplicative congruential generator'', MCG) atau [[pembangkit Lehmer]]. Jika <math> c\neq0</math>, metode ini disebut '''metode kongruensial campuran'''.<ref>Donald E. Knuth. [http://books.google.com/books?id=Zu-HAwAAQBAJ&pg=PT4 Art of Computer Programming, Volume 2: Seminumerical Algorithms]. Addison-Wesley Professional. 6 May 2014. hlm. 4–. ISBN 978-0-321-63576-1.</ref> Ketika <math> c\neq0</math>, relasi rekursif LCM sebenarnya adalah sebuah [[transformasi affine]], bukan [[Peta linear|transformasi linear]]. Namun penggunaan istilah linear yang salah sudah sangat umum pada bidang [[ilmu komputer]].<ref>Guy Steele. [http://arxiv.org/abs/2001.05304 Computationally easy, spectrally good multipliers for congruential pseudorandom number generators]. ''arXiv:2001.05304 [cs]''. 2021-01-21.</ref>


== Demonstrasi ==
== Demonstrasi ==
Baris 29: Baris 29:


== Sejarah ==
== Sejarah ==
Metode pembangkit Lehmer dipublikasikan pada tahun 1951, dan the Metode linear kongruen dipublikasikan pada tahun 1958 oleh W. E. Thomson and A. Rotenberg.
Metode pembangkit Lehmer dipublikasikan pada tahun 1951,<ref>Derrick H. Lehmer. ''Mathematical methods in large-scale computing units''. ''Proceedings of 2nd Symposium on Large-Scale Digital Calculating Machinery''. 1951. hlm. 141–146.</ref> dan the Metode linear kongruen dipublikasikan pada tahun 1958 oleh W. E. Thomson and A. Rotenberg.<ref>W. E. Thomson. [https://doi.org/10.1093/comjnl/1.2.83 A Modified Congruence Method of Generating Pseudo-random Numbers]. ''The Computer Journal''. 1958-02-01. Vol. 1 (2). hlm. 83–83. doi:10.1093/comjnl/1.2.83.</ref><ref>A. Rotenberg. [https://doi.org/10.1145/321008.321019 A New Pseudo-Random Number Generator]. ''Journal of the ACM''. 1960-01-01. Vol. 7 (1). hlm. 75–77. doi:10.1145/321008.321019.</ref>


== Panjang periode ==
== Panjang periode ==
Ciri dari LCM adalah akan terjadi pengulangan hasil setelah sekian kali pembangkitan. Dengan pemilihan parameter yang baik, periode pengulangan dapat diketahui dan dipilih agar lebih lama. Walaupun bukan satu-satunya kriteria, periode yang sangat singkat adalah kesalahan fatal bagi pembangkit bilangan acak semu.<ref>[http://mesran.blogspot.com/2013/06/metode-lcm-linear-congruent-method.html Metode LCM (Linear Congruent Method) - Mesran Punya Blog]. ''mesran.blogspot.com''.</ref><ref>Pierre L'Ecuyer. [https://www.iro.umontreal.ca/~lecuyer/myftp/papers/wsc17rng-history.pdf History of Uniform Random Number Generation]. 13 July 2017.</ref>


Ciri dari LCM adalah akan terjadi pengulangan hasil setelah sekian kali pembangkitan. Dengan pemilihan parameter yang baik, periode pengulangan dapat diketahui dan dipilih agar lebih lama. Walaupun bukan satu-satunya kriteria, periode yang sangat singkat adalah kesalahan fatal bagi pembangkit bilangan acak semu.
Walaupun LCM dapat menghasilkan [[bilangan acak semu]] yang lulus [[uji keacakan]], kualitas bilangan yang dihasilkan sangat sensitif terhadap pemilihan parameter <math>a</math> dan <math> m</math>.<ref>Guy Steele. [http://arxiv.org/abs/2001.05304 Computationally easy, spectrally good multipliers for congruential pseudorandom number generators]. ''arXiv:2001.05304 [cs]''. 2021-01-21.</ref><ref>[http://mesran.blogspot.com/2013/06/metode-lcm-linear-congruent-method.html Metode LCM (Linear Congruent Method) - Mesran Punya Blog]. ''mesran.blogspot.com''.</ref><ref>George Marsaglia. [https://www.pnas.org/content/61/1/25 Random Numbers Fall Mainly in the Planes]. ''Proceedings of the National Academy of Sciences''. 1968-09-01. Vol. 61 (1). hlm. 25–28. doi:10.1073/pnas.61.1.25.</ref><ref>S. K. Park. [https://doi.org/10.1145/63039.63042 Random number generators: good ones are hard to find]. ''Communications of the ACM''. 1988-10-01. Vol. 31 (10). hlm. 1192–1201. doi:10.1145/63039.63042.</ref><ref>W. Hörmann. [https://doi.org/10.1145/168173.168414 A portable random number generator well suited for the rejection method]. ''ACM Transactions on Mathematical Software''. 1993-12-01. Vol. 19 (4). hlm. 489–495. doi:10.1145/168173.168414.</ref><ref>Donald Knuth. ''Seminumerical Algorithms''. Addison-Wesley Professional. 1997. hlm. 10-26.</ref> Sebagai contoh, <math>a=1</math> dan <math>c=1</math> menghasilkan bilangan modulo-''m'' yang terurut, yang walau memiliki periode yang panjang, jelas tidak acak. Secara historis, pemilihan konstanta <math>a</math> yang buruk berujung pada implementasi LCM yang buruk. Contoh khusus kasus ini adalah [[RANDU]], yang digunakan secara luas pada awal 1970-an dan berujung pada banyak hasil yang tidak kredibel.<ref>William H. Press. ''Numerical Recipes in Fortran 77: The Art of Scientific Computing''. 1992. ISBN 978-0-521-43064-7.</ref>
 
Walaupun LCM dapat menghasilkan [[bilangan acak semu]] yang lulus [[uji keacakan]], kualitas bilangan yang dihasilkan sangat sensitif terhadap pemilihan parameter <math>a</math> dan <math> m</math>. Sebagai contoh, <math>a=1</math> dan <math>c=1</math> menghasilkan bilangan modulo-''m'' yang terurut, yang walau memiliki periode yang panjang, jelas tidak acak. Secara historis, pemilihan konstanta <math>a</math> yang buruk berujung pada implementasi LCM yang buruk. Contoh khusus kasus ini adalah [[RANDU]], yang digunakan secara luas pada awal 1970-an dan berujung pada banyak hasil yang tidak kredibel.


Terdapat tiga keluarga parameter yang umum digunakan:
Terdapat tiga keluarga parameter yang umum digunakan:
Baris 48: Baris 47:
Hal ini perlu diikuti oleh pengurangan nilai <math> m</math> jika hasilnya terlalu besar, namun banyaknya pengurangan terbatas oleh <math> ad/m</math>, yang dapat dibatasi dengan mudah menjadi 1 jika nilai <math> d</math> kecil.
Hal ini perlu diikuti oleh pengurangan nilai <math> m</math> jika hasilnya terlalu besar, namun banyaknya pengurangan terbatas oleh <math> ad/m</math>, yang dapat dibatasi dengan mudah menjadi 1 jika nilai <math> d</math> kecil.


Jika ''double-width product'' tidak tersedia, namun pengali dipilih secara saksama, '''metode Schrage''' dapat digunakan. Untuk melakukannya:
Jika ''double-width product'' tidak tersedia, namun pengali dipilih secara saksama, '''metode Schrage'''<ref>Raj Jain. [http://www.cse.wustl.edu/~jain/iucee/ftp/k_26rng.pdf#page=19 Computer Systems Performance Analysis Chapter 26: Random-Number Generation]. 9 July 2010. hlm. 19–20.</ref> dapat digunakan. Untuk melakukannya:


* Faktorkan <math> m=qa+r</math>, misal dengan <math> q = \lfloor m/a \rfloor</math> dan <math> r = m \ \ \text{mod} \ \ a</math>.
* Faktorkan <math> m=qa+r</math>, misal dengan <math> q = \lfloor m/a \rfloor</math> dan <math> r = m \ \ \text{mod} \ \ a</math>.
Baris 54: Baris 53:
* Karena <math> x \ \ \text{mod} \ \ q < q \leq m/a</math>, suku pertama tegas lebih kecil dari <math> am/a = m</math>. Jika <math> a</math> dipilih sehingga <math> r\leq d</math> (sehingga <math> r/q \leq 1</math>), maka suku kedua juga akan lebih kecil dari <math> m</math> karena <math> r\lfloor x/q \rfloor \leq rx/q = x (r/q) \leq x < m</math>.
* Karena <math> x \ \ \text{mod} \ \ q < q \leq m/a</math>, suku pertama tegas lebih kecil dari <math> am/a = m</math>. Jika <math> a</math> dipilih sehingga <math> r\leq d</math> (sehingga <math> r/q \leq 1</math>), maka suku kedua juga akan lebih kecil dari <math> m</math> karena <math> r\lfloor x/q \rfloor \leq rx/q = x (r/q) \leq x < m</math>.


Dengan cara ini, untuk menghitung kedua suku cukup digunakan ''single-width product'', dan selisih antara keduanya terletak di <math> [1-m, \,m-1]</math>, sehingga dapat disederhanakan menjadi <math> [0,\,m-1]</math> dengan satu kondisi penjumlahan.
Dengan cara ini, untuk menghitung kedua suku cukup digunakan ''single-width product'', dan selisih antara keduanya terletak di <math> [1-m, \,m-1]</math>, sehingga dapat disederhanakan menjadi <math> [0,\,m-1]</math> dengan satu kondisi penjumlahan.<ref>Paul Fenerty. [http://home.earthlink.net/~pfenerty/pi/schrages_method.html Schrage's Method]. 11 September 2006.</ref>


Kekurangan kedua dari metode ini adalah cukup canggung untuk mengonversi nilai <math> 1\leq x < m</math> ke distribusi bit acak yang uniform. Jika sebuah prima yang dekat dengan perpangkatan 2 digunakan, bilangan acak (yang tidak pernah muncul) dapat diabaikan.
Kekurangan kedua dari metode ini adalah cukup canggung untuk mengonversi nilai <math> 1\leq x < m</math> ke distribusi bit acak yang uniform. Jika sebuah prima yang dekat dengan perpangkatan 2 digunakan, bilangan acak (yang tidak pernah muncul) dapat diabaikan.
Baris 61: Baris 60:
Memilih <math> m</math> sebagai perpangkatan dari 2, umumnya <math> m = 2^{32}</math> atau <math> m = 2^{64}</math>, menghasilkan LCM yang efisien karena hal ini memungkinan operasi modulo dihitung dengan memotong representasi biner bilangan. Faktanya, bit paling signifikan umumnya tidak dihitung sama sekali. Namun, parameter ini memiliki kekurangan.
Memilih <math> m</math> sebagai perpangkatan dari 2, umumnya <math> m = 2^{32}</math> atau <math> m = 2^{64}</math>, menghasilkan LCM yang efisien karena hal ini memungkinan operasi modulo dihitung dengan memotong representasi biner bilangan. Faktanya, bit paling signifikan umumnya tidak dihitung sama sekali. Namun, parameter ini memiliki kekurangan.


Bentuk ini memiliki periode maksimum <math> m/4</math>, diperoleh ketika <math> a\equiv 3 \ \ \text{mod} \ \ 8</math> atau <math> a\equiv 5 \ \ \text{mod} \ \ 8</math>. Kondisi awal <math> X_0</math> perlu bilangan ganjil, dan nilai tiga bit terkecil dari <math> X</math> berseling antara dua nilai sehingga tidak berguna. Dapat ditunjukkan bahwa bentuk ini setara dengan pembangkit dengan modulus <math> m/4</math> dan <math> c\neq 0</math>.
Bentuk ini memiliki periode maksimum <math> m/4</math>, diperoleh ketika <math> a\equiv 3 \ \ \text{mod} \ \ 8</math> atau <math> a\equiv 5 \ \ \text{mod} \ \ 8</math>. Kondisi awal <math> X_0</math> perlu bilangan ganjil, dan nilai tiga bit terkecil dari <math> X</math> berseling antara dua nilai sehingga tidak berguna. Dapat ditunjukkan bahwa bentuk ini setara dengan pembangkit dengan modulus <math> m/4</math> dan <math> c\neq 0</math>.<ref>Donald Knuth. ''Seminumerical Algorithms''. Addison-Wesley Professional. 1997. hlm. 10-26.</ref>


Isu yang lebih serius karena menggunakan modulus perpangkatan 2 adalah bit-bit rendah memiliki periode yang lebih kecil dibandingkan bit-bit tinggi. Bit terendah dari <math> X</math> tidak pernah berubah (karena selalu bilangan ganjil), dan dua bit selanjutnya berseling antara dua nilai (jika <math> a\equiv 5 \ \ \text{mod} \ \ 8</math>, nilai bit 1 tidak pernah berubah dan nilai bit 2 berseling, sedangakan jika <math> a\equiv 3 \ \ \text{mod} \ \ 8</math> nilai bit 1 berseling dan nilai bit 2 selalu tetap).
Isu yang lebih serius karena menggunakan modulus perpangkatan 2 adalah bit-bit rendah memiliki periode yang lebih kecil dibandingkan bit-bit tinggi. Bit terendah dari <math> X</math> tidak pernah berubah (karena selalu bilangan ganjil), dan dua bit selanjutnya berseling antara dua nilai (jika <math> a\equiv 5 \ \ \text{mod} \ \ 8</math>, nilai bit 1 tidak pernah berubah dan nilai bit 2 berseling, sedangakan jika <math> a\equiv 3 \ \ \text{mod} \ \ 8</math> nilai bit 1 berseling dan nilai bit 2 selalu tetap).


=== ''c'' ≠ 0 ===
=== ''c'' ≠ 0 ===
Ketika <math> c\neq 0</math>, pemilihan parameter yang baik memungkinkan periode dapat sepanjang <math> m</math>, untuk semua kondisi awal. Hal ini terjadi, [[jika dan hanya jika]]:
Ketika <math> c\neq 0</math>, pemilihan parameter yang baik memungkinkan periode dapat sepanjang <math> m</math>, untuk semua kondisi awal. Hal ini terjadi, [[jika dan hanya jika]]:<ref>Donald Knuth. ''Seminumerical Algorithms''. Addison-Wesley Professional. 1997. hlm. 10-26.</ref>


# <math>m</math> dan <math>c</math> [[Koprima (bilangan)|koprima]] ,
# <math>m</math> dan <math>c</math> [[Koprima (bilangan)|koprima]] ,
Baris 72: Baris 71:
# <math>a - 1</math> dapat dibagi 4 jika <math>m</math> dapat dibagi 4.
# <math>a - 1</math> dapat dibagi 4 jika <math>m</math> dapat dibagi 4.


Tiga syarat ini dikenal sebagai Teorema Hull–Dobell.
Tiga syarat ini dikenal sebagai Teorema Hull–Dobell.<ref>T. E. Hull. [http://chagall.med.cornell.edu/BioinfoCourse/PDFs/Lecture4/random_number_generator.pdf Random Number Generators]. ''SIAM Review''. July 1962. Vol. 4 (3). hlm. 230–254. doi:10.1137/1004061.</ref><ref>Severance, Frank. [https://archive.org/details/systemmodelingsi0000seve System Modeling and Simulation]. John Wiley & Sons, Ltd. 2001. hlm. [https://archive.org/details/systemmodelingsi0000seve/page/86 86]. ISBN 978-0-471-49694-6.</ref>


Bentuk ini dapat digunakan untuk sebarang <math> m</math>, namun hanya bekerja dengan baik untuk <math> m</math> yang memiliki banyak faktor prima yang berulang, seperti perpangkatan angka 2. Jika <math> m</math> [[bilangan bebas-kuadrat]], hal ini mengakibatkan <math> a\equiv 1 \ \ \text{mod} \ \ m</math>, menjadikannya pembangkit bilangan acak yang sangat buruk. Pengali dengan periode maksimum hanya tersedia ketika <math> m</math> memiliki faktor prima yang berulang.
Bentuk ini dapat digunakan untuk sebarang <math> m</math>, namun hanya bekerja dengan baik untuk <math> m</math> yang memiliki banyak faktor prima yang berulang, seperti perpangkatan angka 2. Jika <math> m</math> [[bilangan bebas-kuadrat]], hal ini mengakibatkan <math> a\equiv 1 \ \ \text{mod} \ \ m</math>, menjadikannya pembangkit bilangan acak yang sangat buruk. Pengali dengan periode maksimum hanya tersedia ketika <math> m</math> memiliki faktor prima yang berulang.


Walau teorema Hull–Dobell memberikan periode yang maksimum, hal tersebut belum cukup untuk membuktikan pembangkit yang ''baik''. Sebagai contoh, <math> a-1</math> yang lebih sulit dibagi oleh faktor-faktor prima <math> m</math> lebih disukai. Karena itu, jika <math> m</math> adalah perpangkatan angka 2, maka <math> a-1</math> perlu dapat dibagi 4 tetapi tidak dapat dibagi 8, misal  <math> a\equiv 5 \ \ \text{mod} \ \ 8</math>.
Walau teorema Hull–Dobell memberikan periode yang maksimum, hal tersebut belum cukup untuk membuktikan pembangkit yang ''baik''. Sebagai contoh, <math> a-1</math> yang lebih sulit dibagi oleh faktor-faktor prima <math> m</math> lebih disukai. Karena itu, jika <math> m</math> adalah perpangkatan angka 2, maka <math> a-1</math> perlu dapat dibagi 4 tetapi tidak dapat dibagi 8, misal  <math> a\equiv 5 \ \ \text{mod} \ \ 8</math>.<ref>Donald Knuth. ''Seminumerical Algorithms''. Addison-Wesley Professional. 1997. hlm. 10-26.</ref>


Tentu, kebanyakan pengali menghasilkan barisan yang gagal untuk suatu uji keacakan, dan memilih pengali yang memenuhi semua kriteria uji cukup sulit. [[Uji spektral]] adalah salah satu uji keacakan terpenting.
Tentu, kebanyakan pengali menghasilkan barisan yang gagal untuk suatu uji keacakan, dan memilih pengali yang memenuhi semua kriteria uji cukup sulit. [[Uji spektral]] adalah salah satu uji keacakan terpenting.
Baris 84: Baris 83:
Pembangkit LCM sendiri tidak sensitif terhadap pemilihan <math> c</math>, selama nilainya koprima terhadap modulus (misal, jika <math> m</math> merupakan perpangkatan angka 2, maka <math> c</math> perlu bernilai ganjil), sehingga nilai <math> c=1</math> umum dipilih.
Pembangkit LCM sendiri tidak sensitif terhadap pemilihan <math> c</math>, selama nilainya koprima terhadap modulus (misal, jika <math> m</math> merupakan perpangkatan angka 2, maka <math> c</math> perlu bernilai ganjil), sehingga nilai <math> c=1</math> umum dipilih.


Barisan yang dihasilkan dari pemilihan <math> c</math> yang lain dapat ditulis sebagai fungsi sederhana dari barisan ketika <math> c=1</math>. Secara spesifik, jika <math> Y</math> adalah barisan yang didefinisikan dengan <math> Y_0 = 0</math> dan <math> Y_{n+1} = aY_n + 1 \ \ \text{mod} \ \ m</math>, maka barisan <math> X_{n+1} = aX_n + c \ \ \text{mod} \ \ m</math> dapat ditulis sebagai fungsi affine dari <math> Y</math>:
Barisan yang dihasilkan dari pemilihan <math> c</math> yang lain dapat ditulis sebagai fungsi sederhana dari barisan ketika <math> c=1</math>.<ref>Donald Knuth. ''Seminumerical Algorithms''. Addison-Wesley Professional. 1997. hlm. 10-26.</ref> Secara spesifik, jika <math> Y</math> adalah barisan yang didefinisikan dengan <math> Y_0 = 0</math> dan <math> Y_{n+1} = aY_n + 1 \ \ \text{mod} \ \ m</math>, maka barisan <math> X_{n+1} = aX_n + c \ \ \text{mod} \ \ m</math> dapat ditulis sebagai fungsi affine dari <math> Y</math>:


<math>X_n = (X_0(a-1)+c)Y_n + X_0 = (X_1 - X_0)Y_n + X_0 \pmod m.</math>
<math>X_n = (X_0(a-1)+c)Y_n + X_0 = (X_1 - X_0)Y_n + X_0 \pmod m.</math>
Baris 93: Baris 92:


== Parameter yang umum digunakan ==
== Parameter yang umum digunakan ==
Tabel berikut berisi daftar parameter LCM yang umum digunakan, termasuk fungsi <code>rand()</code> yang umum dimiliki oleh banyak [[kompilator]]. Tabel ini hanya menunjukkan parameter yang populer, bukan sebagai parameter implementasi yang baik. Tabel dengan parameter yang bagus tersedia.
Tabel berikut berisi daftar parameter LCM yang umum digunakan, termasuk fungsi <code>rand()</code> yang umum dimiliki oleh banyak [[kompilator]]. Tabel ini hanya menunjukkan parameter yang populer, bukan sebagai parameter implementasi yang baik. Tabel dengan parameter yang bagus tersedia.<ref>Guy Steele. [http://arxiv.org/abs/2001.05304 Computationally easy, spectrally good multipliers for congruential pseudorandom number generators]. ''arXiv:2001.05304 [cs]''. 2021-01-21.</ref><ref>Pierre L’Ecuyer. [https://www.ams.org/mcom/1999-68-225/S0025-5718-99-00996-5/ Tables of linear congruential generators of different sizes and good lattice structure]. ''Mathematics of Computation''. 1999. Vol. 68 (225). hlm. 249–260. doi:10.1090/S0025-5718-99-00996-5.</ref>
 
{| class="wikitable"
!Sumber
!modulus
<math>m</math>
!pengali
<math>a</math>
!penambah
<math>c</math>
!bit keluaran pada <code>rand()</code> atau <code>Random(L)</code>
|-
|''[[Numerical Recipes]]''
|2³²
|1664525
|1013904223
|
|-
|[[Borland]] C/C++
|2³²
|22695477
|1
|bit 30..16 pada <code>rand()</code>, 30..0 in <code>lrand()</code>
|-
|[[glibc]] (digunakan oleh [[GNU Compiler Collection|GCC]])<ref>[https://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/random_r.c;hb=glibc-2.26#l362 Implementation in glibc-2.26 release.] See the code after the test for "TYPE_0"; the GNU C library's ''rand()'' in stdlib.h uses a simple (single state) linear congruential generator only in case that the state is declared as 8 bytes. If the state is larger (an array), the generator becomes an additive feedback generator ([https://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/random_r.c;hb=glibc-2.26#l187 initialized using ''minstd_rand0''] ) and the period increases. See the [http://www.mscs.dal.ca/~selinger/random/ simplified code] that reproduces the random sequence from this library.</ref>
|2³¹
|1103515245
|12345
|bit 30..0
|-
|[[ANSI C]]: [[Watcom C compiler|Watcom]], [[Digital Mars]], [[CodeWarrior]], [[IBM VisualAge]] C/C++ <ref>K. Entacher. [http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.53.3686&rep=rep1&type=pdf A collection of selected pseudorandom number generators with linear structures]. 21 August 1997.</ref>[[C90 (C version)|C90]], [[C99]], [[C11 (C standard revision)|C11]]: Saran dalam ISO/IEC 9899,<ref>[http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf Last public Committee Draft from April 12, 2011]. hlm. 346f.</ref> [[C18 (C standard revision)|C18]]
|2³¹
|1103515245
|12345
|bit 30..16
|-
|[[Borland Delphi]], [[Virtual Pascal]]
|2³²
|134775813
|1
|bit 63..32 dari <code>seed × L</code>
|-
|[[Turbo Pascal]]
|2³²
|134775813 (8088405₁₆)
|1
|
|-
|[[Visual C++|Microsoft Visual/Quick C/C++]]
|2³²
|214013 (343FD₁₆)
|2531011 (269EC3₁₆)
|bit 30..16
|-
|[[Visual Basic|Microsoft Visual Basic]] (versi 6 dan sebelumnya)<ref>[http://support.microsoft.com/kb/231847 How Visual Basic Generates Pseudo-Random Numbers for the RND Function]. ''Microsoft Support''. Microsoft.</ref>
|
|1140671485 (43FD43FD₁₆)
|12820163 (C39EC3₁₆)
|
|-
|RtlUniform dari [[Native API]]<ref>In spite of documentation on [http://msdn.microsoft.com/en-us/library/bb432429(VS.85).aspx MSDN], RtlUniform uses LCG, and not Lehmer's algorithm, implementations before Windows Vista are flawed, because the result of multiplication is cut to 32 bits, before modulo is applied</ref>
|2³¹ − 1
|2147483629 (7FFFFFED₁₆)
|2147483587 (7FFFFFC3₁₆)
|
|-
|[[CarbonLib|Apple CarbonLib]], <code>minstd_rand0</code> milik [[C++11]]<ref>[http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=50372 ISO/IEC 14882:2011]. ISO. 2 September 2011.</ref>
|2³¹ − 1
|16807
|0
|lihat [[MINSTD]]
|-
|[[C++11]]'s <code>minstd_rand</code><ref>[http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=50372 ISO/IEC 14882:2011]. ISO. 2 September 2011.</ref>
|2³¹ − 1
|48271
|0
|lihat [[MINSTD]]
|-
|[[MMIX]] oleh [[Donald Knuth]]
|2⁶⁴
|6364136223846793005
|1442695040888963407
|
|-
|[[Newlib]], [[Musl]]
|2⁶⁴
|6364136223846793005
|1
|bit 63..32
|-
|[[OpenVMS|VMS]]'s '''MTH$RANDOM''',<ref>[https://www.gnu.org/software/gsl/manual/html_node/Other-random-number-generators.html GNU Scientific Library: Other random number generators]</ref> versi lawas dari [[glibc]]
|2³²
|69069 (10DCD₁₆)
|1
|
|-
|[[Java (programming language)|Java]]'s java.utilRandom, [[POSIX]] [ln]rand48, [[glibc]] [ln]rand48[_r]
|2⁴⁸
|25214903917 (5DEECE66D₁₆)
|11
|bit 47..16
|-
|<code>random0</code><ref>Stephen J. Chapman. "Example 6.4 – Random Number Generator". [https://books.google.com/books?id=e80HBgAAQBAJ "MATLAB Programming for Engineers"]. 2015. pp. 253–256.</ref><ref>Stephen J. Chapman. "Example 6.4 – Random Number Generator". [https://books.google.com/books?id=of8KAAAAQBAJ "MATLAB Programming with Applications for Engineers"]. 2012. pp. 292–295.</ref><ref>S. J. Chapman. [http://www.udel.edu/CIS/106/pconrad/MPE3/code/chap5/random0.m random0]. 2004.</ref><ref>Stephen J. Chapman. [https://books.google.com/books?id=QoVGAAAAYAAJ "Introduction to Fortran 90/95"]. 1998. pp. 322–324.</ref><ref>Wu-ting Tsai. [http://homepage.ntu.edu.tw/~wttsai/fortran/ppt/11.Module.pdf "'Module': A Major Feature of the Modern Fortran"] . pp. 6–7.</ref>
|134456 = 2³7⁵
|8121
|28411
|<math>\frac{ X_n }{ 134456 }</math>
|-
|[[POSIX]]<ref>[http://pubs.opengroup.org/onlinepubs/9699919799/ The Open Group Base Specifications Issue 7] IEEE Std 1003.1, 2013 Edition</ref> [jm]rand48, [[glibc]] [mj]rand48[_r]
|2⁴⁸
|25214903917 (5DEECE66D₁₆)
|11
|bit 47..15
|-
|[[POSIX]] [de]rand48, [[glibc]] [de]rand48[_r]
|2⁴⁸
|25214903917 (5DEECE66D₁₆)
|11
|bit 47..0
|-
|[[cc65]]<ref>Sidney Cadot. [https://github.com/cc65/cc65/blob/master/libsrc/common/rand.s rand.s]. ''cc65''.</ref>
|2²³
|65793 (10101₁₆)
|4282663 (415927₁₆)
|bit 22..8
|-
|[[cc65]]
|2³²
|16843009 (1010101₁₆)
|826366247 (31415927₁₆)
|bit 31..16
|- style="border-top:2px solid;"
|''Pernah umum digunakan: [[RANDU]]'' <ref>William H. Press. ''Numerical Recipes in Fortran 77: The Art of Scientific Computing''. 1992. ISBN 978-0-521-43064-7.</ref>
|2³¹
|65539
|0
|
|}
Seperti terlihat di atas, LCM tidak selalu menggunakan semua bit bilangan yang dihasilkan. Sebagai contoh, implementasi [[Java (programming language)|Java]] beroperasi dengan 48-bit pada setiap iterasi, tetapi hanya menghasilkan nilai dari 32 bit pertama. Hal ini disebabkan karena bit dengan order yang lebih tinggi memiliki periode yang lebih lama dibandingkan dengan bit dengan order rendah. LCM yang menggunakan teknik pemotongan bit ini menghasilkan nilai yang secara statistik lebih baik jika dibandingkan dengan yang tidak. Hal ini terlihat pada implementasi kode yang menggunakan [[Operasi modulus|operasi modulo]] untuk memperkecil jangkauan hasil; tanpa pemotongan, modulo 2 dari bilangan acak yang dihasilkan akan menghasilkan hasil 0 dan 1 yang periodik.
Seperti terlihat di atas, LCM tidak selalu menggunakan semua bit bilangan yang dihasilkan. Sebagai contoh, implementasi [[Java (programming language)|Java]] beroperasi dengan 48-bit pada setiap iterasi, tetapi hanya menghasilkan nilai dari 32 bit pertama. Hal ini disebabkan karena bit dengan order yang lebih tinggi memiliki periode yang lebih lama dibandingkan dengan bit dengan order rendah. LCM yang menggunakan teknik pemotongan bit ini menghasilkan nilai yang secara statistik lebih baik jika dibandingkan dengan yang tidak. Hal ini terlihat pada implementasi kode yang menggunakan [[Operasi modulus|operasi modulo]] untuk memperkecil jangkauan hasil; tanpa pemotongan, modulo 2 dari bilangan acak yang dihasilkan akan menghasilkan hasil 0 dan 1 yang periodik.


== Kelebihan dan kekurangan ==
== Kelebihan dan kekurangan ==
Metode LCM cepat dan hanya memerlukan memori yang kecil (satu bilangan modulo-m, umumnya 32 atau 64 bit) untuk penyimpanan sementara bilangan yang dihasilkan. Hal ini yang membuat LCM berguna untuk menyimulasikan beberapa keadaan independen. LCM tidak ditujukan, dan jangan digunakan, untuk aplikasi dalam bidang [[kriptografi]]; pembangkit bilangan acak semu (Inggris: ''pseudo random number generator'', PRNG) yang aman secara kriptografi diperlukan untuk hal tersebut.
Metode LCM cepat dan hanya memerlukan memori yang kecil (satu bilangan modulo-m, umumnya 32 atau 64 bit) untuk penyimpanan sementara bilangan yang dihasilkan. Hal ini yang membuat LCM berguna untuk menyimulasikan beberapa keadaan independen. LCM tidak ditujukan, dan jangan digunakan, untuk aplikasi dalam bidang [[kriptografi]]; pembangkit bilangan acak semu (Inggris: ''pseudo random number generator'', PRNG) yang aman secara kriptografi diperlukan untuk hal tersebut.


Walau LCM memiliki beberapa kelemahan spesifik, kebanyakan kelemahannya diakibatkan dari pemilihan parameter yang terlalu kecil. LCM dengan parameter yang cukup besar dapat lulus dari tes statistik yang ketat; LCM modulo-2 yang menghasilkan 32 bit bilangan lulus SmallCrush oleh [[TestU01]], dan LCM 96-bit lulus dari tes BigCrush yang jauh lebih sulit.
Walau LCM memiliki beberapa kelemahan spesifik, kebanyakan kelemahannya diakibatkan dari pemilihan parameter yang terlalu kecil. LCM dengan parameter yang cukup besar dapat lulus dari tes statistik yang ketat; LCM modulo-2 yang menghasilkan 32 bit bilangan lulus SmallCrush oleh [[TestU01]], dan LCM 96-bit lulus dari tes BigCrush yang jauh lebih sulit.<ref>Melissa E. O'Neill. [http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf#page=9 PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation]. Harvey Mudd College. 5 September 2014. hlm. 6–7.</ref>


Untuk contoh yang spesifik, pembangkit bilangan acak semu (PNRG) dengan keluaran 32 bit, memiliki [[Peluang (matematika)|ekspektasi]] (lewat [[teorema Birthday]]) mulai mengulangi keluaran yang pernah dihasilkan setelah melakukan <math>\sqrt m \approx 2^{16}</math> keluaran. ''Setiap'' PNRG dengan keluaran tanpa pemotongan bit, tidak akan berulang sampai periode maksimumnya tercapai; sebuah cacat statistik yang mudah dideteksi. Dengan alasan serupa, PNRG perlu memiliki periode yang lebih panjang daripada akar dari banyak keluaran yang diinginkan. Mempertimbangkan kecepatan komputer modern, periode sebesar <math>2^{64}</math> dibutuhkan untuk aplikasi kurang penting (secara kriptografi), dan periode yang lebih besar untuk aplikasi yang penting.
Untuk contoh yang spesifik, pembangkit bilangan acak semu (PNRG) dengan keluaran 32 bit, memiliki [[Peluang (matematika)|ekspektasi]] (lewat [[teorema Birthday]]) mulai mengulangi keluaran yang pernah dihasilkan setelah melakukan <math>\sqrt m \approx 2^{16}</math> keluaran. ''Setiap'' PNRG dengan keluaran tanpa pemotongan bit, tidak akan berulang sampai periode maksimumnya tercapai; sebuah cacat statistik yang mudah dideteksi. Dengan alasan serupa, PNRG perlu memiliki periode yang lebih panjang daripada akar dari banyak keluaran yang diinginkan. Mempertimbangkan kecepatan komputer modern, periode sebesar <math>2^{64}</math> dibutuhkan untuk aplikasi kurang penting (secara kriptografi), dan periode yang lebih besar untuk aplikasi yang penting.


Satu kecacatan spesifik LCM adalah, jika digunakan untuk memilih titik pada ruang dimensi <math>n</math>, titik tersebut akan terletak (maksimal) pada <math>\sqrt[n]{n!m}</math> ''hyperplane'', berdasarkan [[teorema Marsaglia]] (yang dikembangkan oleh [[George Marsaglia]]). Hal ini disebabkan oleh ''serial correlation'' antar nilai yang berurutan pada barisan <math>X_n</math>. Pengali yang dipilih dengan lalai umumnya menghasilkan sedikit bidang, dengan jarak antar bidang yang besar, yang dapat menyebabkan masalah. [[Uji spektral]], yang merupakan tes kualitas LCM yang sederhana, mengukur jarak antar bidang dan memungkinkan untuk memilih nilai pengali yang baik.
Satu kecacatan spesifik LCM adalah, jika digunakan untuk memilih titik pada ruang dimensi <math>n</math>, titik tersebut akan terletak (maksimal) pada <math>\sqrt[n]{n!m}</math> ''hyperplane'', berdasarkan [[teorema Marsaglia]] (yang dikembangkan oleh [[George Marsaglia]]).<ref>George Marsaglia. [https://www.pnas.org/content/61/1/25 Random Numbers Fall Mainly in the Planes]. ''Proceedings of the National Academy of Sciences''. 1968-09-01. Vol. 61 (1). hlm. 25–28. doi:10.1073/pnas.61.1.25.</ref> Hal ini disebabkan oleh ''serial correlation'' antar nilai yang berurutan pada barisan <math>X_n</math>. Pengali yang dipilih dengan lalai umumnya menghasilkan sedikit bidang, dengan jarak antar bidang yang besar, yang dapat menyebabkan masalah. [[Uji spektral]], yang merupakan tes kualitas LCM yang sederhana, mengukur jarak antar bidang dan memungkinkan untuk memilih nilai pengali yang baik.


Jarak antar bidang bergantung pada modulus dan pengali LCM. Modulus yang cukup besar dapat memperkecil jarak ini sehingga kurang dari bilangan ''double precision''. Pemilihan pengali menjadi kurang penting ketika modulus yang dipakai besar. Namun masih penting untuk menghitung indeks spektral dan memastikan tidak memilh pengali yang buruk, walau secara statistik hampir mustahil mendapatkan pengali yang buruk ketika nilai modulus lebih besar dari <math>2^{64}</math>.
Jarak antar bidang bergantung pada modulus dan pengali LCM. Modulus yang cukup besar dapat memperkecil jarak ini sehingga kurang dari bilangan ''double precision''. Pemilihan pengali menjadi kurang penting ketika modulus yang dipakai besar. Namun masih penting untuk menghitung indeks spektral dan memastikan tidak memilh pengali yang buruk, walau secara statistik hampir mustahil mendapatkan pengali yang buruk ketika nilai modulus lebih besar dari <math>2^{64}</math>.
Baris 116: Baris 249:


== Implementasi ==
== Implementasi ==
Berikut salah satu implementasi LCM dalam bahasa pemrograman [[Python (programming language)|Python]]:Seperti semua pembangkit bilangan acak semu lainnya, LCM perlu menyimpan dan mengubah keadaan bilangan acak yang dihasilkan. Komputer dengan banyak [[Utas (komputer)|utas]] yang mengakses keadaan ini dapat menyebabkan ''race condition''. Implementasi dengan setiap utas memiliki inisialisasi nilai awal yang unik diperlukan agar tidak ada utas dengan barisan bilangan acak yang sama.
Berikut salah satu implementasi LCM dalam bahasa pemrograman [[Python (programming language)|Python]]:<syntaxhighlight lang="python">
def lcg(modulus, a, c, seed):
    """Linear congruential generator."""
    while True:
        seed = (a * seed + c) % modulus
        yield seed
</syntaxhighlight>Seperti semua pembangkit bilangan acak semu lainnya, LCM perlu menyimpan dan mengubah keadaan bilangan acak yang dihasilkan. Komputer dengan banyak [[Utas (komputer)|utas]] yang mengakses keadaan ini dapat menyebabkan ''race condition''. Implementasi dengan setiap utas memiliki inisialisasi nilai awal yang unik diperlukan agar tidak ada utas dengan barisan bilangan acak yang sama.


== Turunan LCM ==
== Turunan LCM ==
Baris 124: Baris 263:


== Referensi ==
== Referensi ==
 
<references />
 


== Sumber dan atribusi ==
== Sumber dan atribusi ==


Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Metode+linear+kongruen&oldid=29301643 Wikipedia bahasa Indonesia], revisi 29301643 (2026-06-01T06:18:00Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.
Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Metode+linear+kongruen&oldid=29301643 Wikipedia bahasa Indonesia], revisi 29301643 (2026-06-01T06:18:00Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.
<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Revisi per 25 Agustus 2026 03.57

Metode linear kongruen (Inggris: linear congruent method, dapat disingkat dengan LCM) merupakan algoritma yang menghasilkan barisan bilangan acak semu lewat persamaan linear bagian-demi-bagian. Metode ini juga dikenal dengan metode kongruen linear, pembangkit kongruensial linear dan generator kongruensial linear (Inggris: linear congruential generator, LCG). Metode ini termasuk algoritma yang tertua dan terkenal untuk membangkitkan bilangan acak semu.[1] Konsep metode ini relatif mudah dipahami, mudah diimplementasikan, dan memiliki waktu eksekusi yang cepat, khususnya untuk perangkat keras komputer yang mendukung aritmetika modular dengan pemotongan pada bit-bit penyimpanan. LCM memanfaatkan relasi rekursif linear:

Xn+1=(aXn+c)modm

dengan X sebagai barisan bilangan acak semu, dan konstanta bilangan bulat

m positif sebagai "modulus"
a dengan 0<a<m sebagai "pengali"
c dengan 0≤c<m sebagai "penambah"; dan
X0 dengan 0≤X0<m sebagai "benih", "nilai awal", atau "kondisi awal"

sebagai parameter khas untuk LCM. Jika c=0, metode ini umum disebut degan metode kongruensial multiplikatif (Inggris: multiplicative congruential generator, MCG) atau pembangkit Lehmer. Jika c≠0, metode ini disebut metode kongruensial campuran.[2] Ketika c≠0, relasi rekursif LCM sebenarnya adalah sebuah transformasi affine, bukan transformasi linear. Namun penggunaan istilah linear yang salah sudah sangat umum pada bidang ilmu komputer.[3]

Demonstrasi

Terdapat 50 soal pada sebuah sistem database ujian. Untuk setiap ujian, 5 soal akan dipilih secara acak dari database. Untuk mengusahakan tidak terjadi repetisi soal-soal yang telah dikerjakan, sistem memilih soal "baru" dengan menggunakan LCM; dengan konstanta a=11, c=7, m=50, dan X0=1. Berikut adalah lima bilangan acak (semu) pertama yang dihasilkan oleh LCM tersebut

  • X1=(11(1)+7)  mod  50=18
  • X2=(11(18)+7)  mod  50=5
  • X3=(11(5)+7)  mod  50=12
  • X4=(11(12)+7)  mod  50=39
  • X5=(11(39)+7)  mod  50=36

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

Pemilihan nilai konstanta pada a, c, dan m pada LCM ini sesuai untuk menghindari perulangan soal pada saat melakukan ujian. Saat melakukan ujian pertama kali, nilai X1 dan peserta akan mendapatkan soal bernomor {18, 5, 12, 39, 36}. Namun ujian yang kedua memiliki nilai awal X6 dan peserta akan mendapatkan soal bernomor {3, 40, 47, 24, 21}.

Sejarah

Metode pembangkit Lehmer dipublikasikan pada tahun 1951,[4] dan the Metode linear kongruen dipublikasikan pada tahun 1958 oleh W. E. Thomson and A. Rotenberg.[5][6]

Panjang periode

Ciri dari LCM adalah akan terjadi pengulangan hasil setelah sekian kali pembangkitan. Dengan pemilihan parameter yang baik, periode pengulangan dapat diketahui dan dipilih agar lebih lama. Walaupun bukan satu-satunya kriteria, periode yang sangat singkat adalah kesalahan fatal bagi pembangkit bilangan acak semu.[7][8]

Walaupun LCM dapat menghasilkan bilangan acak semu yang lulus uji keacakan, kualitas bilangan yang dihasilkan sangat sensitif terhadap pemilihan parameter a dan m.[9][10][11][12][13][14] Sebagai contoh, a=1 dan c=1 menghasilkan bilangan modulo-m yang terurut, yang walau memiliki periode yang panjang, jelas tidak acak. Secara historis, pemilihan konstanta a yang buruk berujung pada implementasi LCM yang buruk. Contoh khusus kasus ini adalah RANDU, yang digunakan secara luas pada awal 1970-an dan berujung pada banyak hasil yang tidak kredibel.[15]

Terdapat tiga keluarga parameter yang umum digunakan:

m bilangan prima, c = 0

Ini adalah konstruksi dasar dari pembangkit bilangan acak Lehmer. Periode LCM adalah m−1 jika pengali a dipilih sebagai elemen primitif dari modulo m. Kondisi awal perlu dipilih antara 1 dan m−1.

Kelemahan dari menggunakan modulus bilangan prima adalah operasi modulo memerlukan double-width productdan langkah operasi modulo yang eksplisit. Umumnya prima yang dekat dengan perpangkatan angka 2 ( prima Mersenne yang berbentuk 231−1 dan 261−1 populer), sehingga operasi modulo m=2e−d dapat dihitung sebagai

(ax  mod  2e)+d⌊ax2e⌋

Hal ini perlu diikuti oleh pengurangan nilai m jika hasilnya terlalu besar, namun banyaknya pengurangan terbatas oleh ad/m, yang dapat dibatasi dengan mudah menjadi 1 jika nilai d kecil.

Jika double-width product tidak tersedia, namun pengali dipilih secara saksama, metode Schrage[16] dapat digunakan. Untuk melakukannya:

  • Faktorkan m=qa+r, misal dengan q=⌊m/a⌋ dan r=m  mod  a.
  • Hitung nilai ax  mod  m=a(x  mod  q)−r⌊x/q⌋
  • Karena x  mod  q<q≤m/a, suku pertama tegas lebih kecil dari am/a=m. Jika a dipilih sehingga r≤d (sehingga r/q≤1), maka suku kedua juga akan lebih kecil dari m karena r⌊x/q⌋≤rx/q=x(r/q)≤x<m.

Dengan cara ini, untuk menghitung kedua suku cukup digunakan single-width product, dan selisih antara keduanya terletak di [1−m,m−1], sehingga dapat disederhanakan menjadi [0,m−1] dengan satu kondisi penjumlahan.[17]

Kekurangan kedua dari metode ini adalah cukup canggung untuk mengonversi nilai 1≤x<m ke distribusi bit acak yang uniform. Jika sebuah prima yang dekat dengan perpangkatan 2 digunakan, bilangan acak (yang tidak pernah muncul) dapat diabaikan.

m perpangkatan 2, c = 0

Memilih m sebagai perpangkatan dari 2, umumnya m=232 atau m=264, menghasilkan LCM yang efisien karena hal ini memungkinan operasi modulo dihitung dengan memotong representasi biner bilangan. Faktanya, bit paling signifikan umumnya tidak dihitung sama sekali. Namun, parameter ini memiliki kekurangan.

Bentuk ini memiliki periode maksimum m/4, diperoleh ketika a≡3  mod  8 atau a≡5  mod  8. Kondisi awal X0 perlu bilangan ganjil, dan nilai tiga bit terkecil dari X berseling antara dua nilai sehingga tidak berguna. Dapat ditunjukkan bahwa bentuk ini setara dengan pembangkit dengan modulus m/4 dan c≠0.[18]

Isu yang lebih serius karena menggunakan modulus perpangkatan 2 adalah bit-bit rendah memiliki periode yang lebih kecil dibandingkan bit-bit tinggi. Bit terendah dari X tidak pernah berubah (karena selalu bilangan ganjil), dan dua bit selanjutnya berseling antara dua nilai (jika a≡5  mod  8, nilai bit 1 tidak pernah berubah dan nilai bit 2 berseling, sedangakan jika a≡3  mod  8 nilai bit 1 berseling dan nilai bit 2 selalu tetap).

c ≠ 0

Ketika c≠0, pemilihan parameter yang baik memungkinkan periode dapat sepanjang m, untuk semua kondisi awal. Hal ini terjadi, jika dan hanya jika:[19]

  1. m dan c koprima ,
  2. a−1 dapat dibagi semua faktor prima dari m,
  3. a−1 dapat dibagi 4 jika m dapat dibagi 4.

Tiga syarat ini dikenal sebagai Teorema Hull–Dobell.[20][21]

Bentuk ini dapat digunakan untuk sebarang m, namun hanya bekerja dengan baik untuk m yang memiliki banyak faktor prima yang berulang, seperti perpangkatan angka 2. Jika m bilangan bebas-kuadrat, hal ini mengakibatkan a≡1  mod  m, menjadikannya pembangkit bilangan acak yang sangat buruk. Pengali dengan periode maksimum hanya tersedia ketika m memiliki faktor prima yang berulang.

Walau teorema Hull–Dobell memberikan periode yang maksimum, hal tersebut belum cukup untuk membuktikan pembangkit yang baik. Sebagai contoh, a−1 yang lebih sulit dibagi oleh faktor-faktor prima m lebih disukai. Karena itu, jika m adalah perpangkatan angka 2, maka a−1 perlu dapat dibagi 4 tetapi tidak dapat dibagi 8, misal a≡5  mod  8.[22]

Tentu, kebanyakan pengali menghasilkan barisan yang gagal untuk suatu uji keacakan, dan memilih pengali yang memenuhi semua kriteria uji cukup sulit. Uji spektral adalah salah satu uji keacakan terpenting.

Perhatikan bahwa modulus berupa perpangkatan angka 2 memiliki permasalahan yang sama dengan kasus c=0: k bit terendah menghasilkan pembangkit dengan modulus 2k dan karenanya memiliki periode 2k; hanya bit paling signifikan yang memiliki periode penuh. Jika sebuah bilangan acak semu kurang dari r yang diperlukan, menghitung ⌊rX/m⌋ memberikan hasil yang lebih baik ketimbang X  mod  r. Sayangnya pada kebanyakan bahasa pemrograman, bentuk terakhir lebih banyak digunakan karena lebih mudah ditulis

Pembangkit LCM sendiri tidak sensitif terhadap pemilihan c, selama nilainya koprima terhadap modulus (misal, jika m merupakan perpangkatan angka 2, maka c perlu bernilai ganjil), sehingga nilai c=1 umum dipilih.

Barisan yang dihasilkan dari pemilihan c yang lain dapat ditulis sebagai fungsi sederhana dari barisan ketika c=1.[23] Secara spesifik, jika Y adalah barisan yang didefinisikan dengan Y0=0 dan Yn+1=aYn+1  mod  m, maka barisan Xn+1=aXn+c  mod  m dapat ditulis sebagai fungsi affine dari Y:

Xn=(X0(a−1)+c)Yn+X0=(X1−X0)Yn+X0(modm).

Secara umum, dua barisan X dan Z yang memiliki pengali dan modulus yang sama memiliki hubungan:

Xn−X0X1−X0=Yn=an−1a−1=Zn−Z0Z1−Z0(modm).

Parameter yang umum digunakan

Tabel berikut berisi daftar parameter LCM yang umum digunakan, termasuk fungsi rand() yang umum dimiliki oleh banyak kompilator. Tabel ini hanya menunjukkan parameter yang populer, bukan sebagai parameter implementasi yang baik. Tabel dengan parameter yang bagus tersedia.[24][25]

Sumber modulus

m

pengali

a

penambah

c

bit keluaran pada rand() atau Random(L)
Numerical Recipes 2³² 1664525 1013904223
Borland C/C++ 2³² 22695477 1 bit 30..16 pada rand(), 30..0 in lrand()
glibc (digunakan oleh GCC)[26] 2³¹ 1103515245 12345 bit 30..0
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++ [27]C90, C99, C11: Saran dalam ISO/IEC 9899,[28] C18 2³¹ 1103515245 12345 bit 30..16
Borland Delphi, Virtual Pascal 2³² 134775813 1 bit 63..32 dari seed × L
Turbo Pascal 2³² 134775813 (8088405₁₆) 1
Microsoft Visual/Quick C/C++ 2³² 214013 (343FD₁₆) 2531011 (269EC3₁₆) bit 30..16
Microsoft Visual Basic (versi 6 dan sebelumnya)[29] 1140671485 (43FD43FD₁₆) 12820163 (C39EC3₁₆)
RtlUniform dari Native API[30] 2³¹ − 1 2147483629 (7FFFFFED₁₆) 2147483587 (7FFFFFC3₁₆)
Apple CarbonLib, minstd_rand0 milik C++11[31] 2³¹ − 1 16807 0 lihat MINSTD
C++11's minstd_rand[32] 2³¹ − 1 48271 0 lihat MINSTD
MMIX oleh Donald Knuth 2⁶⁴ 6364136223846793005 1442695040888963407
Newlib, Musl 2⁶⁴ 6364136223846793005 1 bit 63..32
VMS's MTH$RANDOM,[33] versi lawas dari glibc 2³² 69069 (10DCD₁₆) 1
Java's java.utilRandom, POSIX [ln]rand48, glibc [ln]rand48[_r] 2⁴⁸ 25214903917 (5DEECE66D₁₆) 11 bit 47..16
random0[34][35][36][37][38] 134456 = 2³7⁵ 8121 28411 Xn134456
POSIX[39] [jm]rand48, glibc [mj]rand48[_r] 2⁴⁸ 25214903917 (5DEECE66D₁₆) 11 bit 47..15
POSIX [de]rand48, glibc [de]rand48[_r] 2⁴⁸ 25214903917 (5DEECE66D₁₆) 11 bit 47..0
cc65[40] 2²³ 65793 (10101₁₆) 4282663 (415927₁₆) bit 22..8
cc65 2³² 16843009 (1010101₁₆) 826366247 (31415927₁₆) bit 31..16
Pernah umum digunakan: RANDU [41] 2³¹ 65539 0

Seperti terlihat di atas, LCM tidak selalu menggunakan semua bit bilangan yang dihasilkan. Sebagai contoh, implementasi Java beroperasi dengan 48-bit pada setiap iterasi, tetapi hanya menghasilkan nilai dari 32 bit pertama. Hal ini disebabkan karena bit dengan order yang lebih tinggi memiliki periode yang lebih lama dibandingkan dengan bit dengan order rendah. LCM yang menggunakan teknik pemotongan bit ini menghasilkan nilai yang secara statistik lebih baik jika dibandingkan dengan yang tidak. Hal ini terlihat pada implementasi kode yang menggunakan operasi modulo untuk memperkecil jangkauan hasil; tanpa pemotongan, modulo 2 dari bilangan acak yang dihasilkan akan menghasilkan hasil 0 dan 1 yang periodik.

Kelebihan dan kekurangan

Metode LCM cepat dan hanya memerlukan memori yang kecil (satu bilangan modulo-m, umumnya 32 atau 64 bit) untuk penyimpanan sementara bilangan yang dihasilkan. Hal ini yang membuat LCM berguna untuk menyimulasikan beberapa keadaan independen. LCM tidak ditujukan, dan jangan digunakan, untuk aplikasi dalam bidang kriptografi; pembangkit bilangan acak semu (Inggris: pseudo random number generator, PRNG) yang aman secara kriptografi diperlukan untuk hal tersebut.

Walau LCM memiliki beberapa kelemahan spesifik, kebanyakan kelemahannya diakibatkan dari pemilihan parameter yang terlalu kecil. LCM dengan parameter yang cukup besar dapat lulus dari tes statistik yang ketat; LCM modulo-2 yang menghasilkan 32 bit bilangan lulus SmallCrush oleh TestU01, dan LCM 96-bit lulus dari tes BigCrush yang jauh lebih sulit.[42]

Untuk contoh yang spesifik, pembangkit bilangan acak semu (PNRG) dengan keluaran 32 bit, memiliki ekspektasi (lewat teorema Birthday) mulai mengulangi keluaran yang pernah dihasilkan setelah melakukan m≈216 keluaran. Setiap PNRG dengan keluaran tanpa pemotongan bit, tidak akan berulang sampai periode maksimumnya tercapai; sebuah cacat statistik yang mudah dideteksi. Dengan alasan serupa, PNRG perlu memiliki periode yang lebih panjang daripada akar dari banyak keluaran yang diinginkan. Mempertimbangkan kecepatan komputer modern, periode sebesar 264 dibutuhkan untuk aplikasi kurang penting (secara kriptografi), dan periode yang lebih besar untuk aplikasi yang penting.

Satu kecacatan spesifik LCM adalah, jika digunakan untuk memilih titik pada ruang dimensi n, titik tersebut akan terletak (maksimal) pada n!mn hyperplane, berdasarkan teorema Marsaglia (yang dikembangkan oleh George Marsaglia).[43] Hal ini disebabkan oleh serial correlation antar nilai yang berurutan pada barisan Xn. Pengali yang dipilih dengan lalai umumnya menghasilkan sedikit bidang, dengan jarak antar bidang yang besar, yang dapat menyebabkan masalah. Uji spektral, yang merupakan tes kualitas LCM yang sederhana, mengukur jarak antar bidang dan memungkinkan untuk memilih nilai pengali yang baik.

Jarak antar bidang bergantung pada modulus dan pengali LCM. Modulus yang cukup besar dapat memperkecil jarak ini sehingga kurang dari bilangan double precision. Pemilihan pengali menjadi kurang penting ketika modulus yang dipakai besar. Namun masih penting untuk menghitung indeks spektral dan memastikan tidak memilh pengali yang buruk, walau secara statistik hampir mustahil mendapatkan pengali yang buruk ketika nilai modulus lebih besar dari 264.

Salah satu kecacatan lain yang spesifik pada LCM adalah periode bit-rendah yang pendek ketika m dipilih sebagai bilangan perpangkatan 2. Hal ini dapat dihindari dengan menggunakan modulus yang lebih besar daripada banyak keluaran yang diinginkan, dan menggunakan bit-bit tinggi dari hasil yang dikeluarkan.

Walaupun demikian, LCM dapat menjadi pilihan yang bagus untuk beberapa aplikasi. Sebagai contoh, pada sistem tertanam, banyak memori yang tersedia sangat terbatas. Pada lingkungan yang serupa, seperti pada konsol permainan, mengambil beberapa bit-tinggi dari LCM mungkin sudah cukup. Keacakan nilai bit-bit rendah dari LCM dengan modulus berupa perpangkatan 2 tidak disarankan untuk digunakan. Hal ini disebabkan karena periode yang sangat pendek. Sebagai contoh, LCM dengan modulus berupa perpangkatan 2, dan dengan hasil yang tidak mengalami pemotongan bit, akan menghasilkan bilangan genap dan bilangan ganjil yang berselang-seling.

LCM perlu dievaluasi secara mendalam untuk penggunaan pada aplikasi non-kriptografis yang memerlukan kualitas keacakan tinggi. Untuk simulasi Monte Carlo dibutuhkan LCM dengan nilai modulus yang (jauh) lebih besar daripada pangkat tiga dari banyak keluaran yang dibutuhkan. Hal ini mengartikan, sebagai contoh, LCM 32 bit (yang baik) dapat digunakan untuk menghasilkan sekitar 1000 bilangan acak, dan LCM 64 dapat digunakan untuk menghasilkan 221 (sedikit diatas dua juta) bilangan. Karena keadaan tersebut, LCM secara praktis tidak cocok untuk simulasi Monte Carlo skala besar.

Implementasi

Berikut salah satu implementasi LCM dalam bahasa pemrograman Python:<syntaxhighlight lang="python"> def lcg(modulus, a, c, seed): 

   """Linear congruential generator."""
   while True:
       seed = (a * seed + c) % modulus
       yield seed

</syntaxhighlight>Seperti semua pembangkit bilangan acak semu lainnya, LCM perlu menyimpan dan mengubah keadaan bilangan acak yang dihasilkan. Komputer dengan banyak utas yang mengakses keadaan ini dapat menyebabkan race condition. Implementasi dengan setiap utas memiliki inisialisasi nilai awal yang unik diperlukan agar tidak ada utas dengan barisan bilangan acak yang sama.

Turunan LCM

Terdapat beberapa pembangkit dengan bentuk yang didasarkan pada LCM, sehingga teknik yang digunakan untuk menganalisis LCM juga dapat dipakai untuk mereka.

Salah satu metode untuk menghasilkan periode yang lebih panjang adalah dengan menjumlahkan beberapa LCM, dengan periode yang berbeda dan memiliki faktor bersama yang besar. Pembangkit Wichmann-Hill adalah salah satu contoh metode ini. Metode ini dapat ditunjukkan ekuivalen dengan sebuah LCM dengan modulus sebagai hasil perkalian modulus LCM komponen-komponennya.

Referensi

  1. ↑ Linear Congruential Generators - Wolfram Demonstrations Project. demonstrations.wolfram.com.
  2. ↑ Donald E. Knuth. Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley Professional. 6 May 2014. hlm. 4–. ISBN 978-0-321-63576-1.
  3. ↑ Guy Steele. Computationally easy, spectrally good multipliers for congruential pseudorandom number generators. arXiv:2001.05304 [cs]. 2021-01-21.
  4. ↑ Derrick H. Lehmer. Mathematical methods in large-scale computing units. Proceedings of 2nd Symposium on Large-Scale Digital Calculating Machinery. 1951. hlm. 141–146.
  5. ↑ W. E. Thomson. A Modified Congruence Method of Generating Pseudo-random Numbers. The Computer Journal. 1958-02-01. Vol. 1 (2). hlm. 83–83. doi:10.1093/comjnl/1.2.83.
  6. ↑ A. Rotenberg. A New Pseudo-Random Number Generator. Journal of the ACM. 1960-01-01. Vol. 7 (1). hlm. 75–77. doi:10.1145/321008.321019.
  7. ↑ Metode LCM (Linear Congruent Method) - Mesran Punya Blog. mesran.blogspot.com.
  8. ↑ Pierre L'Ecuyer. History of Uniform Random Number Generation. 13 July 2017.
  9. ↑ Guy Steele. Computationally easy, spectrally good multipliers for congruential pseudorandom number generators. arXiv:2001.05304 [cs]. 2021-01-21.
  10. ↑ Metode LCM (Linear Congruent Method) - Mesran Punya Blog. mesran.blogspot.com.
  11. ↑ George Marsaglia. Random Numbers Fall Mainly in the Planes. Proceedings of the National Academy of Sciences. 1968-09-01. Vol. 61 (1). hlm. 25–28. doi:10.1073/pnas.61.1.25.
  12. ↑ S. K. Park. Random number generators: good ones are hard to find. Communications of the ACM. 1988-10-01. Vol. 31 (10). hlm. 1192–1201. doi:10.1145/63039.63042.
  13. ↑ W. Hörmann. A portable random number generator well suited for the rejection method. ACM Transactions on Mathematical Software. 1993-12-01. Vol. 19 (4). hlm. 489–495. doi:10.1145/168173.168414.
  14. ↑ Donald Knuth. Seminumerical Algorithms. Addison-Wesley Professional. 1997. hlm. 10-26.
  15. ↑ William H. Press. Numerical Recipes in Fortran 77: The Art of Scientific Computing. 1992. ISBN 978-0-521-43064-7.
  16. ↑ Raj Jain. Computer Systems Performance Analysis Chapter 26: Random-Number Generation. 9 July 2010. hlm. 19–20.
  17. ↑ Paul Fenerty. Schrage's Method. 11 September 2006.
  18. ↑ Donald Knuth. Seminumerical Algorithms. Addison-Wesley Professional. 1997. hlm. 10-26.
  19. ↑ Donald Knuth. Seminumerical Algorithms. Addison-Wesley Professional. 1997. hlm. 10-26.
  20. ↑ T. E. Hull. Random Number Generators. SIAM Review. July 1962. Vol. 4 (3). hlm. 230–254. doi:10.1137/1004061.
  21. ↑ Severance, Frank. System Modeling and Simulation. John Wiley & Sons, Ltd. 2001. hlm. 86. ISBN 978-0-471-49694-6.
  22. ↑ Donald Knuth. Seminumerical Algorithms. Addison-Wesley Professional. 1997. hlm. 10-26.
  23. ↑ Donald Knuth. Seminumerical Algorithms. Addison-Wesley Professional. 1997. hlm. 10-26.
  24. ↑ Guy Steele. Computationally easy, spectrally good multipliers for congruential pseudorandom number generators. arXiv:2001.05304 [cs]. 2021-01-21.
  25. ↑ Pierre L’Ecuyer. Tables of linear congruential generators of different sizes and good lattice structure. Mathematics of Computation. 1999. Vol. 68 (225). hlm. 249–260. doi:10.1090/S0025-5718-99-00996-5.
  26. ↑ Implementation in glibc-2.26 release. See the code after the test for "TYPE_0"; the GNU C library's rand() in stdlib.h uses a simple (single state) linear congruential generator only in case that the state is declared as 8 bytes. If the state is larger (an array), the generator becomes an additive feedback generator (initialized using minstd_rand0 ) and the period increases. See the simplified code that reproduces the random sequence from this library.
  27. ↑ K. Entacher. A collection of selected pseudorandom number generators with linear structures. 21 August 1997.
  28. ↑ Last public Committee Draft from April 12, 2011. hlm. 346f.
  29. ↑ How Visual Basic Generates Pseudo-Random Numbers for the RND Function. Microsoft Support. Microsoft.
  30. ↑ In spite of documentation on MSDN, RtlUniform uses LCG, and not Lehmer's algorithm, implementations before Windows Vista are flawed, because the result of multiplication is cut to 32 bits, before modulo is applied
  31. ↑ ISO/IEC 14882:2011. ISO. 2 September 2011.
  32. ↑ ISO/IEC 14882:2011. ISO. 2 September 2011.
  33. ↑ GNU Scientific Library: Other random number generators
  34. ↑ Stephen J. Chapman. "Example 6.4 – Random Number Generator". "MATLAB Programming for Engineers". 2015. pp. 253–256.
  35. ↑ Stephen J. Chapman. "Example 6.4 – Random Number Generator". "MATLAB Programming with Applications for Engineers". 2012. pp. 292–295.
  36. ↑ S. J. Chapman. random0. 2004.
  37. ↑ Stephen J. Chapman. "Introduction to Fortran 90/95". 1998. pp. 322–324.
  38. ↑ Wu-ting Tsai. "'Module': A Major Feature of the Modern Fortran" . pp. 6–7.
  39. ↑ The Open Group Base Specifications Issue 7 IEEE Std 1003.1, 2013 Edition
  40. ↑ Sidney Cadot. rand.s. cc65.
  41. ↑ William H. Press. Numerical Recipes in Fortran 77: The Art of Scientific Computing. 1992. ISBN 978-0-521-43064-7.
  42. ↑ Melissa E. O'Neill. PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation. Harvey Mudd College. 5 September 2014. hlm. 6–7.
  43. ↑ George Marsaglia. Random Numbers Fall Mainly in the Planes. Proceedings of the National Academy of Sciences. 1968-09-01. Vol. 61 (1). hlm. 25–28. doi:10.1073/pnas.61.1.25.

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 29301643 (2026-06-01T06:18:00Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.


Diperoleh dari "https://wiki.unissula.ac.id/index.php?title=Metode_linear_kongruen&oldid=8934"