pseudo-random numbers : Java Glossary

Pseudo Random Numubers

Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number — there are only methods to produce random numbers and a strict arithmetic procedure, of course, is not such a method.
~ John von Neumann (1903-12-28 1957-02-08 age:53)

There are two kinds of random numbers, pseudo-random numbers that can be rapidly generated from mathematical formulae and true random numbers, generated from some random physical process such as radioactive decay. We are discussing pseudo-random numbers here. These are what you nearly always want.

Random.nextInt(int)

The pseudo random number generator built into Java is portable and repeatable. If two Random objects are created with the same seed and the same sequence of method calls is made for each, they will generate and return identical sequences of numbers in all Java implementations.

I have seen dozens of routines posted on the Internet for generating uniformly distributed random numbers. Almost none of them worked. If you want 100 evenly distributed random integers 0..10 you would use JDK (Java Development Kit) 1.2+s Random.nextInt(int) to generate them:

Seeding

Don’t use two different generators with a null seed. The default seed is based on time of day and thus the two generators will then usually give identical streams of numbers.

To create a repeatable sequence seed with a constant, e.g. 149L. That will let you for example generate the exact same fake data for a benchmark over and over, or debug something that behaves predictable.

The best way to stay out of trouble into use new Random only once a program in a static init.

Random in the old Java version 1.1

Random between low and high bounds

import java.util.Random;
// ...
static Random wheel = new Random();
//...
// generate an int in range low..high inclusive.
int m = wheel.nextInt( high - low + 1 ) + low;

Random.nextBoolean

import java.util.Random;
// ...
static Random wheel = new Random();
// ...
// generating a boolean without nextBoolean to avoid the sticky bit problem.
boolean heads = ( wheel.nextInt() & (1 << 15) ) != 0;

Random.nextDouble

Random Strings

If the set of unique values is small, consider permuting the set of unique values e.g. 0..n and permuting/shuffling them, then just dealing them in order (without reshuffling), as you would to generate a card hand.

Normal Gaussian Distribution

Exotic Distributions

To compute a geometric distribution where n is the number you get from nextDouble.

The basic idea is you take some function of nextDouble after suitably scaling its range 0..1 e.g. sqrt or exp. Then you scale the result back into the range 0..1. Different functions will do different warpings.

For serious work, you will have to consult a probability and statistics text to see what the various distributions look like to simulate various natural processes. To get a distribution that fits some shape, you can try differentiating the shape either analytically or numerically, then inverting the function, exchanging the rôle s of x and y. Use that function to warp your outputs from nextDouble. To see what I mean, draw graphs of the various functions. You can see that flat areas of your warping curve tend to accumulate more random hits and sharp inclines and declines do not.

Unique Random Numbers

Playing Card Hands

If you need a shuffle for an array, see com.mindprod.common18.Shuffle.

Math.Random

SecureRandom

For a faster, higher quality random number generator try the Mersenne Twister.Java source and other languages are available. SecureRandom is extremely slow under Linux. If you need any quantity of high quality random numbers you will have to look outside the core Java classes.

Random Number Code to Avoid

Unfortunately, even if you do everything perfectly to use java.util.Random, the generator itself is flawed. It falls into the trap Knuth says to avoid — namely using a power of two for the modulus. The random numbers it generates are not all that random. It is blindingly obvious when you plot the low order bits of the random numbers visually.

Specifically, like all LCGs (Linear Congruential random number Generators) that use a power of two for the modulus, the lower-order bits of the generated sequence have a much shorter period than the sequence as a whole. Fortunately, this limitation is mitigated in the implementation of nextInt( int n ), which uses the high-order bits when n is a power of two.

Knuth gave me permission to translate his definitive random number generators into Java. Now all I need in the time and energy to tackle the task.

Using nextInt(int) for generating random integers is faster than using nextDouble, multiplying and converting to int as many authors suggest. In solving problems of this sort, you must be mindful that nextInt() (no parameter) returns a positive or negative integer, including MIN_VALUE (whose absolute value cannot be represented) and MAX_VALUE and that Java division/modulus has unexpected results for negative operands. You must also be careful to maintain even distribution. Consider the following code that also produces a random integer in the range 0 .. 10.

// bad way to generate random ints
import java.util.Random;
// ...
static Random wheel = new Random();
// ...
int m = wheel.nextInt() % 6 + 5; // not recommended!!

The following paragraph is controversial. Two experts disagreed on it. I have not taken the time to research it. In any case nextInt is faster than use nextDouble.

nextDouble() can return a 0.0, but never a 1.0. However, if you want a random number in the interval [0, N), taking the result returned by nextDouble() and multiplying by N will not always work; for some values of N, the final result can be N (the high bound). nextDouble() works by taking 53 random bits divided by (double) (1 << 53). So, the closest it can get to 1.0 is 0.99999999999999988897. When you multiply by a sufficiently large number, the tiny difference from 1.0 gets lost and the result is the same as if you had started with 1.0 not a number just less than 1.0. According to Merlin Hughes, any number that the generator produces will occur 32 times more commonly than for a perfect distribution; 31 of every 32 numbers just won’t ever be produced.

About every four days someone will post the following code as a way to generate a random integer 0 .. 10:

// bad way to generate random ints
import java.util.Random;
// ...
static Random wheel = new Random();
// ...
int m = (int)( Math.random() * 10.0d ); // not recommended!!

1. It will generate a number 0 to 9, not 0 to 10.
2. However, the technique in general may once in a blue moon generate 10. It won’t actually do this with 10, but it will hit the upper bound with larger ranges, so I think it wise to avoid the technique on general principles.
3. It requires two int <=> double floating point conversions and a floating point multiply. These are slow operations and completely unnecessary.
4. Math.Random gives you no power over the seed. It is hard to debug if your program behaves a totally different way every time you run it.

The Java random number generator does very poorly at generating the low order bit. It tends to repeat itself every 128 times you call nextInt(). It tends to get stuck for long runs of 0s or 1s, if you look only at every 128th result. In other words it is somewhat predictable. Bit 1 tends to repeat on a 256 cycle. The following code to generate simulate a heads or tail coin flip

// bad way to generate booleans
import java.util.Random;
// ...
static Random wheel = new Random();
// ...
boolean heads = ( wheel.nextInt() & 1 ) != 0; // not recommended!!

The following code works quickly to generate a random number between 0 and n, but the technique skews the results for large values of n, returning small numbers more frequently than it should. Instead use the nextInt(int) technique given above.

Random Enum

Here

// picking a random enum
static Random wheel = new Random();
...
// Fruit is an enum, possibleFruits an array of all possible Fruit constants
Fruit[] possibleFruits = Fruit.values();

// pick is a randomly selected enum constant
Fruit pick = possibleFruits[  Wheel.nextInt( possibleFruits.length ) ];

Random Daily Quotation

What if you want a random daily quotation to display on a web page chosen from a set of candidates, but you want the choice to remain stable, even if you recompute the choice. Here is how you could do that, without using java.util.Random at all.

Weighted Random Choices

Let us say you wanted a computer program to choose a random ice cream flavour to surprise you, but you wanted to have chocolate, strawberry and orange surprises more often. Here is how you could weight the random picks. In this case, the weights are integers.

Here is a slower technique that uses binarySearch. The advantage is you can use floating point weights which give you greater precision.

Books

Learning More