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 4 Apr 2010 00:20 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. So far, I had been using subtractive lagged Fibonacci generators - if a and b are both 53-bit fractions between 0 and 1, you cannot add them without risking to lose a bit to overflow, but you can safely decrease a by b, and add 1 if the result is negative. It is quite possible to make excellent PNRGs that way, but here, I want to submit another approach: Marsaglia's Multiply-with-carry. It has a rather fascinating theory - one essentially grinds out the binary representation of the inverse of a large prime. It may not have been *proved* that this does indeed provide good pseudo-random bits, but any evidence of systematic regularities would surely constitute a major mathematical discovery. More down to earth, MWCs fare very well in empirical tests, actually better so than, e.g., the Mersenne Twister. Besides, they are shorter and faster. My idea is to equate the carries with the integer parts of the main multiplicands, which, if there were to be converted into fixed point, would have at most 21 bits before the "decimal" point and exactly 32 after. (I have experimented with other distributions of the "carry" and the "remainder" parts. Increasing the latter, say, to 38 bits obviously improves the period, but the multiplier becomes too small to affect enough bits. 21 + 32 seems to be a sensible compromise that also makes testing on integer C versions easier.) To the best of my knowledge, this idea of splitting the "carry" and "remainder" in integer and fractional parts is new, which is why I solicit criticism. As a minor point, I would like to point out the use of the Fowler-Noll-Vo hash in order to seed the generator with *any* kind of arguments - Numbers, Strings, Dates, Objets, anything that has a toString method. Here is the code (sorry if it is long, but half of it is comments): function MWC4() { /* Usage: var random = [new] MWC4([...]); The resulting function, random, behaves like Math.random: successive calls to random() return "random" numbers in [0, 1[. The generated pseudo-random numbers should be much more "random", though. If you provide arguments, calling MWC4 again with the same values for all arguments will result in a function that returns the same sequence of pseudo-random numbers across standard-compliant implementations. E.g., var random = MWC4(0); for (var i = 0; i < 1000000; i++) {random();} var x = random(); should always yield x === 0.1041667880930884 If you do provide no arguments, MWC4(+ new Date()) is silently assumed. Using the empty string as sole argument(s) - MWC4('') - is a bad idea: the first numbers won't be very random. Anything else should be OK. Calling MWC4 with new is unnecessary but harmless. */ return (function (args) { /* Marsaglia's Multiply-with-carry ("Mother of All Random Number Generators"), on a small array of four 32-bit numbers, adapted to javascript's quaint notion of numbers. http://groups.google.com/group/sci.stat.math/msg/dd90bad892f56640 http://interstat.statjournals.net/YEAR/2005/articles/0510005.pdf http://en.wikipedia.org/wiki/Multiply-with-carry The multiplier a (here, a = 2096715) must be such that a * s[k] + c fits in 53 bits, and that a * (2 ^ 32) ^ 4 - 1 is a safe prime, that is, a prime whose floored half is also a prime. The period is close to 2 ^ 148, which should be sufficient for most purposes. If you need something stronger, try MWC16: uncomment the 4 lines thus marked below, delete the lines that precede them, and change the name of the pseudo-constructor. That would give you a period of more than 2 ^ 531; I cannot conceive any reasonable use of a PRNG in javascript for which that would not be more than adequate. */ var norm = Math.pow(2, -32); var s = [0, 0, 0, 0]; // MWC16: var s = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; var c = 0; var k = 0; var a = 2096715; // MWC16: var a = 1994205; function mwc() { 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 + s[k] * norm; } // seed array s with arguments // if no arguments, take present time as seed if (args.length === 0 ) { args = [+new Date()]; } // Fowler/Noll/Vo FNV-1a hash // http://www.isthe.com/chongo/tech/comp/fnv/index.html var hash = 0x811c9dc5; function fnv1a(x) { x = x.toString(); for (var i = x.length - 1; i >= 0; i--) { hash = ((hash ^ x.charCodeAt(i)) * 0x01000193) >>> 0; } return hash; } for (var i = 0; i < args.length; i++) { for (var j = 0; j < 4; j++) { // MWC16: for (var j = 0; j < 16; j++) { s[j] -= fnv1a(args[i]) * norm; if (s[j] < 0) { s[j] += 1; } } } return mwc; }(Array.prototype.slice.call(arguments))); } -- Johannes
From: Scott Sauyet on 5 Apr 2010 09:07 Johannes Baagoe wrote: > The resulting function, random, behaves like Math.random: successive > calls to random() return "random" numbers in [0, 1[. The generated > pseudo-random numbers should be much more "random", though. I have no background in PRNGs to really comment on the quality. In brief tests, it gave results that to my naive eyes look random. Have you done performance tests to compare with other JS approaches? What other restrictions are there on the multiplier ("a") than what you describe in the comments? -- Scott
From: Joe Nine on 5 Apr 2010 09:23 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?
From: "Michael Haufe ("TNO")" on 5 Apr 2010 10:17 On Apr 5, 8:23 am, Joe Nine <j...(a)yahoo.com> wrote: > 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? https://bugzilla.mozilla.org/show_bug.cgi?id=322529
From: Hans-Georg Michna on 5 Apr 2010 10:25
On Mon, 05 Apr 2010 15:23:55 +0200, Joe Nine wrote: >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? From the spec: "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 means the function is mostly undefined and has different results and varying quality in different implementations. If you need deterministic results from a program, for example, for a series of tests, you cannot use the built-in Math.random() method. You need a random number generator that, after the same seed, produces exactly the same series of pseudo-random numbers. On top of that, the built-in random number generators may be poorly designed and may not have very good distribution or cycles. Random numbers and their generators are something that, in my experience, is often not well understood. Hans-Georg |