@agatestudio

Pseudo Random Number Generator &

Mersenne Twister

Sanrio Hernanto

Knight

Agate Studio

@agatestudio

PSEUDO RANDOM NUMBER GENERATOR (PRNG)

• Algoritma untuk menghasilkan urutan angka yang terdistribusi secara random

• Urutan didapatkan berdasarkan nilai awal

Random Seed

initial value random number sequencePRNG

@agatestudio

Pseudo Random Number Generator (PRNG)

• Keunggulan PRNG

– Speed

– Reproducibility

• Penggunaan

– Simulation Apps

– Procedural Generation

– Cryptography

• Blum Blum Shub

• Wichmann-Hill

• Complementary-multiply-with-carry

• Inversive congruential generator

• ISAAC (cipher)

• Lagged Fibonacci generator

• Linear congruential generator

• Linear feedback shift register

• Maximal periodic reciprocals

• Mersenne Twister

• Multiply-with-carry

• Naor-Reingold Pseudorandom Function

• Park–Miller random number generator

• RC4 PRGA

• Well Equidistributed Long-period Linear

• Xorshift

Contoh-contoh implementasi PRNG

@agatestudio

Mersenne Twister

• Algoritma PRNG yang dibuat pada tahun 1997

• PRNG pertama yang dapat menghasilkanpseudorandom integer dengan kualitas tinggi danalgoritma yang cepat

• PRNG yang banyak digunakan sampai sekarang

• PRNG Default

– R

– Python

– Ruby

– IDL

– Free Pascal

– PHP

– Maple

– MATLAB

– GAUSS

– CMU Common Lisp

– GNU Multiple Precision Arithmetic Library

– GNU Scientific Library

Penggunaan Mersenne Twister

@agatestudio

Keunggulan Mersenne Twister

• Keunggulan

– Panjang deret yang sangat tinggi (2^19937 - 1)

– Telah diuji dengan berbagai tes untuk statistical randomness

• Kelemahan

– Gagal melewati beberapa tes randomness

– Kurang cocok untuk kriptografi

@agatestudio

Extra Note

• Pseudo Random Number Generator tidak menghasilkannilai random yang sempurna, termasuk mersennetwister.

• Untuk nilai random seed yang sama, algoritma mersennetwister yang sama akan menghasilkan nilai yang sama

• Terdapat berbagai macam implementasi mersennetwister, random seed yang sama pada implementasimersenne twister yang berbeda akan menghasilkan nilaiyang berbeda

Implementasi Mersenne Twister

Variasi Implementasi

– SFMT (SIMD-oriented Fast Mersenne Twister)

– MTGP

Implementasi pada bahasapemrograman berbeda

– ActionScript

– Ada

– C++

– C#

– Java

– Javascript

– PHP

– Python

– etc

Sekian

Terima Kasih