To FootSee "About This JavaScript Site" in JavaScript Index and Introduction.
For both this page and JavaScript Shuffle, Deal, Draw :-
See also my Borland Pascal/Delphi Random, the general considerations and methods of which are applicable in any language.
In the production of random numbers, shuffling, dealing, drawing, etc., all possible outcomes should have equal probability unless explicitly required otherwise. Also, there should be no significant correlations between the values or bit patterns in the sequence of numbers produced; that is harder to test.
Most work assumes that the underlying randomness generator does have those properties. Normally, generators for computer languages have only a close approximation to them. Generators which are worse than might reasonably be expected have been detected in some Web browsers.
Most computers do not have hardware to produce 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 (but not necessarily known) cycle length, which cannot be more than 2N for a generator with an N-bit internal state. But N can easily be in the hundreds. A simple generator using N bits of state storage commonly, but not necessarily, has an internal state representing 2N different equally-spaced values. The number of different output values cannot be more, and can easily be less, than the number of internal states.
The internal values may be converted to values of output X such that 0.0 ≤ X < 1.0 (as required for Math.random), which should all 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 initialisations (seeds) is smaller than might be expected.
For the best work, the cycle length of the generator and the number of values used in a cycle of the application should have few small common factors – ideally, they would be co-prime.
Almost anything will do for adding a little variety to a Web page, or for simple amusements. Better is needed, for example, for security, for Monte Carlo method applications or for generating GUIDs; and better still for cryptography-related work.
Function Math.random() should return an evenly-distributed Number X such that 0.0 ≤ X < 1.0 (ECMA 262 5th Edition) - note, ≤ and <.
That is best fulfilled if the possible values are everywhere exactly equally spaced and are as numerous as possible – K/2N for all 0 ≤ K < N – and the sequence of the values is in all respects highly disordered. Since JavaScript Numbers are IEEE Doubles, the resolution of Math.random cannot exceed one part in 253 of value : N ≤ 53. Some current (2010) browsers are not that good.
A generator with a 32-bit state can lead at best to 232 different Random values, which should be 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, many additional smaller values are likely to occur - it seems that Mac iCab may have done that.
The random number generator of Math.random() is commonly seeded from the current time (that is not a requirement of ECMA 262). There is no JavaScript equivalent of the Randomize or RandSeed of Pascal and Delphi. I know of no way of giving it a specific internal value, for consistency in testing - other than by calling repeatedly until a particular sequence is obtained, which is not necessarily practicable or reliable.
The present (2010) browser functions Math.random, and the demonstration functions coded below, should not be used for anything approaching crypto-grade work, or for generating GUIDs. Instead, see Better Pseudo-Random Number Functions below.
Math.random() in Opera (5.02..6.01 at least), I have read, could give a value of 1.0, with a frequency of the order of one in 35000 times - so that the function Random() below could return X. Precautions were needed; appending %1 to Math.random() would do. LRN 20030804 : Opera 4, 5, not 6.05. Me : not 9.20+. As a sideline, the more general "Test Resolution 1" below supersedes the code which was here.
The actual sequence given by Math.random depends on its algorithm and on the initialisation. The initialisation should itself be random; but there is generally no available source of true randomness.
Initialisation could occur at system boot, at browser load, at window creation, at tab creation, at frame creation, or perhaps otherwise. This has security implications.
It has seemed likely that a seed was obtained from one of time-of-day, date-and-time, or count-since-boot; compare Borland Pascal/Delphi Random. Modern Intel CPUs provide nore counts to choose from.
If time-of-day from the apparent DOS clock at 0x40:0x6C is used, then only 0x1800B0 (1573040) 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. Nowadays, a CPU clock is fast enough; but, in a PC, it counts from boot.
Note that where some form of program scheduling is used, it is possible that the time of initialisation may vary only to a limited extent.
Unfortunately, read/write access to the internal state is not provided in the language.
It appears that Math.random can be a security hole. If the generator state is not re-randomised in between, it can be possible for one page or frame to preset the state which another will receive. With a weak Math.random, it can be possible to track a user from one site to another, or to identify a return visit. Browser-generated GUIDs can be a danger.
See, via HTML Temporary user tracking in major browsers and Cross-domain information leakage and attacks and "download paper", a 325kB PDF of the same title, by Amit Klein. The paper gives considerable information on the internals of Math.random in major browsers.
Relevant pages on that site include :-
* Temporary user tracking in major browsers and Cross-domain information leakage and attacks - a MUST READ page
* Google Chrome 3.0 (Beta) Math.random vulnerability,
* Google Chrome 6.0 and above Math.random vulnerability,
* Cross-domain information leakage and Temporary user tracking attacks in Apple Safari 4.02-4.0.5 and Apple Safari 5.0-5.0.2 (Windows),
* Detecting virtualization over the web with IE9 (platform preview) and Semi-permanent computer fingerprinting and user tracking in IE9 (platform preview)
* and via Trusteer Publications.
The crypto element is not in the ECMA 5 standard. Firefox has apparently inherited it from Netscape; my other browsers (2010-11-29) do not have it. Firefox 3.6.12 can enumerate properties of crypto†, including crypto.random. The call crypto.random(N) would give a random N-byte string; but in Firefox 3.6.12 it gives me an "uncaught exception".
See JavaScript crypto, Miscellaneous, for a partial explanation.
† disableRightClick enableSmartCardEvents generateCRMFRequest importUserCertificates logout popChallengeResponse random signText version
For reproducibility, which is valuable in testing. the coder must be able to set the complete internal state of the function. More background is in Borland Pascal/Delphi Random..
Lehmer's Linear Congruential Generator X = ((X * A) + C) modulo M is conceptually simple and adequate for low-grade common use. The sequence generated has detectable imperfections. The algorithm is not suitable for generating GUIDs or for cryptographic work, and can be used for tracking.
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
Other algorithms could replace Lehmer's in adjusted versions of the routines provided below.
NOTE : This 32-bit part contains demonstrations, not recommendations for general JavaScript use. But its best may beat the worst (May 2010) 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 Rand32Rough and Rand32Exact, which use the Borland expression. Except for test, zero is a bad initialisation. For normal use, the internal state function.uint32, corresponding to Borland RandSeed, should be initialised with an arbitrary constant, perhaps from new Date().
NOTE : There is loss of accuracy in the multiplication in function Rand32Rough() 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 Exact Arithmetic), 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 functions use the Lehmer algorithm. The present demonstration function InitQuads provides randomness no better than that of consecutive calls of Math.random.
A long integer is represented by an array of Numbers ("digits") each of integer value in the range 0 to 65535 (216-1). Element J has a weight of 164×J. Array [0x0001, 0x0055, 0x0999, 0xDDDD] would represent unsigned 0xDDDD099900550001.
The code can do long arithmetic to base 65536 (216), without limitation of length.
The functions require a property including their state as such an array. On return, the array 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 the array remains to be optimised.
The code does long arithmetic without limitation of length. The test uses 64 bits, since that is the largest size for which I have seen recommended constants.
The internal state is held in an Object of value {Stat:X, Mult:A, More:C, Chop:log2(M)} which also provides the Lehmer constants. Property Chop is a small integer; properties Mult and More are arrays like Stat.
Function VastRandFnc is given the State Object as a property; an argument or a global variable could be used instead.
The code does long arithmetic with four "digits".
This works as VastRand but is simplified to use only a built-in 64-bit expression. The X is held between calls as State, an Array property of the function. On function return, the property will represent a new random integer X such that 0 ≤ X < 264.
An argument or a global variable could be used instead of the Array property.
The above Lehmer algorithms, in particular Random64Fnc, are in principle fairly comprehensible, fairly compact in core code, and can give results of moderate quality (better than some [2010] native Math.random). But much better algorithms are available.
Johannes Baagøe has a page Better random numbers for javascript, providing a set of Ancestor functions each of which returns a quality substitute for the default function Math.random. A returned function is initialised from the arguments of its Ancestor, or by default from +new Date().
This page now supports Ancestor functions compatible with Baagøe's version 0.9 only
His main Ancestor functions require an ancestral function Mash, his code for which I have copied into this page. RSVP if it needs updating.
A new Mash can be inserted using this box. OMIT any leading var :-
His version 0.9+ Ancestor functions can be pasted into the box in the section "Select a Function" below. Initialisation of the child functions is now handled by my code.
This can test any of :-
Note that these are simple tests, the results applying to the set of values so far tested without reference to their order except when testing repeat intervals. Functions should also be tested for subtle patterns in the sequence of results, which is harder.
Remember to use the Select button after altering any of the settings.
Initialisation now works wherever possible. It cannot work on ECMA-262 3/5 Math.random.
A line Init(+), if present, shows whether further generated functions have independent state variables. If it matches the Init(1) lines, they are independent.
Variables appearing to be global in the "Pop Func" box are not necessarily really so.
This supersedes previous code using ResolA ResolB ResolC. It shows that different browsers have substantially different Math.random methods, and that at least some are poor.
It gives, for each range 2-J×(2-ε) to 2-J of Math.random(), the value of the smallest "1" bit so far seen in that range. Note that as the ranges get smaller more tests are needed (on average) to hit them.
Math.random : results above the gap were deduced from earlier code MS IE 7 1 53, 2 54, 3 54, 4 54, ... Opera 9.51 1 32, 2 32, 3 32, 4 32, ... Safari 3.11 1 32, 2 32, 3 32, 4 32, ... Chrome 1.0 1 30, 2 30, 3 30, 4 30, ... reported for Mac : Safari 31, iCab 64 ---- MS IE 8 1 53, 2 54, 3 54, 4 54, 5 54, 6 54, ... Firefox 3.6.13 1 53, 2 53, 3 53, 4 53, 5 53, 6 53, ... Opera 10.63 1 53, 2 53, 3 53, 4 53, 5 53, 6 53, ... Safari 5.0.3 1 32, 2 32, 3 32, 4 32, 5 32, 6 32, ... Chrome 5.0 1 30, 2 30, 3 30, 4 30, 5 30, 6 30, ... Chrome 7.0 1 32, 2 32, 3 32, 4 32, 5 32, 6 32, ...
Results show that some browsers give or have given about 32 bits, some about 53 bits, and about 64 bits is possible (Mac). Since an IEEE Double offers 53 bits, anything over 53 implies finer subdivisions of smaller values, which is untidy.
Reasons for at least some of the results can be seen in Temporary user tracking in major browsers and Cross-domain information leakage and attacks.
The following form shows a browser-dependent pattern of counts of "1" bits obtained from Count values of the selected function.
The value of the function is here considered as a leading-point binary fraction in which bit N represents 2-N, so that the MSB position is bit 1 and the LSB position ought to be bit 53. The "BIT N" row or column is for all values of the function not less than 2-N and not dealt with in earlier lines. The last "bin" is therefore as wide as the one before it. "Par" shows the proper mean value for all bits after the first "1" (which is double that). Count positions marked '-' are impossible.
For Math.random(), MS IE 8 shows '1' bits to bit53, and for bit54 except for when BIT 1 is set (random value ≥ 0.5). Firefox and Opera are good, with '1' bits to bit53. Safari and Chrome show '1' bits to bit32. (2010-12-09, current browser releases.)
The random value is as a fixed-point binary fraction (integers are normalised to that).
Note : this tests one aspect of distribution, not randomness as such.
The random value is considered as a fixed-point binary fraction (integers are normalised to that). Bit number J is then worth 2-J. Bit values are 0 or 1.
Tail values are the values of "'that bit' binary-point 'the rest'". Tail values have 0.5 LSB added, in order to make the ideal value 1.0 throughout.
Note : this shows one aspect of distribution, not randomness as such.
This reports repeat intervals for a random initial value. Note that the code can run for ever, seeking all repeats of that initial value.
For a function returning the maximum possible number of values which are evenly-spaced, non-negative, and less than one, because the result is a Number (an IEEE Double), the average repeat interval must be 253 = 0x20000000000000 (Hex 0020 0000 0000 0000).
For Math.random the test speed will be of the order of a million tries per second, on a P4/3GHz PC. In MSIE 8 and Opera 10, each repeat could well take very many years. Firefox 3 is expected to repeat after about 4 years. Safari 4 and Chrome 4 repeated after several to many minutes. Other functions will generally be slower.
For Math.random :-
To see whether a PRNG has been correctly implemented, one can call it many times and then check a few consecutive values against those of a known-good version. This requires the generator to be initialised.
If the name of a property of the function being tested is given, then the .toString() of that property will currently be reported. Probably it will be necessary to allow a user-provided function to write the properties, since different generators will hold different properties. By default, the State property is reported correctly for Rand32Rough Rand32Exact Random64Fnc.
A Random function often has a primary result of its PRNG among its properties as a 32- or 64-bit random integer.
After 1e6 calls, return : Math.random No Initialisation Code box Glob 0x0.b614 0x0.37b41 0x0.21c8a XYZ 0.9+ Glob ? ? ? Rand32Rough 0x0.b60a19 0x0.8b167d 0x0.37e471 Rand32Exact 0x0.aea805c 0x0.3a3f1cc1 0x0.9c1713c6 VastRandFnc 0x0.8fbf63adba86 0x0.50230d10438e08 0x0.afc14169fdef7 Random64Fnc 0x0.8fbf63adba86 0x0.50230d10438e08 0x0.afc14169fdef7 Alea 0.9 0x0.7eab667d 0x0.4b90ac34 0x0.d5ce952c Kybos 0.9 0x0.adaea994 0x0.32daa8c2 0x0.58676b8
Repeatedly averaging several Batches each taking seconds is needed for a good result. Use Dummy() to measure tining overhead.
Note that the timing accuracy may be impaired by necessary flexibility in the script. For best results, test specific methods yourself.
If, for example, two smaller-range random numbers are added to give a full 53-bit value, care should be taken to ensure that no rounding up occurs. That fault may occur very infrequently, and might not be seen in moderate testing.
If, for example, two 32-bit Math.random fractions are combined to give a full 53-bit Math.random fraction, care must be taken to ensure that rounding up to 1.0 cannot occur. Using 32-bit random integers is safer.
Algorithms should be tested with inputs designed to check perceived points of possible weakness. But to find the unexpected, it can be easy and effective to test also with a large number of random inputs. Once detected, a bug can be investigated in accordance with its apparent nature.
In some browsers, the following code detects bugs or peculiarities in Number.toString(radix). It is hard to explain what all of the bugs are, though. The code box is editable. The test takes a few seconds.
The results are, for each possible radix, the ordered set of characters found as the final character of the .toString(radix) representation of a non-zero Random number, optionally after applying a given Math function. Since trailing zeroes should not be shown, the first numeric line should read "2 1" with only the character representing (radix-1) appended on each successive line.
It can be seen that toString(radix) (useful for obtaining the bits of a Number) is not always as expected. Any difference caused by using Math.sqrt may mean something about Math.random.
Using Math.random, Firefox 3.6.13 looks good. MS IE 8 gives zeroes (except base 10 and powers of 2). Opera 10.10 gave all results as 123456789; Opera 10.63 generally can give (radix+1) and colon - bad rounding-up; Opera 11.00 seems to have corrected that. Safari 5.0.3 gives zeroes in all rows except base 10. Chrome 9.0 gives zeroes for odd bases and few characters for some bases.
Some Bugs in JavaScript Implementations contains another test of Number.toString(radix).
The topic of this page is continued in JavaScript Shuffle, Deal, Draw.