14.2 Uniformly Distributed Random Numbers

   

 
Java Number Cruncher: The Java Programmer's Guide to Numerical Computing
By Ronald  Mak

Table of Contents
Chapter  14.   Generating Random Numbers

14.2 Uniformly Distributed Random Numbers

The most straightforward random numbers to generate are ones that are uniformly distributed between a minimum value and a maximum value. Each value has an equal probability of being anywhere within that range.

A very popular algorithm for generating uniformly distributed random values is the linear congruential algorithm. This algorithm generates random integer values that range over all the possible positive and negative values of the integer type. It uses the formula

graphics/14equ01.gif


where the x i are the generated random values, m is a constant multiplier , a is a constant addend, and d is a constant divisor. A seed value kicks off the sequence. The formula relies on the fact that integer arithmetic does not overflow but wraps around. (See Chapter 2.)

The trick is to find the right constants m, a, and d such that the random x values have a long period. The period cannot have more than d different values, and so we want a large value for d. To make the random number generator fast, we can choose d to be 1 less than a power of 2 (and so its binary representation is a string of 1 bits), and then we can perform the modulo operation with a logical and operation using the value of d as the mask. We should also choose values of m and d that are relatively prime (they have no factors in common).

In the standard class java.util.Random , method nextInt() uses the linear congruential algorithm with the constant values m = 25,214,903,917, a = 11, and d = 281,474,976,710,655 (= 2 48 -1).

An algorithm that produces uniformly distributed random integer values can be the basis of other random number generators. For example, method java.util.Random.nextFloat() returns a uniformly distributed random float value between 0 and 1 by first generating a random positive 24-bit integer value and then dividing that value by 2 24 . Uniformly distributed random values can also be used to generate random values with other distributions, as we'll see in the following sections.


   
Top
 


Java Number Cruncher. The Java Programmer's Guide to Numerical Computing
Java Number Cruncher: The Java Programmers Guide to Numerical Computing
ISBN: 0130460419
EAN: 2147483647
Year: 2001
Pages: 141
Authors: Ronald Mak

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net