Re: Math.random

In comp.lang.javascript message <x6ydnWI21dMBbtvXnZ2dnUVZ8oRi4p2d@gigane
ws.com>, Sat, 27 Jun 2009 23:37:48, Johannes Baagoe <baagoe@xxxxxxxxxx>
posted:
Johannes Baagoe :

The problem arises because the vast majority of PRNGs generate
integers, not fractions between 0 (included) and 1 (excluded). And
the ones most suitable for ECMAScript produce 32-bit integers

Dr J R Stockton :

I disagree strongly. The ones most commonly used may be 32-bit;
but they are NOT suitable.

Why not? I am talking about the number of bits they produce at a time,
not their internal state which is always larger in the case of good
PRNGs, and often *much* larger.

OK; but it seems silly nowadays to have RNGs with many more states and
to get only 32-bit values.


There is no difficulty in programming 64-bit Lehmer, and 64-bit code
using the kiss32 approach, on any modern machine; it just takes a
little more work.

Quite, but why would one bother when some of the most suitable
operations - shifts, XORs, etc - happen to operate on 32 bits
in ECMAScript, and several 32-bit well-researched PRNGS which
are straightforward to code pass all known tests with flying
colours, whereas even the best LCG fails them miserably,
and *must* fail them, for well-known theoretical reasons ?
(http://www.pnas.org/content/61/1/25.full.pdf)

You are still concentrating on systems suitable for generating GUIDs,
and possibly for crypto work. I am interested in getting an adequate
Math.random, preferably native to browsers, with the sort of performance
that a Double should give - equivalent to a fixed exponent, 53 random
mantissa bits, and a cycle length of at least 2^53, with a cycle length
over 2^64 being overkill.

An attempt to over-improve on Math.random by something that looks too
complicated may be self-defeating.

To get a non-native version, one must code in JavaScript, where logical
operations on over 32 bits are cumbersome. But one hopes that the
JavaScript engine is not written entirely in JavaScript. IIRC, the 8086
language has 16-bit shifts with carry, so that a 64-bit shift by 1
requires just 4 ops; and the 386 language may have 32-bit shifts; and
modern machines should be better than that.


VastRand, in <js-randm.htm>, does exact 64-bit Lehmer in JavaScript
in only a few lines of my code; it would be easier in ASM or Pascal
(or, I presume, on C/C++) on a 32-bit machine, especially if the
flexibility were omitted.

Yes, I must confess that I haven't understood the code, not even to
the point of figuring out what the multiplier may be.

Well, it comes from the control marked "Mult", which has a name of Mult,
and is read into Obj.Mult. The default value is from Knuth, as in your
next paragraph.


64-bit Lehmer, sagaciously converted to 53 bits, may not be the
best solution of its order of complexity; but it is surely better
than what the inferior browsers use for Math.random, when using
Knuth-approved constants.

Knuth recommends C. E. Haynes's 6364136223846793005, I know of no other
proposal. *Nobody* does 2^64 LCGs, there is simply no point. It is
like investing lots of efforts to build a bigger and better Zeppelin.

Let a and b be two "random" unsigned 32-bit integers obtained by
some suitable method.

If they are obtained by successive calls of the same 32-bit method
using one 32-bit state, the second call adds no real randomness.

What do you mean by "real randomness" ? If the generator produces
successive numbers that are not correlated in any meaningful way,
as it should (and LCGs fail to do), what else would be needed ?

With a known algorithm, a 32-bit state and a cycle length of 2^32, the
result of the second call is knowable once the result of the first is
known.

One must have sufficient state bits;

Quite so, and 64 is probably not enough. The simplest generator I
*know* passes L'Ecuyers' BigCrunch battery of tests is his own MRG32k3a
which has a state of 192 bits. Marsaglia's KISS32, which I *suspect*
passes BigCruch as well (it passes Crunch, I haven't yet had the time
to test BigCrunch which is rather lengthy) has somewhat less than 127.

You are, of course, aiming for something much better than Math.random
needs, provided that Math.random is not used for crypto or GUIDs.

In any case, Math.random cannot be truly suitable for those, since it
gives a Double and those will want integers or strings.


and if they are in different generators the generators should have
co-prime lengths

That is indeed an important consideration for combined generators,
which are possibly the simplest way to make good ones.

(except maybe if they are truly independently seeded).

That seems to me to be a completely different issue, am I missing
something ?

I thought that I saw a *possible* loophole to the co-prime requirement;
perhaps you know that it's not an actual loophole.

--
(c) John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v6.05 MIME.
Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
Proper <= 4-line sig. separator as above, a line exactly "-- " (SonOfRFC1036)
Do not Mail News to me. Before a reply, quote with ">" or "> " (SonOfRFC1036)
.

Relevant Pages

  • Re: Math.random
    ... the ones most suitable for ECMAScript produce 32-bit integers ... colours, whereas even the best LCG fails them miserably, ... The simplest generator I ... *know* passes L'Ecuyers' BigCrunch battery of tests is his own MRG32k3a ...
    (comp.lang.javascript)
  • Re: Noob questions about Python
    ... multiplying by ten shifts the digits to the left by one place: ... efficient than using a Generator ... memory, leading to all sorts of complicated memory shuffles as the list ...
    (comp.lang.python)
  • Advance SG70 in problems
    ... I recently switched on an old Advance SG70 LF generator and found that the ... It shifts a lot up and down. ... Prev by Date: ...
    (sci.electronics.equipment)