pseudo-random numbers : Java Glossary

*0-9ABCDEFGHIJKLMNOPQRSTUVWXYZ (all)

pseudo-random numbers

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.

int Math.Random
Seeding SecureRandom
Java 1.1 Bad Code
low and high bounds UUID
boolean Random Enum
double Random Daily Quotation
Random Strings Weighted Random Choices
Gaussian Books
Distributions Learning More
Unique Links
Playing Cards

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:

Note, nextInt generates numbers 0 .. n-1, not 0 .. n.
As a general rule, almost any random generator code you come up with you think should work will fail in some corner case. It is very difficult to debug random number generator code. You can’t tell easily if it is working properly. So I have two pieces of advice:
  1. Always use the highest level tools available to you to solve a given problem with the JDK.
  2. Keep reading so you will appreciate just how dicey random number generation is.

Seeding

Seed the random number generator only once. If you keep restarting it (by doing new Random() more than once) using the system time default or some chosen seed, your numbers are not going to be very random. Since the clock does not tick over all that fast you may even create generators with identical default seeds, which then generate identical streams of numbers.

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

If you have Java version 1.1, which does not support nextInt(int), you can extend the Random class with the following code for nextInt stolen from Java version 1.2. Random.next(bits) that cleverly selects the high order bits of the seed, which are more random. When n is a power of two, this code selects the high order bits of 31 selected bits. When n is not a power of two, it uses the less random low order

Random between low and high bounds

To get an evenly distributed random number between integers low and high inclusive use:
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;
Be aware that  Random.nextInt ( n ) gives a number between 0 and n-1 inclusive, not 0 to n. Random. nextDouble() returns a number between 0.0 inclusive and 1.0 exclusive.

Random.nextBoolean

To simulate throwing a coin, generating a Boolean, use Random.nextBoolean. If you are using  Java version 1.1 which does not support nextBoolean, you can use the following code which bypasses the sticky low-bit problem with nextInt(). You can avoid the sticky low order bits by picking a bit out of the middle of the result this way:
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

If you wanted a random double between 0.0 and 10.0 here is how you would generate it.

Random Strings

Sometimes you want a random String to use as an almost unique identifier. You could use  But what about collisions? How likely are you to run into problems with uniqueness? In most cases it is highly unlikely you will get duplicates even though Oracle’s generator generates many more collisions than a theoretically perfect true random number generator. Internally Oracle’s nextLong uses only a 32-bit generator and it does not cycle through all possible 32-bit patterns. I have written code to compute the theoretical possibility of a collision with a perfect true number generator and a simulator that exercises Oracle’s generator and tracks how well it performs. Here is the code:

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

If you want your random numbers to lie on a bell shaped normal curve, use java.util.Random. nextGaussian, which produces numbers with mean 0.0 and standard deviation 1.0.

Exotic Distributions

If you want more exotic distributions, e.g. Poisson, Skewed Gamma or Lognormal have a look at the source code for java.util.Random. nextGaussian and use the same technique to warp the nextDouble uniform distribution, or read Donald Knuth’s Art of Computer Programming which is the reference works for standard algorithms. In particular you want volume 2, Seminumerical Algorithms. If you just want to play around, have a look how java.util. nextGaussian works. You can warp the output n of nextGaussian to have a different mean μ and a different standard deviation σ with a simple formula:
n′ = ( n * σ ) + μ;

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

n′ = ceil(ln n / ln (1 - p));
Precompute ln ( 1 - p ); Use Java’s Math. log to compute ln — the natural logarithm.

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

What if you need unique random integers? Generate them in the ordinary way with nextInt(int). Tick them off as used in a java.util.BitSet. Discard any that are already in use. If that BitSet would be too huge and you only need to generate a few random numbers, wrap them in Integers and store them in a HashSet.

Playing Card Hands

When you are trying to simulate playing card hands, you can create an ArrayList of Integers 0 .. n-1, (or Card objects) and use Collections.shuffle. Then just peel the cards off the bottom or top of the ArrayList.
Note that even though the method is called Collections. shuffle, it does not work on arbitrary Collections, just Lists. It could not very well work on Collections, since they have no ordering to shuffle. I think it should have been called Lists. shuffle.

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

Math.Random

Math.Random is an alternate method to create random doubles that does not require you to create a Random object, but it does not give you control over the seed and has no nextInt(int) or nextBoolean. Other than that, it has the same shortcomings as java.util.Random.

SecureRandom

If you need very high quality random numbers for cryptography, see java.security. SecureRandom. Since it is derived from java.util.Random, it works much the same way. The main difference is the way you construct the wheel: Unfortunately, early versions of Netscape do not include any of the java.security classes. For ordinary use, use java.util.Random.

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!!
However, that code would generate 5 twice as frequently as the other values.

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!!
There are four things wrong with the technique:
  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.

I use the code above in my Static Macros package to every half hour change quotations at the top and bottom of pages such as the mindprod.com home page, The Java Glossary home page, The Computer Buyers’ Glossary home page, The Gay Glossary home page, The Environment page, The Politics page, The Religion page, The Ethics page, The Living Love page. I also use it to slowly rotate the PSAs (Public Service Advertisements) at the bottom of pages, every couple of months, a few randomly selected to change each day.

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

Oracle’s Javadoc on java.util.Random class : available:
Oracle’s Javadoc on SecureRandom class : available:
Oracle’s Javadoc on UUID class : available:
Oracle’s Javadoc on Collections.shuffle : available:
Oracle’s Javadoc on Random.nextInt : available:
Oracle’s Javadoc on Random.nextLong : available:
combination
ISSAC: fast cryptographic random number generator
Mersenne Twister: theory
modulus
permutation
shuffle
true random numbers
Uncommon Maths: a library of random number generators
unique numbers
UUID

This page is posted
on the web at:

http://mindprod.com/jgloss/pseudorandom.html

Optional Replicator mirror
of mindprod.com
on local hard disk J:

J:\mindprod\jgloss\pseudorandom.html
Canadian Mind Products
Please the feedback from other visitors, or your own feedback about the site.
Contact Roedy. Please feel free to link to this page without explicit permission.

IP:[65.110.21.43]
Your face IP:[3.236.112.101]
You are visitor number