Friday, January 11, 2013

Algorithm for random number

I was trying understand the implementation of Java.util.Random implementation but could not crack through it!!

In Java, If we want to generate random number between 1 to 6 (dice game), we can implement like below.

Using  Java.util.Random

public class CheckRandom {

public static void main(String[] args) {
Random random = new Random();
for (int i =0; i< 10;i++) {
int nextInt = random.nextInt(6)+1;

Where random.nextInt(x), uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence. The general contract of nextInt is that one int value in the specified range is pseudorandomly generated and returned. All n possible int values are produced with (approximately) equal probability.

Using Java.math.random() 
This also works internally based on the java.util.random only. but it generates the values between 0.0 to 1.0.

We can make use of this in the following way to generate random number.
 int diceValue = (int)(Math.random()*6) + 1;

Here is the interesting algorithm for generating a random number. This explains in terms of mathematical expression.

What is a Linear Congruential Random Number Generator?

          Many computer applications rely on random number generation. For example, if you want to write a program to simulate a poker game, you don't want each player to get the same cards every hand. Since some programs require a large number of random numbers, we can greatly speed up the program by using a faster, more efficient random number generator. The method of this  random number generation by linear congruential method, works by computing each successive random number from the previous. Starting with a seed, Xo, the linear congruential method uses the following formula:

Xi+1 = (A*Xi + C) mod M
           In his book, The Art of Computer Programming, Donald Knuth presents several rules for maximizing the length of time before the random number generator comes up with the same value as the seed. This is desirable because once the random number generator comes up with the initial seed, it will start to repeat the same sequence of random numbers (which will not be so random since the second time around since we can predict what they will be). According to Knuth's rules, if M is prime, we can let C be 0 and he suggests that this variant of the line
THEOREM : (By Greenberger in 1961 )

The LCG defined above has full period . if and only if the following conditions are satisfied 

a)      m and c are relatively prime
     b)      If q is a prime number  that divides m , then q divides a-1
    c)      If 4 divides m, then 4 divides a-1
 The LCG tend to behave differently for c>0 and c=0
 A linear congruential generator lnc( ) generates a sequences of integers
                                      U0, U1 ,  ����.   , Uk
that are restricted to the range to m. On each call to lnc( ), you must
give it as argument the previous number in the sequence. It returns the following by
                                       Uk+1   =  ( a Uk +b ) mod (  m + 1).
 where a, b, and can be chosen to be any positive integers. (The operation mod n p is the integer remainder when the integer is divided by the integer p. This remainder must be between 0 and p-1, inclusive.) Once you�ve chosen these three constants and the starting value 0 you�ve completely defined the sequence that lnc( ) will produce. If you set a, b, and to reasonably large values (there are rules of thumb to follow in choosing these values so as the maximize the apparent disorder in the sequence: see Knuth, 1971), the resulting sequence looks satisfyingly random. Of course, you want numbers between 0 and 1, not integers between 0 and m. But you need only divide 1 k U + by m+2 to map the output of lnc into the desired range.

It�s easier to see what lnc( ) is doing if we pick small values a=5, b=1, and m=7. If 0 is set to 2, the resulting sequence is
2, 3, 0, 1, 6, 7, 4, 5, 2, 3, 0, 1 �.

No comments:

Post a Comment