To FootSee "About This JavaScript Site" in JavaScript Index and Introduction.
In the generation of random numbers, shuffling, dealing, drawing, etc., all possible outcomes should have equal probability unless explicitly required otherwise.
Most work assumes that the underlying randomness generator does have this property. Normally, generators for computer languages have only a close approximation to the property. Some are worse than might reasonably be expected.
See also my Borland Pascal/Delphi Random, the considerations and methods of which are applicable in any language. It includes the generation of floats with specified distributions.
Function Math.random() should return an evenly-distributed real value X such that 0.0 ≤ X < 1.0 (ECMA 262, #15.8.2.14) - note, ≤ and <.
The random number generator is commonly seeded from the current time (that is not a requirement of ISO/IEC 16262). There is no equivalent of the Randomize or RandSeed in Pascal and Delphi. I know of no way of giving it a specific internal value, for consistency in testing - other than by calling Math.random() repeatedly until a particular sequence is obtained, which is not necessarily reliable.
Browser Math.random should not be used for crypto-grade work, nor for generating GUIDs; instead, see Higher Quality Generators below.
Opera (5.02..6.01 at least), I have read, could give a value of 1.0 from its Math.random(), with a frequency of the order of one in 35000 times - so that the function Random() below could return X. There is a Test Page by SC. Precautions were needed; appending %1 to Math.random() would do. LRN 20030804 : Opera 4, 5, not 6.05. Me : not 9.20+
Most computers do not have hardware to generate truly random bits at a reasonable speed.
Various sorts of pseudo-random number generator (PRNG) are known, and can be implemented in software. They have a definite cycle length, which cannot be more than 2N for a generator with an N-bit internal state.
A generator using N bits of state storage commonly, but not necessarily, has an internal state representing 2N different equally-spaced values. The internal values may be converted to values of output X with 0 ≤ X < 1, which should be equally-spaced and equally probable.
Most elegantly, a single call of a single PRNG would be used for each random number provided. Often, that is not so. Then, the period of the system and the number of different possible outputs are correspondingly reduced; and the possible output values may not be a uniform comb.
Commonly, too, the number of possible seeds is smaller than might be expected.
Since JavaScript Numbers are IEEE Doubles, the resolution of Math.random cannot exceed one part in 253 of value.
A generator with a 32-bit state can lead at best to 232 different Random values, at multiples of 2-32 from 0.0 up. A generator with a 64-bit state should normally have a copy of its state reduced to 53 bits before conversion to Double, to give 253 correspondingly-different values. But if converted without preliminary reduction, additional smaller values are likely to occur - it seems that Mac iCab may do that.
Note : Code changed 2008-07-27, 29; results now are one higher.
These take Count values of Math.random() within the range, and, treating each Double as its fixed-point equivalent, report the position of the smallest-value "1" bit seen.
Results show that some browsers give about 32 bits, some give about 53 bits, and about 64 bits is possible (Mac). Since a Double offers 53 bits, anything over 53 implies finer subdivisions of smaller values, which is untidy.
In my Windows, MSIE 7 shows exponent -54; Firefox 2.0.0.16 and 3.0.1 show -53; Opera 9.27 and 9.51 showed -32; Safari 3.1.1 showed -32, Safari 4.0 shows -30. Google Chrome 1.0 shows -30. Mac browsers are reported as showing similar results (Safari -31), except for iCab which shows -64.
In my Windows, MSIE 7 shows 53 bits; Firefox 2.0.0.16 and 3.0.1 showed 53; Opera 9.27 and 9.51 showed 32; Safari 3.1.1 showed 32, Safari 4.0 shows 30. Google Chrome 1.0 shows 30. Mac browsers are reported as showing similar results.
In IE7, but not in the others, range 2-1 to 2-0 shows 53, others show 54. Weird? Google Chrome 1.0 and Safari 4.0 show 30.
Turn off the browser's "looping warning" (if possible). I estimate that with a 1.7 GHz CPU, this test will run for half an hour, per repeat, in Opera and maybe not much longer in Safari, and for over a millennium in IE and Firefox. It took about three minutes in Chrome 0.2 (which seems to have a peculiar Math.random; ignore "Kill pages").
Opera 9.62 repeats after 2^31.
I estimate that with a 1.7 GHz CPU, this test will run for half an hour, per repeat, in Opera and maybe an hour and a quarter in Safari 3, a quarter of an hour in Safari 4, and for over a millennium in IE and Firefox. It took about three minutes in Chrome 0.2 (which seems to have a peculiar Math.random; ignore "Kill pages").
The actual sequence given by Math.random using such a generator depends on the generator algorithm and on the initial seed. The initial seed should itself be random; but there is generally no available source of true randomness.
It seems likely that the seed is generated from one of time-of-day, date-and-time, or count-since-boot; compare Borland Pascal/Delphi Random.
If time-of-day from the DOS clock at 0x40:0x6C is used in a Win9x system, then only 0x1800B0 initial seeds are possible; about 232/2730.
To get 253 different seeds during a single year, a clock of frequency no less than 9E15/3E7 ~ 3E8 Hz would be needed.
Note that where some form of scheduling is used, it is possible that the time of initialisation may vary only to a limited extent.
Unfortunately, read/write access to the seed is not provided in the language.
It appears that Math.random can be a security hole. See, via HTML Temporary user tracking in major browsers and Cross-domain information leakage and attacks, a 325kB PDF of the same title, by Amit Klein.
The paper gives considerable information on the internals of Math.random in major browsers.
For positive integer X, the following Random(X) should return an evenly-distributed integer value J such that 0 ≤ J ≤ (X-1); this is equivalent to the function Random(N) in other languages. There are then X equi-possible outcomes, so that the throwing of dice can be simulated with calls of (Random(6)+1). Note that the sequence is implementation-dependent.
Function Randum(X) will be slightly quicker.
There will be upper limits on for satisfactory results; but they will be large. The functions might also reasonably be used for non-integer X >= 1.0 but not for negative arguments.
Then function RanSpan(MinV, MaxV) should return a random integer within the integer range MinV to MaxV inclusive.
To generate a random three-letter word :-
To generate a random fixed-length numeric string :-
Using Math.round() in this context is usually incorrect, since the end values get half the probability of the others; but Math.round(Math.random()) does give 0 or 1, at random.
Using Math.ceil() in this context to avoid adding 1 is incorrect, since Math.random() can give 0.0.
For reproducibility, which is valuable in testing. the coder must be able to set the complete internal state of the generator. More background is in Borland Pascal/Delphi Random..
The Lehmer algorithm X = ((X * A) + C) modulo M is conceptually simple and adequate for common use. The sequence generated has detectable imperfections; the algorithm is not suitable for generating GUIDs or for cryptographic work.
Borland Pascal uses A = 134775813 = 0x08088405 ; C = 1 ; M = 232 Knuth has written that the following combination is excellent. A = 0x5851F42D4C957F2D ; C = 1 ; M = 264
NOTE : This 32-bit part contains demonstrations, not recommendations for general JavaScript use. But its best should beat the worst of my five browsers.
I have read that : Random implementation in Delphi (and Borland Pascal) is as follows: Pseudorandom longint sequence is implemented as a congruential generator with the formula X[n+1]=134775813*X[n] + 1 (mod 2^32). It can be shown that the sequence has full period (its length is 2^32). It is important that a well-chosen multiplier be used, in order to get a maximal-length sequence which passes most tests for randomness. See also in Borland Pascal/Delphi Random. I seek a 48-bit expression to give a longer sequence.
Note that Borland Pascal generates a DWORD RandSeed stored in a LongInt, which affects the relationship between RandSeed and Random.
Function Test32 is a demonstrator for functions Rand32A and Rand32B, which use the Borland expression. Except for test, zero is a bad initialisation. The global seed RandSeed should be initialised with an arbitrary constant, perhaps from new Date().
NOTE : There is loss of accuracy in the multiplication in function Rand32A() which leads to loss of quality in the result. A suitable smaller constant might be used. Alternatively, one can get exact results from "multi-word" arithmetic (cf. "Bit Representations of Number" in JavaScript Miscellany 0), as below.
(* This Borland Pascal 7 program should give the same sequence *)
var J : integer ; R : extended ; X : longint ;
begin Writeln ;
RandSeed := -1498392781 { precedes 0 } ;
J := -1 ;
repeat
X := RandSeed ;
R := Random ;
if R=0.0 then begin Writeln(X) ; J := 0 end ;
if J>=1 then Write(R:1:3, ',') ;
if J>=0 then J := J+1 ;
until J>11 ;
Writeln ;
end.
Gives :-
0.000,0.031,0.861,0.203,0.273,0.672,0.319,0.162,0.372,0.426,0.082,
The code does long arithmetic to base 65536 (216), without limitation of length. But the present demonstration function Init provides randomness no better than that of Math.random.
The functions require an argument of type Object. Its property Stat contains their state as an array of integers in which element J has a weight of 164×J. Array [0x0000, 0x0055, 0x0999, 0xDDDD] would represent unsigned 0xDDDD099900550000. On return, the Stat property will represent a new random integer X such that 0 ≤ X < M.
As Math.random does, they return an IEEE Double (a JavaScript Number). The generation of the Number from Stat remains to be optimised.
Function VastRand requires at each call an Object variable of value {Stat:X, Mult:A, More:C, Chop:log2(M)} which also provides the constants of the Lehmer expression. Property Chop is a small integer; properties Mult and More are arrays like Stat.
Function Rand64 works as VastRand but is simplified to use only a built-in 64-bit expression. It is to be provided at each call with an Object variable of value {Stat:X} which holds the state of the generator between calls. On return, the Stat property will represent a new random integer X such that 0 ≤ X < 264.
The above Lehmer generators, in particular Rand64, are in principle fairly comprehensible, fairly compact in core code, and can give results of moderate quality (better than some (2009) native Math.random). But much better ones are available.
The following partially demonstrates code from Johannes Baagøe :-
Within this page, the Objects are named Hasard in order to avoid a clash with the Random already used here.
NOTE : That demonstration code currently raises the entropy count for Random in an underhand, unsatisfactory, but convenient manner. Event Objects should be used instead of a Date Object.
NOTE : Routines baagoe.js & kiss2007.js are currently via Programs Index, until such time as a maintained source is found.
Example : to generate numbers chosen from 0..4, of equal probability except that 2 must be twice as likely as each of the others. For 60 numbers, the counts should be about 10,10,20,10,10.
The method can be adapted for the case of generating floats in a range according to a probability distribution function.
The above method will be slow if the distribution is very uneven. In that case, put the cumulative probability in an array, generate a random in 0..1, and scan the array for the first index exceeding it, returning that index. Beware rounding errors; the following test ensures that the final figure is 1.0.
To make it faster, the code could be reworked to use base 0x1000000 rather than 0x10000; the base must be less than the square root of the largest consecutive integer that the arithmetic operators support.
See also Borland Pascal/Delphi Random ff, and Ziggurat algorithm.
For this, the items will normally be held or placed in an array. In some cases, the array is 0..N-1; in others, 1..N.
Up to the date of writing this paragraph, I have given no thought whatsoever to the shuffling, dealing, or drawing of linked lists.
A satisfactory routine will, demonstrably, produce any of the possible results, with equal probability, in minimum time, using minimum code - on the assumption that it has the use of a perfect Random Number Generator.
One can generate new items in sequence; or one can start with an existing set, which it may or may not be permissible to rearrange.
Where a method uses an array for input and changes it, one may wish to work with a copy - note that one needs a new name and a copy of the structure, without necessarily duplicating the elements themselves.
One can, often conveniently, generate a set of numbers and use it to index into a supplied array of items, which is thereby preserved; there is then no need to copy the array, and it is clear that the elements are not copied.
One may need as the result the full set of possible items; or one may need a partial set, in which case the order may or may not matter. The case of a partial set should include those of empty and full sets, as testable limits.
Hence :-
Table entries link to functions given below; blanks are not needed :-
| Pick from a supplied array Q | Generate a set from 0..N-1 | |||||
|---|---|---|---|---|---|---|
| Destroy | Disturb | Preserve | ||||
| Full set | Shuffle(Q) | * | Deal(N) | |||
| Subset size M | Sequenced | . | PSS(Q, M) | * | # | |
| Unordered | Sparse | . | . | * | GSUS(M, N) | |
| Dense | . | . | * | GSUD(M, N) | ||
| Notes :-
*: Generate a set, and use it to index into Q #: Deal(N) ; use M entries in the final result. | ||||||
For uniformity, a definite amount of randomness is required; N! for a full shuffle or deal. A call of Random(N) generates randomness N and randomnesses combine multiplicatively. The amount of randomness generated must be an exact multiple of that required, and the number of calls of the function should be minimised. For more, see in Borland Pascal/Delphi Random.
To test uniformity, one can work with a small integer set 0..N-1 and consider the result as giving a base-N integer; use that as the index to increment in an array of counts, and inspect that array.
Here the result consists of all possible elements, in random order.
A perfect full shuffle or deal introduces complete randomness; no trace of the original order is left. For N items, there is one chance in N! of ending up with the original order.
There are N! possible orders for N numbers; therefore, for a perfect efficient full shuffle or deal, exactly N! of randomness is needed. This is obtained by calling Random(N) to Random(1) or Random(2) in some order.
The following matches that given by Knuth - see in Pascal Random. It is the Fisher-Yates shuffle, as implemented by Durstenfeld. It is an in-place shuffle.
The result grows from the right. For each loop, a value randomly chosen from those left is exchanged with that at the current end position, and kept.
The following may be considered a more elegant implementation of the same algorithm; with a PII/300 & MSIE4, it was only slightly slower :-
Array.prototype.Swap = function(j, k) {
var T = this[j] ; this[j] = this[k] ; this[k] = T }
function shuffle(Q) {
for (var J=Q.length-1 ; J>0 ; J--) Q.Swap(J, Random(J+1)) }
To shuffle multiple sets of data, maintaining correspondence between items. Two approaches :-
1. Create a new array of objects (or of arrays) in which each object (or array) contains the corresponding elements of the original arrays. So AoO[1] is {k:key1, v:value1} (or AoA[1] is [key1, value1]) etc. Now shuffle the array of objects, then either read the items out into separate arrays or use them as they are. It seems generally better to design on that basis.
2. Use a function like Shuffle above, but modified to take several array arguments (or an array of array arguments) and to have an outer loop which exchanges elements in the same manner in every array.
The following, mentioned by Jim Ley, may be the shortest and most amusing shuffle :-
function Shuffel(Q) {
return Q.sort(new Function("return 0.5-Math.random()")) }
// or
return Q.sort(function(){return Math.random() < 0.5 ? -1 : 1}) }
// or
function fn() { return 0.5-Math.random() }
function Shuffell(Q) { return Q.sort(fn) }
Testing the first of those with MSIE 4 in my Evaluate box, it was about 2/3 the length and 2/3 the speed of my Shuffle(Q); the results looked random, but may have depended crucially on the sort algorithm used. Later tests in MSIE 8 have shown significant bias, not matched in two other browsers.
The standards require a comparison function to give consistent results. Actual use cannot be recommended.
An array of numbers in random order can be generated by dealing directly; it is not necessary first to generate the array in systematic order and then shuffle it.
The result grows from the left. For each loop, the new number J displaces a number from randomly chosen position K to the new end position, or goes to the end itself. To deal items other than integers, replace Q[K] = J by assignment of an item.
The function Shuffle(Q) shown in the section above places entries in turn on the right, each fully random from those remaining on the left. Therefore a partial shuffle will generate a random subset of entries, followed by the result of a Draw.
The Deal shown above generates new entries in numerical order, positioning them at random. Therefore a partial Deal is not merely a good Deal of fewer values.
Proper randomness is obtained by calling Random(N) to Random(N-M+1) in some order.
See Drawing in my Borland Pascal/Delphi Random.
If the order of the result matters, repeatedly pick an element at random from those as yet unchosen and swap it with the end unchosen one, ...; after enough selections, the required result will be at the end.
but note that parameter Q is partly shuffled.
For drawing a few items at random from a large collection, there is no need to deal or shuffle the entire set, and there is no significance in the order; the following are derived from my Borland Pascal/Delphi Random.
Translating from Pascal gives
function GenerateSubsetUnorderedSparse1(M, N) {
var J, K, Q = new Array(N)
for ( K = 0 ; K<N ; K++ ) { Q[K] = false }
for ( K = N-M ; K<N ; K++ ) {
J = Random(K+1) ;
Q[J] ? Q[K] = true : Q[J] = true }
return Q } // undertested
which generates an array (0..N-1) containing true for M randomly chosen elements (after Rufus V Smith). One can use this array to pick data from another array.
It further gives
function GenerateSubsetUnorderedSparse2(M, N) {
var J, K, Q = new Array(N)
for ( K = N-M ; K<N ; K++ ) {
J = Random(K+1) ;
typeof Q[J] == "undefined" ? Q[J] = J : Q[K] = K }
return Q } // undertested
or
which generates a sparse array (0..N-1) containing M randomly chosen elements.
Change the last line of the Sparse functions to be
return Q.join('x').split(/x+/) } // undertested
and the sparse array is compacted to length M; there may be better ways.
The elements of a sparse array can be accessed efficiently, but probably in order of creation, with
for (El in Arr) { ... ... }
I've seen the following in News :-
Or, generating a compact result directly,
Before sorting, I suspect that the order of B is only partly random.
Translating code from my Borland Pascal/Delphi Random into similar JavaScript gave a function returning an array of length ≤ N in which M elements exist at random positions indexed 1..N - which corresponds to Pascal/Delphi set notation. A minor change then made the element at position K, if present, be of value K. One needs then only to strip the undefined elements.
Answer = GenerateRandomSet(m, n) // then compactify Answer
NOTES :-
1. The translation needs to be checked
2. The JavaScript needs to be tested more
3. Recursion may not be quickest; convert to iterate?
4. How best to compactify, all-compatibly?
5. The result is automatically in order
6. If the selection is sparse,
for (j in Q) Ans[k++] = Q[j] ; Ans.sort() ; may be faster.
That is in fact a recursive form of GenerateSubsetUnorderedSparse2(M, N).
This is modified from code posted in news:c.l.j by "rh".
NOTES :- 1. The JavaScript needs to be tested more 2. The result is automatically in order
That is probably a form of GenerateSubsetUnorderedSparse3(M, N).
Further modified.
NOTES :- 1. The JavaScript needs to be tested more 2. The result is neither in order, nor in random order
The result is a true Set; .sort() can be used.
Not efficient for full selection.
NOTES :- 1. The JavaScript needs to be tested more 2. The result is in random order
For the generation of a chosen distribution (e.g. a Gaussian), see my Borland Pascal/Delphi Random.
The above methods all use the minimum number of calls of Random(). a slight increase in speed might be obtained by in-lining Math.random or by assigning Mr = Math.random or other such changes. But the only good way to determine or optimise speed requires measuring it, preferably with every browser.
To see the code, use View Source.
Note that time is quantised in units of maybe 50/60ms or 16 ms or 10ms or ..., depending on system.
For a presentation of indefinite length, consider what randomising the order of showing of slides should mean. Normally, the result should be perceived as random. Some care may be needed; for example, a slide should not be repeated too soon, or unshown for too long.
For N slides, there are two limiting cases, A & B :-
A) The slides are chosen at random, independently of what went before. Each time, the chances of a repeat of the previous slide are 1 in N; and the chances of a repeat, in each N slides, must exceed 50%.
B) The slides are given, once and for all, a random order; and that order is repeatedly cycled through. Slide X is either always or never followed by slide Y. Slides repeat after N intervals.
Then there's
C) Repeatedly, all of the slides are shown in random order. There's then a 1 in N chance of a repeat at the end of each group, and about a 2 in N chance of a slide being repeated with a single other one in between.
Now consider
D) Deal, once and for all, the set of N slide-numbers into an array. Then, repeatedly, select at random one of the first M entries; show it; and move its entry to the end of the array, allowing other entries to move forwards.
If M = N, we have Case A behaviour.
If M = 1, we have Case B behaviour.
If M = N-K, repeats of a slide occur at intervals containing at
least K other slides.
But, as in Case A but not in Cases B & C, there is no upper limit on the interval between showings of a given slide. It is possible (if Random is perfectly random, which it is not), for an unlucky slide never to be shown.
These functions are for test. In practice, Deal would be called at start-up and the body of the J loop (with A.push replaced by Display) could be included in a function called by setInterval.
Is there a simple elegant method including the advantage of Case D but fixing the defect?
Of course, one could maintain for each slide a count of time since it had been selected, and select the first entry if its count exceeded N+K, treating it as if it had been chosen randomly as before. But I see no way of avoiding a loop through all N incrementing an object element for each.
I'm not quite sure that the algorithm described verbally is ideal, nor that its implementation in ShowE is good.
Two different images (of digits) are chosen from five by
Selettore2 at random, in a one-second test cycle.
Selections are independent, so repeats may occur ?
.