To FootSee "About This JavaScript Site" in JavaScript Index and Introduction; and also Borland Pascal/Delphi Random.
Read the random.org site, and maybe java.util Class Random and Random Number Generators (RNGs) in the Scientific Computing and Numerical Analysis FAQ.
See also my Borland Pascal/Delphi Random Page, the considerations and methods of which are applicable in any language. It includes the generation of floats with specified distributions.
Note in particular : 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.
The random number generator is seeded from the current time (not a requirement of ISO 16262); I know of no way of giving it a specific initial value, for consistency in testing - no equivalent of Randomize or RandSeed in Pascal and Delphi.
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, ≤ & < respectively.
Netscape's Web site had "between 0 and 1"; but it seems that they mean, and implement, the same as above.
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+
A pseudo-random sequence generator is probably used. Such have a definite cycle length, which cannot be more than 2n for a generator with an n-bit seed. An n-bit generator most probably gives 2n equally-spaced values of X with 0≤X<1.
It looked as if, in MSIE 4, the number given had the full potential variability implied by an IEEE Double; in particular, that it was not quantised in units like 2-32, as elsewhere. That suggested that the sequence length, necessarily finite, exceeded 232 and may have been 264. Try evaluating
while ( (T = Math.random()) < 0.5 ) ; Z = ( T*Math.pow(2, 50) ) % 1 ;
a few times in JavaScript Demos and observe whether it gives all eight different results, as it did in my MSIE4. Tests using >= instead of < gave me more different results, which requires further thought.
For your browser :-
Since Numbers are IEEE Doubles, the resolution cannot exceed 53 bits. Resolution and cycle-length are semi-autonomous concepts. MSIE 6 and 7 show 53 bits; Firefox 2.0.0.3 shows 52 bits; Opera 9.21 shows 31 bits; Safari 3.1 shows 31 bits.
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 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.
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.
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.
This is a demonstration; 0 is a bad initialisation. The seed should be initialised with an arbitrary constant.
and as a function SeedRand (assign an arbitrary initial RandSeed, perhaps from new Date()) :-
I seek a 48-bit expression to give a longer sequence. See also in Borland Pascal/Delphi Random.
NOTE : I now suspect that there is loss of accuracy in the multiplication, likely to lead to loss of quality in the result. Either a suitable smaller constant, or a better multiplication, could be used.
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.
See also Borland Pascal/Delphi Random ff.
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.
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.
However, 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 batch, 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 chosen from five by Selettore2
at random, in a two-second test cycle.
Selections are independent, so repeats may occur ?
.