logo To Foot
© J R Stockton, ≥ 2013-11-09

JavaScript Random Numbers.

No-Frame * Framed Index * Frame This
Links within this site :-

See "About This JavaScript Site" in JavaScript Index and Introduction.

Donald E Knuth :-
"Random numbers should not be generated with a method chosen at random".

Links

For both this page and JavaScript Shuffle, Deal, Draw :-

Random Number Generation

See also my Borland Pascal/Delphi Random, the general considerations and methods of which are applicable in any language.

Notes

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.

Pseudo-Random Number Generators

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.

Grades

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.

Math.random

[ECMA 262-5]
15.8.2.14 random ( )
Returns a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy. This function takes no arguments.

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 function properties of the Math object (but not of Math.prototype) are seemingly read/write (the numerical properties are read-only). So Math.random might perhaps be reassigned to in order to upgrade the randomness used in an imported routine.

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.

An Old Opera Error

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.

Initialisation

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.

Security

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.

crypto.random

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

Repeatable Random Numbers

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..

Simple Reproducible Random Numbers

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.

32-bit State

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().

Rough 32-bit Arithmetic

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.

Exact 32-bit Arithmetic
Pascal Equivalent
(* 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

Two Long-Period Random Number Generators

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.

General State

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.

Enter numbers as normal hexadecimal, quad-spaced   Prev
× Mult
+ More
= Prod
% Chop (Bits)
= Rslt
# Random IEEE Double
At present, Rslt and Mult must be given sufficient digits; and if that is stipulated, simplifications can be made. Modification is needed, at least for Chop < 53.

64-bit State

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.

  Rslt
  Random IEEE Double

Better Pseudo-Random Number Functions

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

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 :-


  Show version in use :-  

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.

Testing Random-Function Properties

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.

A button intitially marked 1 is an on/off button.
"Stop" takes effect at the end of a Batch.
Turn off each fast test after use, since if more than one test is left running with default timeout, the browser may appear very slow.

Select a Function

Remember to use the Select button after altering any of the settings.

Select and try a Random routine to be tested below
Routine to be used
Code below, read as each test is started, giving either of
  • a function to be used instead of Math.random,
  • a function returning such a function.
  The box is editable; and other functions can be pasted in.
 Math.random
 Rand32Rough
 Rand32Exact
 VastRandFnc
 Random64Fnc
Code insertion box
TYPE :   As a simple function :     As Baagøe v0.9+ :
Choose the initialisation of a Baagøe function from the box above
  Ancestor()  Not right here ?
  Ancestor(0)
  Ancestor("")
  Ancestor(  )  
  Ancestor(+new Date())
Choose for tests below Return :   frac53 :   uint32 :   ( uint64 : dodgy)
  I.D. :
Initial trial @1Hz
uint64 :   frac53 :
uint32 :   Return :   Binary :
Chosen :
My Opera 10.10 to 10.63 toString(2) gave Binary displays visibly wrong at the end of the line; 11.01 did not.
Test Resolution 1Test Resolution 2Test UniformityTest Mean Bit and Tail Values
Test Repeat IntervalTest for SequenceTest for Time
Initialisation Test (General Test)

Initialisation now works wherever possible. It cannot work on ECMA-262 3/5 Math.random.


Each row shows three consecutive results after attempting the indicated initialisation.

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.

Test Resolution 1

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.

  Batch:   Timeout: ms  
Batch and Timeout are re-read for each Batch. There is a Timeout between each Batch of new random values. In IE8, layout fails.
Hits
Zeroes
 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.

Test Resolution 2

I have read that, for each call of Math.random, versions of MS IE (including 6-8, 9 preview and beta, but perhaps not 9 release) use a common 48-bit PRNG twice, concatenate 27-bit (starting at the MSB) subsets, divide by 254, and convert to an IEEE Double. If the MSB of the 54 bits is 1, there will be rounding, with detectable effects. If that MSB is not 1 (value < 0.5), the "54th bit" can be set. Other effects are predicted and found.

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.)

FIRST '1' : BIT 1 to BIT   bits shown :   Test Count :
  Flip :

Test Uniformity

The random value is as a fixed-point binary fraction (integers are normalised to that).

  Batch :   Timeout : ms  
BINS : Start :   SSize :   Steps :
Batch and Timeout are re-read for each Batch. There is a Timeout between each Batch of new random values. In IE8, layout fails and there are no graphs.
Bits

Note : this tests one aspect of distribution, not randomness as such.

Test Mean Bit and Tail Values

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.

  Batch :   Timeout : ms  
Batch and Timeout are re-read for each Batch. There is a Timeout between each Batch of new random values. In IE8, layout fails and there are no graphs.
Bits
  Small-bit results for uint64 need contemplation and may well be meaningless.

Note : this shows one aspect of distribution, not randomness as such.

Test Repeat Interval

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.

  Batch :   Timeout : ms  
Batch and Timeout are re-read for each Batch. There is a Timeout between each Batch of new random values.
Count, Time :

For Math.random :-

Test for Sequence

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.

  Initify :   Batch :   Timeout : ms   Show 10 from :
Batch and Timeout are re-read for each Batch. There is a Timeout between each Batch of new random values.
Property : Use if found - ABANDON?
Count :
If the results are not reproducible, the function lacks an effective initialise.
 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

Test for Time

Repeatedly averaging several Batches each taking seconds is needed for a good result. Use Dummy() to measure tining overhead.

  Batch :   Timeout : ms   Count : max   Dummy()
Timeout is re-read for each Batch. Timeout occurs between Batches of new random values.

Time : ns
"Err" should be Estimated Error of Mean. Check.

Note that the timing accuracy may be impaired by necessary flexibility in the script. For best results, test specific methods yourself.

Available Bugs

Bug 1

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.

Testing With Random Numbers

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.

Number.toString(radix)

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.


  Math.
   

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.

Home Page
Mail: no HTML
© Dr J R Stockton, near London, UK.
All Rights Reserved.
These pages are tested mainly with Firefox and W3's Tidy.
This site, http://www.merlyn.demon.co.uk/, is maintained by me.
Head.