Simple Random Number

Introduction

There are many algorithms to generate random number, some require very complex operations in order for the random sequence to have good statistical properties. As the title suggested, this article focus on "simple" algorithm only. That is, no more than a few lines of coding.

Physical Randomness vs Pseudo Randomness

Roughly speaking, a random sequence of numbers should be unpredictable. However, many computer algorithms use deterministic formula to generate random sequence. The sequence is hence predictable if we know the formula and the parameters in advance. To get really random data, we need some physical methods. For example, we may throw 10 dices a hundred times and record the sum of every throw. Of course I am not talking about virtual dice in computer, I am talking about physical dice in reality.

Throwing physical dices does produce pretty random results. It is, however, not practical in computer applications. Fortunately, there exists some methods to collect physical random data in computer, for example, the mini seconds value of the system clock, the hard disk seeking time, the time interval between key press, the pattern of mouse cursor movements are good source for randomness. Collecting these data periodically could produce quite unpredictable results, which is a good starting point for a random seed.

Test for randomness

Not all algorithms produce good random sequences. A good random sequence is required to have certain statistical properties. This is not a statistics course and I am not going through the details here. Instead I would use some more interesting and intuitive method to test whether a sequence is "random" enough. But first we must clarify what is random enough. The obvious question is "random enough for what purpose ?". In this article, "good enough" means it is good enough for casual applications such as computer game, but not for gambling game that involves real money.

How should we define good random sequence ? There are some strict answers in statistical sense. However, those are not the scope of this article. I would give an answer in a more informal sense. Intuitively, a random sequence should at least "looks" random. The next section we will provide a "visual test" for randomness. Note that the visual test only provides a gut feeling for randomness, it is not a strict science.

Linear Congruential Generator

One of the simplest random sequence generator is the linear congruential generator. Which has the following form :

N0 = seed
Ni+1 = (a*Ni + c ) mod m

For example, if we have a=16807, m=2147483647, seed=1, c=0, then we have the following sequence :

N0=1
N1=(16807*1+0) mod 2147483647 = 16807
N2=(16807*16807+0) mod 2147483647 = 282475249
N3=(16807*282475249+0) mod 2147483647 = 1622650073

The implementation is simple :

class LCG
{
  int a=16807,m=2147483647,seed=1, c=0;
  public int nextRandom()
  {
    seed=(a*seed + c) % m;
    return seed;
  }

  public static void main(String[] args) throws Exception
  {
    LCG random=new LCG();

    for (int i=0;i<10;i++)
    {
      System.out.println(random.nextRandom());
    }
  }
}

Visual Test

How good is the above random sequence ? Does it "look" random ? OK, let's have a "look" at it. The following program will generate a random "star field" using the above random sequence.

/******************************************************************************
* File : RandomStarField.java
* Author : http://java.macteki.com/
* Description :
*   Draw a random star field using a random number generator.
* Tested with : JDK 1.6
******************************************************************************/

import java.awt.image.BufferedImage;

class RandomStarField extends javax.swing.JPanel implements Runnable
{
  private BufferedImage image;    // image for holding the star field
  private boolean running=false;  // thread is running

  public RandomStarField()
  {
    this.setPreferredSize(new java.awt.Dimension(300,300));
    image = new BufferedImage(300,300,BufferedImage.TYPE_INT_RGB);
  }

  // override the paint method
  public void paintComponent(java.awt.Graphics graphics)
  {
    graphics.drawImage(image,0,0,this);
  }

  // this method is to be overridden for different random tests
  int a=16807,m=2147483647,seed=1, c=0;
  public int nextRandom()
  {
    seed=(a*seed + c) % m;
    return seed;
  }


  // thread entry point
  public void run()
  {
    java.awt.Graphics gr=image.getGraphics();
    int pixelCount=0;
    java.awt.Color[] colorTable=new java.awt.Color[] {
      java.awt.Color.RED, java.awt.Color.GREEN, java.awt.Color.BLUE, java.awt.Color.WHITE
    };
    running=true;
    while (running)
    {
      int x=Math.abs(nextRandom() % 300);  // random coordinates 
      int y=Math.abs(nextRandom() % 300);

      gr.setColor(colorTable[pixelCount%4]);  // cycle over 4 colors
      pixelCount++;
      gr.drawLine(x,y,x,y);      // draw the random pixel
      repaint();
      try { Thread.sleep(30); } catch (Exception ignore) {}
    }
  }

  // stop a running thread
  public void stop()
  {
    running=false;
  }

  // testing
  public static void main(String[] args) throws Exception
  {
    javax.swing.JFrame window=new javax.swing.JFrame();
    window.setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);
    window.setTitle("Macteki testing on Randomness");
    RandomStarField field = new RandomStarField();
    window.add(field);
    window.pack();
    window.setVisible(true);

    Thread thread=new Thread(field);
    thread.start();

  }
}

Here is how the "star field" looks like after running the program for one minute, at least it looks quite random:

Let's modify the nextRandom() method to generate a "visually less random" sequence. Just change the parameter m to 65536 to see what would happen.

  int a=16807, m=65536, seed=1, c=0;
  public int nextRandom()
  {
    seed=(a*seed + c) % m;
    return seed;
  }

The star field is as follows. Obviously it looks less random, and we would say this random sequence is not as good as the previous one. It shows that the choice of parameters is very important for linear congruential generator.

XORShift Random Number Generator

This method is invented by George Marsaglia. It generates a sequence of long integer. We will only use the higher 32 bits for the integer sequence.

//  XORShift Random Number Generator by George Marsaglia 
  long x=1;
  private long nextRandomLong() {
    x ^= (x << 21);
    x ^= (x >>> 35);
    x ^= (x << 4);
    return x;
  }

  // override nextRandom() for random test
  public int nextRandom()
  {
    return (int) (nextRandomLong()>>>32);  // we need 32 bits only
  }

How does the star field look like ? We will see it later. Let's see some other random sequence first.

Multiply by Carry

This method is also invented by George Marsaglia. The implementation is :

  int w = 31;    // must not be zero 
  int z = 41;    // must not be zero 
 
  public int nextRandom()
  {
    z = 36969 * (z & 65535) + (z >> 16);
    w = 18000 * (w & 65535) + (w >> 16);
    return (z << 16) + w;  // 32-bit result 
  }

java.util.Random

Finally we have the Java API implementation of random sequence.

  java.util.Random random=new java.util.Random(1);

  // override the nextRandom() method
  public int nextRandom()
  {
    return random.nextInt();
  }

Visual Random Test for all methods

With the help of multi threading, we may visually compare all methods in a single program. First we create four subclasses of RandomStarField, all we have to do is to override the nextRandom() method for different algorithms.

// java.util.Random
class StarField1 extends RandomStarField
{
  java.util.Random random=new java.util.Random(1);

  // override the nextRandom() method
  public int nextRandom()
  {
    return random.nextInt();
  }
}

//  XORShift Random Number Generator by George Marsaglia 
class StarField2 extends RandomStarField
{
  //  XORShift Random Number Generator by George Marsaglia 
  long x=1;
  private long nextRandomLong() {
    x ^= (x << 21);
    x ^= (x >>> 35);
    x ^= (x << 4);
    return x;
  }

  // override nextRandom() for random test
  public int nextRandom()
  {
    return (int) (nextRandomLong()>>>32);  // we need 32 bit only
  }
}

// Linear Congruential Generator
class StarField3 extends RandomStarField
{
  // override nextRandom() 
  int a=16807,m=2147483647,seed=1, c=0;
  public int nextRandom()
  {
    seed=(a*seed + c) % m;
    return seed;
  }
}

// Multiply-with-carry method invented by George Marsaglia.
class StarField4 extends RandomStarField
{

  int w = 31;    // must not be zero 
  int z = 41;    // must not be zero 
 
  public int nextRandom()
  {
    z = 36969 * (z & 65535) + (z >> 16);
    w = 18000 * (w & 65535) + (w >> 16);
    return (z << 16) + w;  // 32-bit result 
  }

}

Next we create a window to hold the four star fields. To run the demo, you must have RandomStarField.java and VisualRandomTest.java in the same folder.

javac *.java
java VisualRandomTest

RandomStarField.java is listed above. VisualRandomTest.java is as follows :

/******************************************************************************
* File : VisualRandomTest.java
* Author : http://java.macteki.com/
* Description :
*   Display visual test for four random sequences.
* Tested with : JDK 1.6
******************************************************************************/

class VisualRandomTest
{
  public static void main(String[] args) throws Exception
  {
    javax.swing.JFrame window=new javax.swing.JFrame();
    window.setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);
    window.setTitle("Macteki Visual Test on Randomness");

    // create four random star fields
    RandomStarField[] fields = {
      new StarField1(), new StarField2(), new StarField3(), new StarField4()
    };

    // use a GridLayout to hold the star fields
    window.setLayout(new java.awt.GridLayout(2,2,1,1));
    for (int i=0;i<fields.length;i++)
    {
      window.add(fields[i]);
    }
    window.pack();
    window.setVisible(true);

    // start all threads
    for (int i=0;i<fields.length;i++)
    {
      Thread thread=new Thread(fields[i]);
      thread.start();
    }

  }

}  // class VisualRandomTest

// java.util.Random
class StarField1 extends RandomStarField
{
  java.util.Random random=new java.util.Random(1);

  // override the nextRandom() method
  public int nextRandom()
  {
    return random.nextInt();
  }
}

//  XORShift Random Number Generators by George Marsaglia 
class StarField2 extends RandomStarField
{
  //  XORShift Random Number Generators by George Marsaglia 
  long x=1;
  private long nextRandomLong() {
    x ^= (x << 21);
    x ^= (x >>> 35);
    x ^= (x << 4);
    return x;
  }

  // override nextRandom() for random test
  public int nextRandom()
  {
    return (int) (nextRandomLong()>>>32);
  }
}

// Linear Congruential Generator
class StarField3 extends RandomStarField
{
  // override nextRandom() 
  int a=16807,m=2147483647,seed=1, c=0;
  public int nextRandom()
  {
    seed=(a*seed + c) % m;
    return seed;
  }
}

// Multiply-with-carry method invented by George Marsaglia.
class StarField4 extends RandomStarField
{

  int w = 31;    // must not be zero 
  int z = 41;    // must not be zero 
 
  public int nextRandom()
  {
    z = 36969 * (z & 65535) + (z >> 16);
    w = 18000 * (w & 65535) + (w >> 16);
    return (z << 16) + w;  // 32-bit result 
  }

}

The official Java convention suggests that we should use separate source file for every class. Yes, we should, but we don't have to. Since this site is focus on simplicity and readability, I prefer storing all the StarField subclasses in the same source file. Of course, this should not be done too often, for example, if the classes are very complex, it should go to another source file. In addition, if you are not the only member in the programming team, you'd better follow strict convention.

Are those good random sequences ?

Let's have a look at the result after running the program for one minute. All algorithms look quite random.

Let's see what happen after 30 minutes. That really shows a difference. The third method (linear congruential generator) is obviously "less random" than others. Anyway, I would say all of them are still acceptable for casual applications such as computer games.

Conclusion

This article introduces a visual random test for looking at random sequence. It is not a strict test. That means if a sequence "looks random" in the test, it doesn't mean it is random enough. However, if it doesn't look random at all in the test, you may say it is a bad sequence and discard it for further statistical tests.

Thanks for reading. Comments are welcome.