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: Jorge on 14 Apr 2010 05:10 On Apr 13, 7:36 pm, Dr J R Stockton <reply1...(a)merlyn.demon.co.uk> wrote: > In comp.lang.javascript message <57b4ed7e-8e2e-4e5f-943e-9ceffaa42d18(a)r2 > 7g2000yqn.googlegroups.com>, Mon, 12 Apr 2010 09:40:09, Jorge > <jo...(a)jorgechamorro.com> posted: > > >On Apr 12, 5:40 pm, Johannes Baagoe <baa...(a)baagoe.com> wrote: > >> (...) > >> So, my question is: what are the problems with that approach? > > >None. It's perfectly legal and It's all right, because a function is > >no less an object than any other object, AFAIK. > > >There's something I'd like to ask you. When you say that the period of > >e.g. RandomKISS2007 is greater than 2^123, I wonder how can that be, > >given that there are no more than 64 bits in a float. I mean, it will > >surely return a repeated value long before 2^123, right ? How can the > >period be longer than 2^64, in any case ? > > The state is not stored in a float. > > If you toss a penny in the traditional manner, the state between throws > is stored in exactly 0 bits, and has 1 value. In a set of throws, there > mist be at least one repeated value within every three throws. But the > cycle length is infinite. That's a very good, clear and understandable explanation. Thanks. > 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[. Could you please elaborate ? > N.B. "should" != "will". I don't get it... ¿? -- Jorge.
From: Johannes Baagoe on 14 Apr 2010 13:22 Jorge : >> There's something I'd like to ask you. When you say that the period >> of e.g. RandomKISS2007 is greater than 2^123, I wonder how can that >> be, given that there are no more than 64 bits in a float. I mean, >> it will surely return a repeated value long before 2^123, right ? >> How can the period be longer than 2^64, in any case ? Sorry to respond late, and via another post - yours didn't appear in my news reader, I don't know why. KISS2007 adds the outputs of three independent generators with different periods. The first generators's state is simply an unsigned 32 bit integer. It gets incremented at each call by an odd number, which obviously makes it cycle through all its 2 ^ 32 possible values. That is, it has a period of 2^32. The second generator's state is also an unsigned 32 bit integer, but it is not allowed to be zero. That is, it has 2^32 - 1 possible values. A clever succession of shifts and XORs at each call makes it jump through its possible values in an irregular fashion, reaching its initial position after 2^32 - 1 calls. That is, it has a period of 2^32 - 1. That means that when the second generator reaches its starting position, the first generator has not quite attained *its* starting position - it will reach it one call later, by which time, the second generator has advanced by one step. Since the global generator adds the two results, its period (so far) is 2^23 * (2^32 - 1). The third generator has more state: two 31-bit integers plus one bit. Its progression does not quite loop through all the 2^63 possible values, but it still has a rather long period: 2^62 + 2^31 - 2. This has the common factor 2 with 2^32, and the common factor 5 with 2^32 - 1. The combined period is 2^32 * (2^32 - 1) * (2^62 + 2^31 - 2) / 10 = 8507059175004165644829287608064409600, a bit less than 2 ^ 123 = 10633823966279326983230456482242756608. In short: a good PRNG's output does not reflect its total state. At each call, the state is altered in a way that makes it return to its initial state only after a long period, at least 2^100 for most good generators, even 2^19937 − 1 for the Mersenne Twister. The output "summarises" that state, but by no means in an exhaustive way. -- Johannes
From: Jorge on 15 Apr 2010 12:07 On Apr 14, 7:22 pm, Johannes Baagoe <baa...(a)baagoe.com> wrote: > Jorge : > > >> There's something I'd like to ask you. When you say that the period > >> of e.g. RandomKISS2007 is greater than 2^123, I wonder how can that > >> be, given that there are no more than 64 bits in a float. I mean, > >> it will surely return a repeated value long before 2^123, right ? > >> How can the period be longer than 2^64, in any case ? > > Sorry to respond late, and via another post - yours didn't appear in my > news reader, I don't know why. > > KISS2007 adds the outputs of three independent generators with different > periods. > > The first generators's state is simply an unsigned 32 bit integer. It gets > incremented at each call by an odd number, which obviously makes it cycle > through all its 2 ^ 32 possible values. That is, it has a period of 2^32. > > The second generator's state is also an unsigned 32 bit integer, but it > is not allowed to be zero. That is, it has 2^32 - 1 possible values. A > clever succession of shifts and XORs at each call makes it jump through > its possible values in an irregular fashion, reaching its initial position > after 2^32 - 1 calls. That is, it has a period of 2^32 - 1. > > That means that when the second generator reaches its starting position, > the first generator has not quite attained *its* starting position - > it will reach it one call later, by which time, the second generator has > advanced by one step. Since the global generator adds the two results, > its period (so far) is 2^23 * (2^32 - 1). > > The third generator has more state: two 31-bit integers plus one bit. > Its progression does not quite loop through all the 2^63 possible values, > but it still has a rather long period: 2^62 + 2^31 - 2. This has > the common factor 2 with 2^32, and the common factor 5 with 2^32 - 1. > The combined period is 2^32 * (2^32 - 1) * (2^62 + 2^31 - 2) / 10 = > 8507059175004165644829287608064409600, a bit less than 2 ^ 123 = > 10633823966279326983230456482242756608. > > In short: a good PRNG's output does not reflect its total state. At each > call, the state is altered in a way that makes it return to its initial > state only after a long period, at least 2^100 for most good generators, > even 2^19937 - 1 for the Mersenne Twister. The output "summarises" > that state, but by no means in an exhaustive way. Ok. Thank you very much. 8-P -- Jorge.
From: Dr J R Stockton on 15 Apr 2010 14:02 In comp.lang.javascript message <63f56686-ee89-47ab-8ba1-285a5337e2b5(a)g3 0g2000yqc.googlegroups.com>, Wed, 14 Apr 2010 02:10:47, Jorge <jorge(a)jorgechamorro.com> posted: > >> 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[. > >Could you please elaborate ? Possible values : ( 0) * 2^-53 ( 1) * 2^-53 ( 2) * 2^-53 ( 3) * 2^-53 .... (2^53-3) * 2^-53 (2^53-2) * 2^-53 (2^53-1) * 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. > >> N.B. "should" != "will". > >I don't get it... �? You noticed that I used "should"? it does not mean "will". -- (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: Johannes Baagoe on 15 Apr 2010 18:29
Dr J R Stockton : > Jorge : >>> 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[. >> Could you please elaborate ? > Possible values : > ( 0) * 2^-53 > ( 1) * 2^-53 > ( 2) * 2^-53 > ( 3) * 2^-53 > ... > (2^53-3) * 2^-53 > (2^53-2) * 2^-53 > (2^53-1) * 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. 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.) 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; } -- Johannes |