© J R Stockton, ≥ 2013-11-09

Links within this site :-

**Merlyn Home Page**- Site Index, E-Mail, Copying**This Page**:-**JavaScript**:-- Index and Introduction - with About This Site, Code Re-use, Links
- JavaScript Shuffle, Deal, Draw
- On Standard ECMA-262 5th Edition ... - includes Random
- Maths
- Demonstrations
- Rounding - pages 0 1 2 3
- Date and Time
- Tests
- General
- Alarm
- Include Files

- Borland Pascal/Delphi Random - related material.

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

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

- Wikipedia :-
- Usenet articles :-
- the late George Marsaglia (CLF, Jun 2007)
- Johannes Baagøe (CLJ, Jun 2009)

- Better random numbers for javascript - Johannes Baagøe
- Random Number Generators (RNGs) in the Scientific Computing and Numerical Analysis FAQ
- Class Random for java.util
- random.org
- Resources for random number generation (in Swarm User Guide)
- Chapter 9. Random Numbers (164kB)
- Random, but Not by Chance: A Quantum Random-Number Generator for Encryption, Security
- Expand the Random function (Delphi feedback)
- Amit Klein - (below)
- Other links in my Borland Pascal/Delphi Random

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 2^{N}
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 2^{N}
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.

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

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/2 ^{N}` for all

A generator with a 32-bit state can lead at best to 2^{32}
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
2^{53} 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.

`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
2^{32}/2730.

To get 2^{53} 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 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 = 2 ^{32}`
Knuth has written that the following
combination is excellent.

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

**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 (2^{16}-1). Element J
has a weight of 16^{4×J}. Array [0x0001, 0x0055, 0x0999,
0xDDDD] would represent unsigned 0xDDDD099900550001.

The code can do long arithmetic to base 65536 (2^{16}),
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 < 2^{64}.

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

- your browser's
`Math.random`, - the Random functions given above,
- an editable Random function in the box below,
- any other Random function, to be pasted in,
- Johannes Baagøe's v.0.9 Ancestor code, or similar, to be pasted in.
- any other function with a similar interface to that, to be pasted in.

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.

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

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

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 1 Test Resolution 2 Test Uniformity Test Mean Bit and Tail Values

Test Repeat Interval Test for Sequence Test for Time

Test Resolution 1 Test Resolution 2 Test Uniformity Test Mean Bit and Tail Values

Test Repeat Interval Test for Sequence Test for Time

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.

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
2^{54}, 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.)

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
2^{53} = 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` :-

- MS IE 8 does not repeat before (over 2^34)
- Firefox 3.0.19 did not repeat before (over 2^33),

Firefox 3.6.3 crashed (soon after 2^30 from a clean start). Firefox 3.6.13 crashed likewise - error in looping.

I am told that Firefox will repeat after 2^47. - Opera 9.62 repeated after 2147483648 (2^31); Opera 10.63 does not repeat before (over 2^36)
- Safari 4.0.5 usually repeated after every 1073741824 (2^30), but has often been seen to also repeat alternately after 366551250 and 707190574, 554166754 and 519575070, etc. Safari 5.0.3 repeats irregularly, om average after several times 1e9.
- Chrome 4.1 repeated irregularly, typically after several hundreds of millions (average about 1.2e9?). Chrome 5.0 was similar, with average perhaps nearer 0.8e9? Chrome 8.0 and 9.0 similar, larger average, perhaps about 4.0e9 or 2^32? Averages are very uncertain.

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.randomNo InitialisationCode 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.**