- A random number generator (RNG) is a function which returns a different number each time it is called.
- The sequence of numbers should be distributed uniformly across their range. (Other statistical distrubutions my be required occasionally.)
- There should be no noticable relation between the previous numbers and the next ones generated.

- They cover their range quite uniformly.
- They exhibit very little serial correlation.
- They do not repeat for a very long time.

- Starting from a given state, any purely mathematical algorithm will produce the same sequence.
- Technically they are
*deterministic*and hence*pseudo-*random number generators (PRNGs). - They should not be used when, say, money is involved.
- For true random numbers, special hardware is available that uses physical processes such as thermal noise.
- Unix-like systems offer
`/dev/random`

, which "gathers environmental noise from device drivers and other sources into an entropy pool." But it can be slow or stall while waiting for new noise. - Since neither the hardware nor
`/dev/random`

are sure to be present on client computers, we will confine our attention to PRNGs. - When a true RNG or a better PRNG is needed, it will need to be provided by a server.
- I will just say "RNG" from now on.

- When a RNG starts, it needs to be given an initial state.
- Usually this is a number called the "seed".
- Any given seed will result in the same sequence.
- The ability to set the seed is useful:
- If a bug depends on the random sequence generated, being able to reproduce it is priceless.
- Each hand in, say, FreeCell can automatically be indentified and recreated, allowing replay.

- But otherwise each time we play we want a different seed.
- Unless a true random source is available, a common choice for the seed is the time in, say, milliseconds. JavaScript provides this as
`new Date().getTime()`

.

`Math.random()`

generates floating-point (real) numbers between 0.0 (inclusive) and 1.0 (exclusive).- Often we want integers. To get an integer r with 0 <= r < N, use

`Math.floor( Math.random() * N )`

- To get r with M <= r < N, use

`Math.floor( Math.random() * (N - M) ) + M`

- There is no way to set the seed for this generator. It is probably set when the browser starts up, probably using the time.

- A fast, simple, and very common RNG produces the next number, X
_{n+1}using

X_{n+1}= (aX_{n}+ c) mod m,

where a, c, and m are constants chosen with care. - Since we always have 0 <= X
_{n}< m, m is usually chosen to be a large integer, often 2^{32}or even 2^{64}, depending on what the computer supports.

JavaScript's support for integers is complicated, but 2^{48}works. - The multiplier, a, must be chosen very carefully. 31167285 turns out to be a good value.
- The value of c is not as critical. It mustn't be 0, but 1 is fine (as in fact most odd numbers would be here).
- Another, easy-to-remember, LCG: m = 2
^{32}, a = 69069, c = 1 - In most languages mod 2
^{n}is an easy bit-wise`and`

(or truncation at the word size). Not in JavaScript, unfortunately.

app.lcRandom = (function() { //------------------------------------------------------------------------- var seed, m = 0x1000000000000, //2^48 sqrtM = 0x1000000, a = 31167285, c = 1, x; //========================================================================= function reseed( newSeed ) { if ( newSeed === undefined ) { newSeed = app.stdRandom.integer( m ); } x = seed = newSeed; } //------------------------------------------------------------------------- function getSeed( ) { return seed; } //========================================================================= function real( ) { return integer( m ) / m; } //------------------------------------------------------------------------- function integer( limit ) { if ( seed === undefined ) { reseed( ); } x = ( a * x + c ) % m; if ( limit < sqrtM ) //When possible, just use the return (x / sqrtM) % limit; // higher-order bits. else return x % limit; } //========================================================================= return { reseed: reseed, getSeed: getSeed, real: real, integer: integer }; //------------------------------------------------------------------------- } )();

- Built-in method may be faster, use more bits, and use a better algorithm. (It can use bit-wise operations and techniques not available in JavaScript.)
- Historically, library RNGs have sometimes been notoriously poor, though that is probably a thing of the past.
- As noted above, the ability to set the seed can be valuable.

You can randomly reorder a list like this:

app.shuffleArray = function( array, random ) { var rng = random || app.shRandom, len = array.length, i, r, tmp; for ( i = len - 1; i > 0; --i ) { r = rng.integer( i + 1 ); if ( r !== i ) { tmp = array[ i ]; array[ i ] = array[ r ]; array[ r ] = tmp; } } };

- Donald E. Knuth,
*The Art of Computer Programming, Volume 2: Seminumerical Algorithms*, 1997 Addison-Wesley (ISBN 978-0201896848) - William H. Press, et al.,
*Numerical Recipes: The Art of Scientific Computing*, 2007 Cambridge University Press (ISBN 978-0521880688)