Random is on fashion!
My recent writings on my thesis were about pseudorandom numbers generators. You may be thinking "Why they are called pseudorandom?", and is a common question and a subject of large discutions.
By definition, any sequence of number is called random if is agree with the following properties:
My recent writings on my thesis were about pseudorandom numbers generators. You may be thinking "Why they are called pseudorandom?", and is a common question and a subject of large discutions.
By definition, any sequence of number is called random if is agree with the following properties:
- There's no identificable patterns over the sequence
- Is well distribuited over a set (even on an statistical set)
- Is imposible to guess the future numbers based on the current numbers
If you're using an algorith to generate the sequence, is sure that you're breaking the last condition. And the reason is simple: There's no algorithm with REAL stochastical behavior.
If you're looking for real random number generators, then you should look elsewhere. One of the most common source of true random numbers are physical phenomena, like electric noise or atmospheric noise. Is posible to find random numbers generated from the second phenomena at www.random.org, and with the first in some cryptographic devices (such an IBM crypto-card).
Back to algorithms, there's several generator. One of the most famous and popular, and not necesarly most powerful, is the Linear Congruential Generator (LCG). This generator has been used since the last 40's, when the Monte Carlo simulation arise as a new technique. The basic recurrence relation behind a LCG is defined by:
If you're looking for real random number generators, then you should look elsewhere. One of the most common source of true random numbers are physical phenomena, like electric noise or atmospheric noise. Is posible to find random numbers generated from the second phenomena at www.random.org, and with the first in some cryptographic devices (such an IBM crypto-card).
Back to algorithms, there's several generator. One of the most famous and popular, and not necesarly most powerful, is the Linear Congruential Generator (LCG). This generator has been used since the last 40's, when the Monte Carlo simulation arise as a new technique. The basic recurrence relation behind a LCG is defined by:
Xi = (aXi-1 + c) % m
With this simple formula, is posible to generate a sequence up to m different values. When m is well chosen, it is possible to increase the generator period (numbers generated before it start to repeat), to a maximun of m. Nevertheles, a and c must be well chosen for improving the equidistribution over several sets. Park & Miller, defined and standard for choosing a, and m. They realized that (after some research) generators with c = 0 had the same or better behavior than generators with c!=0. The minimal standar that they pick was:
a = 16807; m = (1<<31) - 1
Some other implementations may be found in the code published on this post, including ran0, ran1 and ran2.
Is important to mention the Blum Blum Shub generator, proposed by the Leonore Blum, Manuel Blum and Michael Shub. This generator is widely used in cryptography. Due this work and some others, Manuel Blum (who born in Venezuela!) gained an Turing Award in 1996.
Comments (0)
