In Java random numbers can be generated by using Math.random() or by the functions in the Random class of java.util package as discussed in my previous post. I got a couple of messages from some of my students who wanted to know how these methods of generating random number works. In this post I will be discussing one such relatively simple method of generating random number known as linear congruential method.

Random numbers generated using software methods are not truly random. It should be obvious that these are generated by deterministically producing a sequence of numbers that appear to exhibit random behaviour.  These sequences are predictable in advance and due to this they are usually termed as pseudo-random number. These sequences are statistically random meaning that they are uniformly distributed. A uniform distribution implies that each possible number is equally probable.

The implementation of the linear congruential method is quiet straight-forward, however for a detailed mathematical treatment students are advised to read The Art of Computer Programming, Volume 2 by D.E. Knuth. Successive values of the linear congruential sequence {x} can be generated using the following expression:

x_n+1 = (ax_n+b) % m for n>=0

where a,b,c are referred to as the multiplier, increment and modulus respectively. The choice of these parameters dictates how efficient the implementation would be. All parameters must be integers greater than or equal to zero and m should be greater than x₀, a and b. The parameter x₀ can be chosen arbitrarily within the range of 0 to m. The value of m should be greater than or equal to the length of the random sequence required. The choice of a is dependent on m. If m is a power of 2 then a % 8 should be 5. If m is the power of 10, then a should be chosen such that a % 200=21. Additional requirements are that a should be larger than √m and less than m-√m, (a-1) should be a multiple of every prime dividing into m, and if m is a multiple of 4 then (a-1) should be a multiple of 4. The constant b should be odd and not a multiple of 5. The Wikipedia link given above enumerates the values of these parameters for various popular libraries like glibc, MSVC++, MSVB6 etc. Also note that m is the period of the sequence meaning that the sequence would repeat at some point for a given values of a, b and c.

A Java implementation of a random number generator using linear congruential method is as follows:

class MyRandom{
    int a; //multiplier
    int b; //increment
    int m; //modulus
    int x; //random number
    public MyRandom(){
        m=4096;
        b=853;
        a=109;
        x=(int)(System.nanoTime() % m);
    }
    public int getRandomNumber(){
        x=(a * x + b) % m;
        return x;
    }
    public static void main(String []args){
        MyRandom objMyRandom = new MyRandom();
        for(int i=1; i<=20; i++){
            System.out.println(objMyRandom.getRandomNumber());
        }
    }
}

In the above program the function nanoTime() is used to seed or assign the first value for x, that is x₀. Use of nanoTime() is not essential to the logic of the program. As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement. In this case the main() function would generate ten random numbers using are own implementation of random number generator.