Tugas Random Number Generation (RNG)

Random Number Generation (RNG)

- Additive/Arithmatic RNG

- Multiplier RNG

- Mixed Pseudo RNG

Random Number Generation

RNG adalah suatu algoritma yang digunakan untuk menghasilkan urutan dari angka-angka sebagai hasil dari perhitungan dengan komputer yang diketahui distribusinya sehingga angka-angkanya muncul secara random dan terus menerus.

Algoritma RNG dibuat oleh usulan Lehmer (1951)

Unsur - Unsur Random Number Generator

- Sequence (urutan)

- Distribusi

- Random

Sumber Random

1. Tabel Random Number

Menggunakan tabel distribusi untuk mengetahui penyebaran bilangan acak

2. Elektronik Random Number

Menggunakan suatu alat yang dapat menghasilkan bilangan acak. Alat ini banyak digunakan dalam percobaan penelitian.

Bagian dari RNG

n RNG ada 3 macam :

1. Additive (arithmathic) RNG

2. Multiplier RNG

3. Mixed Pseudo RNG

n Random Number pada computer sering menggunakan RNG

n Biasanya qt sering menggunakan fungsi yangtelah disediakan program

ex : random( )

Sifat RNG

n Independen

variabelnya bebas tidak terikat dengan memiliki ketentuan ketentuan tersendiri

n Uniform

probabilitas diusahakan sama untuk setiap penarikan random number tersebut

n Dense

densitas probabilitas distribusinya harus terletak antara 0 dan 1

n Efficient

cukup sederhana dan dalam pemakaiannya harus menentukan angka-angka untuk variabel yang cocok

Additive / Arithmatic RNG

n Formula :

Modulo merupakan satu angka integer yang cukup besar dan yang dipakai pada computer. Setiap komputer bisa memiliki modulo yang berbeda.

Ex:

komputer IBM 360/370 dapat mensupport jangkauan 32 bit integer

mikrokomputer 8 bit

Contoh Additive RNG

Jika digunakan mikrokomputer 8 bit dengan :

Xo=12357

a = 19 ; m = 128 ; c = 237

Maka bilangan random yang terbentuk dan densitas yang terbentuk adalah …

X1 =(19.12357+237) mod 128

X1 =235020 – 1836.128 = 12

Densitas (R1) = 12/128 = 0.09375

Additive Random Number Generator

Additive Random Number Generator. Suatu RNG (Random Number Generator) yang berdasarkan lFSR (Linier Feedback Shift Register) secara khusus menggunakan unsur – unsur multi – bit dan integer sebagai pengganti kombinasi XOR.

Keuntungannya :

• Satuan panjang, panjang siklus, dibuktikan secara matematis.
• Implementasi perangkat lunak yang efisien.
• Initialisasi yang sewenang – wenang (beberapa unsur harus mempunyai bit yang sedikit dan yang penting tetap).
• Suatu desain sederhana yang mudah untuk dimengerti dengan jelas.

Sebagai tambahan, suatu keanekaragaman yang luas dari siklus yang mandiri mempunyai potensi untuk mengacaukan suatu “komputer quantum”.

For Degree-n Primitive and Bit Width w

Total States : 2^nw

Non – Init States : 2^n(w-1)

Number of Cycles : 2^(n-1)(w-1)

Length Each Cycle : (2ⁿ-1)2^(w-1)

Period of LSB : 2ⁿ-1

Penambahan biner dua bit dengan tidak memasukkan XOR menyebabkan LSB (Least Significant Bit) suatu Additive Random Number Generator mempunyai periode panjang maksimal.

Additive Random Number Generator merupakan 127 untuk unsur – unsur 32 dari masing – masing bit yang mempunyai 2⁴⁰⁶⁴ keadaan khusus, 2³⁹³⁷ ditolak oleh initialisasi (LSB semuanya “0″) tetapi ini baru satu status yang tak dapat dipakai keluar 2¹²⁷. Masih ada 2³⁹⁰⁶ siklus yang masing – masing mempunyai hampir 2¹⁵⁸langkah. (Stream chyper menggunakan suatu Additive Random Number Generator dengan 9689 unsur – unsur daari 32 bit dan mempunyai 2³¹⁰⁰⁴⁸ keadaan yang unik. Sebagian besar dibagi 2³⁰⁰³²⁸ sikluk yang berbeda dengan masing – masing hampir 2⁹⁷²⁰ langkah).

Catatan : semua LSFR yang mencakup Additive Random Number Generator sangat lemah ketika digunakan sendiri, tetapi jika langkah – langkah tersembunyikan urutan diambil, (seperti penggunaan suatu jitterizer dan suatu kombinasi Substitution yang dinamis) hasilnya akan mempunyai kekuatan yang penting.