Search Results for “metode linear kongruen”

Source: Metode linear kongruen

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 komputer yang mendukung aritmetika modular dengan pemotongan pada bit-bit penyimpanan. LCM memanfaatkan relasi rekursif linear:

X

n
+
1

=

(

a

X

n

+
c

)

mod

m

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

dengan

X

{\displaystyle X}

sebagai barisan bilangan acak semu, dan konstanta bilangan bulat

m

{\displaystyle m}

positif sebagai "modulus"

a

{\displaystyle a}

dengan

0
<
a
<
m

{\displaystyle 0
sebagai "pengali"

c

{\displaystyle c}

dengan

0
≤
c
<
m

{\displaystyle 0\leq c
sebagai "penambah"; dan

X

0

{\displaystyle X_{0}}

dengan

0
≤

X

0

<
m

{\displaystyle 0\leq X_{0}
sebagai "benih", "nilai awal", atau "kondisi awal"
sebagai parameter khas untuk LCM. Jika

c
=
0

{\displaystyle c=0}

, metode ini umum disebut degan metode kongruensial multiplikatif (Inggris: multiplicative congruential generator, MCG) atau pembangkit Lehmer. Jika

c
≠
0

{\displaystyle c\neq 0}

, metode ini disebut metode kongruensial campuran. Ketika

c
≠
0

{\displaystyle c\neq 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.

Demonstrasi

Sejarah

Metode

linear

kongruen

Panjang periode

= m bilangan prima, c = 0

metode

, suku pertama tegas lebih kecil dari

a
m

/

a
=
m

{\displaystyle am/a=m}

. Jika

a

{\displaystyle a}

dipilih sehingga

r
≤
d

{\displaystyle r\leq d}

(sehingga

r

/

q
≤
1

{\displaystyle r/q\leq 1}

), maka suku kedua juga akan lebih kecil dari

m

{\displaystyle m}

karena

r
⌊
x

/

q
⌋
≤
r
x

/

q
=
x
(
r

/

q
)
≤
x
<
m

{\displaystyle r\lfloor x/q\rfloor \leq rx/q=x(r/q)\leq x
.
Dengan cara ini, untuk menghitung kedua suku cukup digunakan single-width product, dan selisih antara keduanya terletak di

[
1
−
m
,

m
−
1
]

{\displaystyle [1-m,\,m-1]}

, sehingga dapat disederhanakan menjadi

[
0
,

m
−
1
]

{\displaystyle [0,\,m-1]}

dengan satu kondisi penjumlahan.
Kekurangan kedua dari metode ini adalah cukup canggung untuk mengonversi nilai

1
≤
x
<
m

{\displaystyle 1\leq x
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

{\displaystyle m}

sebagai perpangkatan dari 2, umumnya

m
=

2

32

{\displaystyle m=2^{32}}

atau

m
=

2

64

{\displaystyle m=2^{64}}

, 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

{\displaystyle m/4}

, diperoleh ketika

a
≡
3

mod

8

{\displaystyle a\equiv 3\ \ {\text{mod}}\ \ 8}

atau

a
≡
5

mod

8

{\displaystyle a\equiv 5\ \ {\text{mod}}\ \ 8}

. Kondisi awal

X

0

{\displaystyle X_{0}}

perlu bilangan ganjil, dan nilai tiga bit terkecil dari

X

{\displaystyle X}

berseling antara dua nilai sehingga tidak berguna. Dapat ditunjukkan bahwa bentuk ini setara dengan pembangkit dengan modulus

m

/

4

{\displaystyle m/4}

dan

c
≠
0

{\displaystyle c\neq 0}

.
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

{\displaystyle X}

tidak pernah berubah (karena selalu bilangan ganjil), dan dua bit selanjutnya berseling antara dua nilai (jika

a
≡
5

mod

8

{\displaystyle a\equiv 5\ \ {\text{mod}}\ \ 8}

, nilai bit 1 tidak pernah berubah dan nilai bit 2 berseling, sedangakan jika

a
≡
3

mod

8

{\displaystyle a\equiv 3\ \ {\text{mod}}\ \ 8}

nilai bit 1 berseling dan nilai bit 2 selalu tetap).

= c ≠ 0

=
Ketika

c
≠
0

{\displaystyle c\neq 0}

, pemilihan parameter yang baik memungkinkan periode dapat sepanjang

m

{\displaystyle m}

, untuk semua kondisi awal. Hal ini terjadi, jika dan hanya jika:

m

{\displaystyle m}

dan

c

{\displaystyle c}

koprima ,

a
−
1

{\displaystyle a-1}

dapat dibagi semua faktor prima dari

m

{\displaystyle m}

,

a
−
1

{\displaystyle a-1}

dapat dibagi 4 jika

m

{\displaystyle m}

dapat dibagi 4.
Tiga syarat ini dikenal sebagai Teorema Hull–Dobell.
Bentuk ini dapat digunakan untuk sebarang

m

{\displaystyle m}

, namun hanya bekerja dengan baik untuk

m

{\displaystyle m}

yang memiliki banyak faktor prima yang berulang, seperti perpangkatan angka 2. Jika

m

{\displaystyle m}

bilangan bebas-kuadrat, hal ini mengakibatkan

a
≡
1

mod

m

{\displaystyle a\equiv 1\ \ {\text{mod}}\ \ m}

, menjadikannya pembangkit bilangan acak yang sangat buruk. Pengali dengan periode maksimum hanya tersedia ketika

m

{\displaystyle 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

{\displaystyle a-1}

yang lebih sulit dibagi oleh faktor-faktor prima

m

{\displaystyle m}

lebih disukai. Karena itu, jika

m

{\displaystyle m}

adalah perpangkatan angka 2, maka

a
−
1

{\displaystyle a-1}

perlu dapat dibagi 4 namun tidak dapat dibagi 8, misal

a
≡
5

mod

8

{\displaystyle a\equiv 5\ \ {\text{mod}}\ \ 8}

.
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

{\displaystyle c=0}

:

k

{\displaystyle k}

bit terendah menghasilkan pembangkit dengan modulus

2

k

{\displaystyle 2^{k}}

dan karenanya memiliki periode

2

k

{\displaystyle 2^{k}}

; hanya bit paling signifikan yang memiliki periode penuh. Jika sebuah bilangan acak semu kurang dari

r

{\displaystyle r}

yang diperlukan, menghitung

⌊
r
X

/

m
⌋

{\displaystyle \lfloor rX/m\rfloor }

memberikan hasil yang lebih baik ketimbang

X

mod

r

{\displaystyle X\ \ {\text{mod}}\ \ r}

. Sayangnya pada kebanyakan bahasa pemrograman, bentuk terakhir lebih banyak digunakan karena lebih mudah ditulis
Pembangkit LCM sendiri tidak sensitif terhadap pemilihan

c

{\displaystyle c}

, selama nilainya koprima terhadap modulus (misal, jika

m

{\displaystyle m}

merupakan perpangkatan angka 2, maka

c

{\displaystyle c}

perlu bernilai ganjil), sehingga nilai

c
=
1

{\displaystyle c=1}

umum dipilih.
Barisan yang dihasilkan dari pemilihan

c

{\displaystyle c}

yang lain dapat ditulis sebagai fungsi sederhana dari barisan ketika

c
=
1

{\displaystyle c=1}

. Secara spesifik, jika

Y

{\displaystyle Y}

adalah barisan yang didefinisikan dengan

Y

0

=
0

{\displaystyle Y_{0}=0}

dan

Y

n
+
1

=
a

Y

n

+
1

mod

m

{\displaystyle Y_{n+1}=aY_{n}+1\ \ {\text{mod}}\ \ m}

, maka barisan

X

n
+
1

=
a

X

n

+
c

mod

m

{\displaystyle X_{n+1}=aX_{n}+c\ \ {\text{mod}}\ \ m}

dapat ditulis sebagai fungsi affine dari

Y

{\displaystyle Y}

:

X

n

=
(

X

0

(
a
−
1
)
+
c
)

Y

n

+

X

0

=
(

X

1

−

X

0

)

Y

n

+

X

0

(
mod

m
)

.

{\displaystyle X_{n}=(X_{0}(a-1)+c)Y_{n}+X_{0}=(X_{1}-X_{0})Y_{n}+X_{0}{\pmod {m}}.}

Secara umum, dua barisan

X

{\displaystyle X}

dan

Z

{\displaystyle Z}

yang memiliki pengali dan modulus yang sama memiliki hubungan:

X

n

−

X

0

X

1

−

X

0

=

Y

n

=

a

n

−
1

a
−
1

=

Z

n

−

Z

0

Z

1

−

Z

0

(
mod

m
)

.

{\displaystyle {X_{n}-X_{0} \over X_{1}-X_{0}}=Y_{n}={a^{n}-1 \over a-1}={Z_{n}-Z_{0} \over Z_{1}-Z_{0}}{\pmod {m}}.}

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.

Seperti terlihat di atas, LCM tidak selalu menggunakan semua bit bilangan yang dihasilkan. Sebagai contoh, implementasi Java beroperasi dengan 48-bit pada setiap iterasi, namun 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.
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

≈

2

16

{\displaystyle {\sqrt {m}}\approx 2^{16}}

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

2

64

{\displaystyle 2^{64}}

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

{\displaystyle n}

, titik tersebut akan terletak (maksimal) pada

n
!
m

n

{\displaystyle {\sqrt[{n}]{n!m}}}

hyperplane, berdasarkan teorema Marsaglia (yang dikembangkan oleh George Marsaglia). Hal ini disebabkan oleh serial correlation antar nilai yang berurutan pada barisan

X

n

{\displaystyle X_{n}}

. 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

2

64

{\displaystyle 2^{64}}

.
Salah satu kecacatan lain yang spesifik pada LCM adalah periode bit-rendah yang pendek ketika

m

{\displaystyle 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

2

21

{\displaystyle 2^{21}}

(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: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.