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 17 Apr 2010 07:00 Johannes Baagoe : > Bulliard Ian Bullard, actually. My apologies if he ever reads this newsgroup. -- Johannes
From: Dr J R Stockton on 18 Apr 2010 13:20 In comp.lang.javascript message <k4s6pgid.fsf(a)gmail.com>, Sat, 17 Apr 2010 11:36:42, Lasse Reichstein Nielsen <lrn.unread(a)gmail.com> posted: >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 Unsatisfactory in that it contains no reference for authority for the quality of the code. >Chrome: > http://code.google.com/p/v8/source/browse/trunk/src/v8.cc#171 No link to the authority, so could be using an outdated version. >(Just like Firefox: > http://hg.mozilla.org/tracemonkey/file/95d633a94459/js/src/jsmath.cpp#l415 >) -- (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: Dr J R Stockton on 18 Apr 2010 17:11 In comp.lang.javascript message <wZOdnRKTK9cQg1TWnZ2dnUVZ8g5i4p2d(a)gigane ws.com>, Fri, 16 Apr 2010 21:35:57, Johannes Baagoe <baagoe(a)baagoe.com> posted: >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 :) That (but ...time.xhtml) does not account for the overheads. I get 267ms for a million Math.random, but do not get how long is spent in the script and how long within Math.random's internal code. What we want is a built-in method of Math that does nothing but return its argument; the difference in time between that and Math.random is the time taken to do the internal work. But Math.abs *should* be good enough; it can be implemented either by clearing the MSB or by a FABS instruction (IIRC), and so should be internally fast. HOWEVER, Math.abs(D) seems slower in FF 3.0.19 & IE8 than Math.random() & Math.random(D) - it's nearly as fast as Math.PI in FF. Your page responded badly to pressing the button while it was running; perhaps disable the button and add a means of breaking between timings? My point is that the true measure of the cost of time taken by code within Math.random is the percentage increase in the time taken by the smallest useful ECMAScript loop that uses the value. >> 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. I think you are looking for higher quality than is needed for Math.random. After all, if the code in Chrome and in Safari has been found generally acceptable, Math.random does not need to be all that good. Upgrade Math.random to satisfy what the existing standard suggests, and add a new Method for those who need better. If there is a real need for GUIDs, add Math.GUID or String.GUID. I don't thing that one can consistently and on grounds of speed (and assuming 32-bit integer & IEEE Double instructions available) both object to 64-bit or 53-bit Lehmer and also favour built-in KISS (for example). To ECMA : ALL random-generating routines should have an optional final argument, which sets the internal state. That's trivial to add, and aids testing. Add the routine in the CLJ FAQ, as a Method. Add Method String.GUID. Add a Method which returns a random 53-bit integer. That can be shortened by % Math.pow(2, N) . >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. My page <URL:http://www.merlyn.demon.co.uk/js-randm.htm>, section "Generator Properties", shows that they don't do it well. >[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 ? Because it is incompatible with a a uniform distribution of equally- spaced values. var x = Math.random() % Math.pow(2, -26) - Math.random() % Math.pow(2, -27) * Math.pow(2, -26); where the 26 & 27 may need changing. >> 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. One can only say what should be provided if one considers all possible applications, coded by programmers within the normal range of skill. >> 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? Note : better does not mean best. Because that will certainly, blunders apart, give all possible evenly-spaced values in [0,1[ with equal probability. There, the integer does not to be held in a Number of integer value; it may well be better to have the exponent smaller by 53. The essential is that no LSBs should be rounded up, and the hardware is not asked to do bitwise 1+1. I am now convinced that, for any consecutive 2^30 + 1 results from Math.random() in Safari 4.0.5 [on both my WinXP machines], the first and the last are equal in value; AND that occasionally (~10% ?) an intermediate result has the same value. On my PCs, Math.random() in a small loop takes about a microsecond; and 2^53 us is over 285 years. But 2^32 us is under an hour and a quarter. Therefore, a period of 2^32 could be inadequate, but one of 2^48 should suffice. 2^53 is adequate even if instruction rates get considerably faster, and there is no need to seek 2^64. I disregard crypto work. -- (c) John Stockton, nr London, UK. ?@merlyn.demon.co.uk Turnpike v6.05 IE 7. Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links. I find MiniTrue useful for viewing/searching/altering files, at a DOS prompt; free, DOS/Win/UNIX, <URL:http://www.idiotsdelight.net/minitrue/> unsupported.
From: Johannes Baagoe on 19 Apr 2010 07:37 Dr J R Stockton : > Johannes Baagoe : >> Try [http://baagoe.com/en/RandomMusings/javascript/time.xhtml] :) > That [...] does not account for the overheads. I get 267ms for a > million Math.random, but do not get how long is spent in the script > and how long within Math.random's internal code. Point taken, and your arguments plus a bit of experimenting have convinced me that there is no way I can meaningfully measure the speed of Math.random on my page. I have therefore removed that test. I have also compensated for overhead, and prevented calls for new timings while one is running. As for the what Math.random should provide, merits of 53 vs 32 bits, 64-bit Lehmer vs. Safari's and Chrome's present implementations, whether it matters that the first value repeats, etc, I think we just have to agree to disagree. -- Johannes
From: VK on 19 Apr 2010 09:02
On Apr 17, 6:35 am, Johannes Baagoe <baa...(a)baagoe.com> wrote: > 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. On the matter of Math.random "randomness" vs. custom algorithms I would suggest the regular way of using Shannon's Clairvoyant. In the professional cryptography it is used to determine if the testing matter truly random or pseudo-random, given that the tester is truly random (based on pre-recorded physical process results). In your case you might make two clairvoyants: one based on the native Math.random, the other on some custom pseudo-random algorithm. Now let them play 1/0 (even/off, true/false) game to each other. Statistically 10,000 rounds with 10,000 moves in each round would suffice for an educated guess and it will take lesser than a minute for them to play - of course setTimeout breaks will be needed. If both are equally good then 50/50 wins +/-5% Above 5% difference would suggest that one algorithm is better pseudo- random than the other. The actual difference will show how much better it is so if it worth to abandon the native method for the custom one. |