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.
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.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.
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.
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;
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.
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.
If you need a shuffle for an array, see com.mindprod.common18.Shuffle.
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.
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:
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.
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 ) ];
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.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.
This page is posted |
http://mindprod.com/jgloss/pseudorandom.html | |
Optional Replicator mirror
|
J:\mindprod\jgloss\pseudorandom.html | |
Please read the feedback from other visitors,
or send your own feedback about the site. Contact Roedy. Please feel free to link to this page without explicit permission. | ||
Canadian
Mind
Products
IP:[65.110.21.43] Your face IP:[3.236.112.101] |
| |
Feedback |
You are visitor number | |