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: Dr J R Stockton on 16 Apr 2010 15:55 In comp.lang.javascript message <vbOdnZn02YqxDlrWnZ2dnUVZ8rhi4p2d(a)gigane ws.com>, Thu, 15 Apr 2010 17:29:00, Johannes Baagoe <baagoe(a)baagoe.com> posted: >Dr J R Stockton : >>>> My belief is that ECMA 6th Edition should specify that the possible >>>> values of Math.random() shall be N * 2^-53, for N in [0, 2^53[. >> That set is the largest possible equally-spaced set of the numbers X, >> such that 0.0 <= X < 1.0, that can be stored in an IEEE Double. > >The problem is that it is very often twice as slow to generate 53-bit >random numbers as it is to generate 32-bit or 31-bit random numbers. >There are very few ways of generating 53 random bits at a time >with IEEE doubles, and AFAIK, none of them is particularly good >from a theoretical point of view. It doesn't help that much if the >implementation may use 64-bit integers internally, either, unless >one has a true 64-bit architecture. Which of course is becoming >increasingly common, but one can hardly assume it yet. Math.random is, I presume, to be implemented in an efficiently compiled manner. If so, it will be fast in comparison with any reasonable script that uses it. My test code for repeats, for example, does rather little with the result of the call, yet each loop takes of the order of a microsecond on a 3 GHz machine, which must mostly be incurred by the script rather than the body of Math.random. Given that a 64-bit Lehmer is easy to program, and the bottom 11 bits will not be used, and the LSBs of Math.random are of little importance, ISTM that it should serve, if nothing simple & better is known. It would at least be better than current Safari and Chrome. Math.random should be raised by explicit specification to what a reasonable optimist would expect on reading the current specification; and given a means of setting the seed/state. There should be a new method of Math, giving a random integer in 0 to N- 1. The FAQ code does that, but putting it in ECMA 6 would get it into all revised lists of Methods. There should also be a new method or methods of Math, along superior lines, including GUIDs. The new methods can be supplied as script for engines not yet implementing them natively. >Therefore, I think that it would be a mistake to mandate anything >more than 32 bits, and wise to allow anything above 30.999999999328196 >(2^31 - 1 is a Mersenne prime, which is handy for some algorithms.) I thing we'll have to agree that we've established a consistent mutual disagreement on this matter. >If you really need 53 bits and are confident that Math.random provides >at least 27, it is easy enough to combine two calls : > > var x = Math.random() - Math.random() * Math.pow(2, -26); > if (x < 0) { > x += 1; > } If the first Math.random gives a small value, and the second gives a value whose mantissa ends in 1, then the result will not be a multiple of 2^-53. OTOH, if the first gives a large value, the result must be a multiple of 2^-53. That sort of result is unsatisfactory; MSIE gives it, but not Firefox Opera Safari Chrome. A side-effect is that 0.0, while possible, is much less probable than 0.5. That is not a uniform distribution. I think it would be better to build a 53-bit integer, effectively by concatenation, and multiply that by 2^-53. It would be slower, but perhaps not enough to matter. Your mail is half-answered ... The average Chrome repeat could well be 2^30. Or a little more! -- (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: Johannes Baagoe on 16 Apr 2010 22:35 Dr J R Stockton : > Math.random is, I presume, to be implemented in an efficiently > compiled manner. If so, it will be fast in comparison with any > reasonable script that uses it. My test code for repeats, for > example, does rather little with the result of the call, yet each loop > takes of the order of a microsecond on a 3 GHz machine, which must > mostly be incurred by the script rather than the body of Math.random. Try http://baagoe.com/en/RandomMusings/javascript/tests.xhtml :) > Given that a 64-bit Lehmer is easy to program, and the bottom 11 > bits will not be used, and the LSBs of Math.random are of little > importance, ISTM that it should serve, if nothing simple & better > is known. Much better is known, and even 64 bit Lehmer (aka LCG) is not good enough. The period should be at least the square of the highest number of calls in the same experiment, and the distribution in higher dimensions should be better than what LCGs can provide. See http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf > It would at least be better than current Safari and Chrome. I'm not sure of that, because I have no idea of how they generate their random numbers. That is precisely the problem - one does not know. [Make 53 bits mandatory] > I thing we'll have to agree that we've established a consistent > mutual disagreement on this matter. I'm afraid so :) >> If you really need 53 bits and are confident that Math.random >> provides at least 27, it is easy enough to combine two calls : >> var x = Math.random() - Math.random() * Math.pow(2, -26); >> if (x < 0) { >> x += 1; >> } > If the first Math.random gives a small value, and the second gives a > value whose mantissa ends in 1, then the result will not be a multiple > of 2^-53. OTOH, if the first gives a large value, the result must > be a multiple of 2^-53. That sort of result is unsatisfactory; Why ? > A side-effect is that 0.0, while possible, is much less probable > than 0.5. That is not a uniform distribution. Unless I have missed something, each of the intervals [i * 2^-53, (i + 1) * 2^-53[ has the same probability, which is what is needed. > I think it would be better to build a 53-bit integer, effectively > by concatenation, and multiply that by 2^-53. It would be slower, > but perhaps not enough to matter. It would certainly be slower, but why would it be better? -- Johannes
From: Johannes Baagoe on 16 Apr 2010 23:02 Johannes Baagoe : > Try http://baagoe.com/en/RandomMusings/javascript/tests.xhtml Sorry, http://baagoe.com/en/RandomMusings/javascript/time.xhtml -- Johannes
From: Lasse Reichstein Nielsen on 17 Apr 2010 05:36 Johannes Baagoe <baagoe(a)baagoe.com> writes: > Dr J R Stockton : >> It would at least be better than current Safari and Chrome. > > I'm not sure of that, because I have no idea of how they generate their > random numbers. That is precisely the problem - one does not know. Luckily both are Open Source: Safari: http://trac.webkit.org/browser/trunk/JavaScriptCore/runtime/WeakRandom.h Chrome: http://code.google.com/p/v8/source/browse/trunk/src/v8.cc#171 (Just like Firefox: http://hg.mozilla.org/tracemonkey/file/95d633a94459/js/src/jsmath.cpp#l415 ) /L -- Lasse Reichstein Holst Nielsen 'Javascript frameworks is a disruptive technology'
From: Johannes Baagoe on 17 Apr 2010 06:56
Lasse Reichstein Nielsen : > Johannes Baagoe : >> Dr J R Stockton : >>> It would at least be better than current Safari and Chrome. >> I'm not sure of that, because I have no idea of how they generate >> their random numbers. That is precisely the problem - one does >> not know. > Luckily both are Open Source: > Safari: > http://trac.webkit.org/browser/trunk/JavaScriptCore/runtime/WeakRandom.h > Chrome: > http://code.google.com/p/v8/source/browse/trunk/src/v8.cc#171 I stand corrected: when it is Open Source, we do know :) Thanks a lot for finding the relevant parts in the sources. So Safari uses Ian Bulliard's GameRand, and Chrome uses Marsaglia's original "Mother of all" MWC. Neither is good, both fail SmallCrush, but 64-bit LCG with multiplier 6364136223846793005 is even worse, it fails it spectacularly : The following tests gave p-values outside [0.001, 0.9990]: (eps means a value < 1.0e-300): (eps1 means a value < 1.0e-15): Test p-value ---------------------------------------------- 3 Gap eps 4 SimpPoker eps 5 CouponCollector eps 7 WeightDistrib eps 9 HammingIndep eps 10 RandomWalk1 H eps ---------------------------------------------- Bulliard himself acknowledges that the main merit of his is speed, http://ianbullard.squarespace.com/journal/2009/4/28/why-you-should-never-use-rand.html but it nearly passes SmallCrush, with only one low p-value of 5.0e-7 for RandomWalk1 H. Marsaglia's is mainly of historical interest, http://groups.google.com/group/sci.stat.math/msg/dd90bad892f56640 http://groups.google.com/group/sci.crypt/msg/eb4ddde782b17051 IMHO, however, failing SmallCrush excludes from further consideration. > (Just like Firefox: > http://hg.mozilla.org/tracemonkey/file/95d633a94459/js/src/jsmath.cpp#l415 > ) Yes, that is the port from java.util.Random. It makes the best one can from a LCG, but LCGs belong in a museum, like FORTRAN IV and OS/360. -- Johannes |