Yet another substitute for Math.random
in [JavaScript]
|
Prev: debt consolidation services debt consolidation debt wyoming student loan debt consolidation
Next: Online brand Carisoprodol order Carisoprodol online cod brand Carisoprodol Now
From: Johannes Baagoe on 5 Apr 2010 15:22 Scott Sauyet : > In brief tests, it gave results that to my naive eyes look random. Actually, I am sorry to say that they aren't... This is the offending line : return t + s[k] * norm; That is, I cheated: I used each "random" 32 bits twice, once to provide the most significant bits in one output, and once again to provide the 21 least significant bits three outputs later. At about 4 AM, it seemed a tolerable way to avoid calling the generator twice for each output, thereby halving the period. It is not. To see just how awful it is, try to repeatedly evaluate r().toString(2).replace(/(\d{21})\d{11}/,'$1...'): 0.011110001001101111110...111111010001001011 0.110011110001101000101...101101001000000110011 0.110111001110011101000...000010000000001000011 0.000010001000011110100...0111100010011011111101001 0.101010111100100010111...11001111000110100011 0.000010100110000100000...1101110011100111010001 0.011010000011001011011...0000100010000111101001 Note how the bits in the first half are systematically repeated three lines later in the second half. I tried other methods to avoid calling the generator twice, but finally admitted the obvious: it is a bad idea. Here is the corrected version : var norm1 = Math.pow(2, -21); function mwc0() { var t; t = a * s[k] + c * norm; c = t | 0; t -= c; s[k] = t; k = (k + 1) & 3; // MWC16: k = (k + 1) & 15; return t; } function mwc() { return mwc0() + mwc0() * norm1; } (I intend to post the corrected version with a lot of context under the heading "Random musings" on a website. I shall drop a line to the group when it is done - some things concern javascript specifically, although the theme is more general.) > Have you done performance tests to compare with other JS approaches? Yes, but not in JS, for speed reasons - the tests I use require up to 2^38 random numbers. What I do is to write an equivalent C version, check that it is indeed equivalent by comparing the outputs after throwing away the first million or so, and run the numbers produced by the C version through L'Ecuyer and Simard's Crush and BigCrush batteries of tests, http://www.iro.umontreal.ca/~simardr/testu01/tu01.html Very few PRNGs pass - e.g., the celebrated Mersenne Twister fails both. Linear congruential generators, which are are used in most implementations of Math.random (they have usually been ported from java.util.Random), even fail the quick SmallCrush, making more stringent tests pointless. So far, the latest version of MWC4 has passed Crush with flying colours, and BigCrush is more than half completed without any trouble (it takes about 36 hours on my laptop). > What other restrictions are there on the multiplier ("a") than what > you describe in the comments? None that I know of, but the examples I know in the literature assume that the "remainder" and the "carry" parts are about the same size. It became clear during my tests that if the carries are too small, that is, the multiplier not big enough, the generator fails, e.g., Knuth's MaxOft test. Which, retrospectively, should have been obvious... Anyway, the restrictions imply finding the largest safe prime that satisfies a certain condition. It isn't that difficult, e.g. using GNU's gmp library which has an efficient implementation of the Miller- Rabin primality test, but one cannot simply pick an a at random. -- Johannes
From: Johannes Baagoe on 5 Apr 2010 16:06 Joe Nine : > What's wrong with Math.random that it needs replacing? Hans-Georg Michna summed it up nicely, I only elaborate on details. There is nothing wrong with Math.random if you only use it for cute animations or inconsequential games, which is what it was intended for. On the other hand, if you abuse it for serious Monte-Carlo simulations (hardly the thing one should do in javascript, but many programmers of the younger generation know nothing else...), or to make supposedly unique identifiers to serve as separators in POST requests, or for games than actually involve money and therefore invites hackers to cheat by predicting outcomes, then you are in deep trouble. Actually, there is IMHO a need not just for one, but for several RandomXXX constructors, according to what is the most crucial in the intended application: speed, impeccable statistical behaviour, cryptological security, etc. They all need to share one characteristic, though: publicly available sources, and ensuing review by knowledgeable people. -- Johannes
From: Dr J R Stockton on 5 Apr 2010 13:18 In comp.lang.javascript message <u6qdnWEY65wCjiXWnZ2dnUVZ7tpi4p2d(a)gigane ws.com>, Sat, 3 Apr 2010 23:20:47, Johannes Baagoe <baagoe(a)baagoe.com> posted: >Like many other (semi-)numerical problems in javascript, writing an >efficient substitute for Math.random is not quite like if it were another >language. > ... It would be nice if one could easily find your routines on, or via links on, your Web site. Perhaps you have not seen <http://fr.wikipedia.org/wiki/Tomate#Fruit_ou_l.C3.A9gume_.3F> ?? ASIDE I now suspect Opera 10.51 time offset of being unreliably wrong - having an uninitialised variable, possibly. -- (c) John Stockton, nr London, UK. ?@merlyn.demon.co.uk Turnpike v6.05. Web <URL:http://www.merlyn.demon.co.uk/> - w. FAQish topics, links, acronyms PAS EXE etc : <URL:http://www.merlyn.demon.co.uk/programs/> - see 00index.htm Dates - miscdate.htm estrdate.htm js-dates.htm pas-time.htm critdate.htm etc.
From: Dr J R Stockton on 6 Apr 2010 13:10 In comp.lang.javascript message <hpco9f$q08$03$1(a)news.t-online.com>, Mon, 5 Apr 2010 15:23:55, Joe Nine <joe9(a)yahoo.com> posted: >Johannes Baagoe wrote: >> Like many other (semi-)numerical problems in javascript, writing an >> efficient substitute for Math.random is not quite like if it were another >> language. It is of course always possible to combine two pseudo-random >> 32-bit integers in order to provide the desired 53 significant fractional >> bits, but doing everything directly in 53-bit floating point is an >> interesting challenge. > >What's wrong with Math.random that it needs replacing? See <URL:http://www.merlyn.demon.co.uk/js-randm.htm>, <URL:http://www.merlyn.demon.co.uk/js-262-5.htm>, for a start. AS SPECIFIED, it does not readily give reproducible results in a single browser, and its results are browser-dependent. The quality of its results varies between browsers too. It should be specified as giving, for 0 <= N < 2^53, all of the values N * 2^-53 with equal probability. It should be specified whether the sequence repeats after 2^53, 2^64, or other value. Some applications need better; that should not be done in Math.random, which would be good enough for most purposes. For those who need better, we have Johannes Baagoe and others to provide library routines. Query re ECMA 6 - should it include a means of adding routines, such as a better random, that execute in native machine code rather than in ECMAscript? They would be processor-dependent, and should be distributed as a package of source code + documentation + binary. -- (c) John Stockton, nr London 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 "-- " (RFCs 5536/7) Do not Mail News to me. Before a reply, quote with ">" or "> " (RFCs 5536/7)
From: Lasse Reichstein Nielsen on 7 Apr 2010 01:58
Dr J R Stockton <reply1014(a)merlyn.demon.co.uk> writes: > Query re ECMA 6 - should it include a means of adding routines, such as > a better random, that execute in native machine code rather than in > ECMAscript? They would be processor-dependent, and should be > distributed as a package of source code + documentation + binary. JSNI? No thanks! The security issues of implementing native libraries downloaded at runtime are bad enough with ActiveX. Let's not break JavaScript too. /L -- Lasse Reichstein Holst Nielsen 'Javascript frameworks is a disruptive technology' |