Reply by Clay July 9, 20092009-07-09
On Jul 9, 9:31&#4294967295;am, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On Jul 8, 10:23&#4294967295;am, Clay <c...@claysturner.com> wrote: > > > > > > > On Jul 8, 8:36&#4294967295;am, robert bristow-johnson <r...@audioimagination.com> > > wrote: > > > > On Jul 7, 2:08&#4294967295;pm, Clay <c...@claysturner.com> wrote: > > > > ... > > > > > When I think about generating a MAXIMUM length sequence, I woudn't > > > > even consider something so short as just 4095 states before repeating. > > > > I often use a Mersenne Twister, which has a period of 2^19937. Yes > > > > that's correct. > > > > how does it work? &#4294967295;i cannot imagine it having a period of 2^m without > > > it having a state that is at least m bits wide. &#4294967295;does it stroll > > > through 19937 bits repeatedly? > > > Of course it has 19937 bits in memory - that is only 624 words (32 > > bits each). This may be an issue in a memory limited application, but > > on a general computer not a problem at all. It uses a basic shift > > register with feedback, but unlike common schemes, the feed back is > > "twisted." > > > The Wiki article may help describe it for you. The pseudo code is > > pretty simple to follow > > >http://en.wikipedia.org/wiki/Mersenne_twister > > so a pseudo-statement like: > > "int y := 32nd bit of(MT[i]) + last 31 bits of(MT[(i+1) mod 624])" > > means that the 32nd bit of MT[i] remains in the 32nd place in y (the > MSB) and the lower 31 bits of (MT[(i+1) mod 624] go into the lower 31 > bits of y? &#4294967295;and does the multiplication in initializeGenerator() > involve a (long long) or (unsigned long long) type? > > it also appears that extractNumber() is essentially a table lookup > (with a pretty damn big table) in that it is only a function of MT > [index] and it does not affect the generation of MT[]. &#4294967295;is that bit > scrambling really necessary? &#4294967295;then, if it *is* necessary (the words > would not look random enough without the bit scrambling), the question > is, is it sufficient? > > just curious (and ignorant). > > r b-j- Hide quoted text - > > - Show quoted text -
Hello Robert, 1st we note that 19937 bits is 623 complete 32 bit words plus 1 extra bit. Basically the MT does bit scrambling on each of the 623 words ontil which time you shift down (but not simple linear shifting) the whole 19937 bits. I would say that both of these stages are necessary to ensure the statistical properties. One of the problems with standard linear congruence modulo generators, was you could take pairs of numbers and then use one as an x value and the other as a y value and plot a spot at (x,y). With an LCM generator, the plotted spots would all appear on straight lines. So there was a strong sample to sample correlation. And a lot has been done to make scramblers to remove this correlation. The MT picks consecutive numbers from different points in the 623 word chain. So this removes the sample to sample correlation. Once you have made 623 picks, then a new 623 word chain is formed. Note the efficiency in this process, that the overall data chain "shifting" occures once every 623 calls! Common "C" implementations of the MT actually run faster than the system supplied rand() function. And yes unsigned 32 bit numbers are being used. In the authors' seminal paper on the MT, the paper's title alludes to the lack of sample to sample correlation for sets of up to 623 - 32 bit samples! IHTH, Clay
Reply by robert bristow-johnson July 9, 20092009-07-09
On Jul 8, 10:23=A0am, Clay <c...@claysturner.com> wrote:
> On Jul 8, 8:36=A0am, robert bristow-johnson <r...@audioimagination.com> > wrote: > > > > > On Jul 7, 2:08=A0pm, Clay <c...@claysturner.com> wrote: > > > ... > > > > When I think about generating a MAXIMUM length sequence, I woudn't > > > even consider something so short as just 4095 states before repeating=
.
> > > I often use a Mersenne Twister, which has a period of 2^19937. Yes > > > that's correct. > > > how does it work? =A0i cannot imagine it having a period of 2^m without > > it having a state that is at least m bits wide. =A0does it stroll > > through 19937 bits repeatedly? > > > Of course it has 19937 bits in memory - that is only 624 words (32 > bits each). This may be an issue in a memory limited application, but > on a general computer not a problem at all. It uses a basic shift > register with feedback, but unlike common schemes, the feed back is > "twisted." > > The Wiki article may help describe it for you. The pseudo code is > pretty simple to follow > > http://en.wikipedia.org/wiki/Mersenne_twister
so a pseudo-statement like: "int y :=3D 32nd bit of(MT[i]) + last 31 bits of(MT[(i+1) mod 624])" means that the 32nd bit of MT[i] remains in the 32nd place in y (the MSB) and the lower 31 bits of (MT[(i+1) mod 624] go into the lower 31 bits of y? and does the multiplication in initializeGenerator() involve a (long long) or (unsigned long long) type? it also appears that extractNumber() is essentially a table lookup (with a pretty damn big table) in that it is only a function of MT [index] and it does not affect the generation of MT[]. is that bit scrambling really necessary? then, if it *is* necessary (the words would not look random enough without the bit scrambling), the question is, is it sufficient? just curious (and ignorant). r b-j
Reply by Clay July 8, 20092009-07-08
On Jul 8, 8:36&#4294967295;am, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On Jul 7, 2:08&#4294967295;pm, Clay <c...@claysturner.com> wrote: > > > > ... > > > When I think about generating a MAXIMUM length sequence, I woudn't > > even consider something so short as just 4095 states before repeating. > > I often use a Mersenne Twister, which has a period of 2^19937. Yes > > that's correct. > > how does it work? &#4294967295;i cannot imagine it having a period of 2^m without > it having a state that is at least m bits wide. &#4294967295;does it stroll > through 19937 bits repeatedly? > > r b-j
Hello Robert, Of course it has 19937 bits in memory - that is only 624 words (32 bits each). This may be an issue in a memory limited application, but on a general computer not a problem at all. It uses a basic shift register with feedback, but unlike common schemes, the feed back is "twisted." The Wiki article may help describe it for you. The pseudo code is pretty simple to follow http://en.wikipedia.org/wiki/Mersenne_twister The paper "Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator" is the one where Makoto Matsumoto and Takuji Nishimura first describe the method. You may find the paper here: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf Enjoy! Clay
Reply by robert bristow-johnson July 8, 20092009-07-08
On Jul 7, 2:08&#4294967295;pm, Clay <c...@claysturner.com> wrote:
>
...
> > When I think about generating a MAXIMUM length sequence, I woudn't > even consider something so short as just 4095 states before repeating. > I often use a Mersenne Twister, which has a period of 2^19937. Yes > that's correct.
how does it work? i cannot imagine it having a period of 2^m without it having a state that is at least m bits wide. does it stroll through 19937 bits repeatedly? r b-j
Reply by Nicholas Kinar July 8, 20092009-07-08
> > When I think about generating a MAXIMUM length sequence, I woudn't > even consider something so short as just 4095 states before repeating. > I often use a Mersenne Twister, which has a period of 2^19937. Yes > that's correct. And it is easy to implement and free code exist on the > web for it. The inventor (Makoto Matsumoto ) put it (code and > algorithm) into the public domain, so you are free to use it without > worry about IP issues. And statistically, the Twister's output fairs > better on statistics tests than stuff from a simple loopback of a > shift register with some exclusive ors. You may want to look into > this. > > Clay
Thanks Clay; that's a really neat algorithm! It's certainly something to think about when doing statistical tests. The large period is just amazing.
Reply by Clay July 7, 20092009-07-07
On Jul 7, 3:42&#4294967295;pm, spop...@speedymail.org (Steve Pope) wrote:
> Clay &#4294967295;<c...@claysturner.com> wrote: > >On Jul 7, 2:53&#4294967295;pm, spop...@speedymail.org (Steve Pope) wrote: > >> For example, with a maximal-length sequence formed from a > >> polynomial over GF(2), it's often practical to jump to > >> a prescribed point in the middle of the sequence, or to > >> examine the register contents and figure out where you > >> are in the sequence. &#4294967295;Can a Mersenne twister do that? > >Yes you can start the twister anywhere you want in the sequence. > >Likewise a small number (compared to the length) of observations can > >tell you the starting state. It is not for cryptographic use because > >of these properties. I'm not sure how one would measure the distance a > >current state is away from a defined starting state without clocking > >it through all of the intervening states. Here its long period makes > >it take a while! > > Thanks. > > I've never used the Twister acutally. &#4294967295;If I need something > stronger or more random than an LFSR I usually go with DES or AES, or > something derived from them. &#4294967295; > > Steve
I use it quite a bit. It works very well as a random number generator for games. Also I use it for all sorts of monte carlo testing. It is even good for monte carlo integration. Clay
Reply by Steve Pope July 7, 20092009-07-07
Clay  <clay@claysturner.com> wrote:

>On Jul 7, 2:53&#4294967295;pm, spop...@speedymail.org (Steve Pope) wrote:
>> For example, with a maximal-length sequence formed from a >> polynomial over GF(2), it's often practical to jump to >> a prescribed point in the middle of the sequence, or to >> examine the register contents and figure out where you >> are in the sequence. &#4294967295;Can a Mersenne twister do that?
>Yes you can start the twister anywhere you want in the sequence. >Likewise a small number (compared to the length) of observations can >tell you the starting state. It is not for cryptographic use because >of these properties. I'm not sure how one would measure the distance a >current state is away from a defined starting state without clocking >it through all of the intervening states. Here its long period makes >it take a while!
Thanks. I've never used the Twister acutally. If I need something stronger or more random than an LFSR I usually go with DES or AES, or something derived from them. Steve
Reply by Clay July 7, 20092009-07-07
On Jul 7, 2:53&#4294967295;pm, spop...@speedymail.org (Steve Pope) wrote:
> Clay &#4294967295;<c...@claysturner.com> wrote: > >On Jul 4, 12:55&#4294967295;am, Nicholas Kinar <n.ki...@usask.ca> wrote: > >> I am trying to generate a Maximum Length Sequence (MLS) using a Linear > >> Feedback Shift Register (LFSR). > >When I think about generating a MAXIMUM length sequence, I woudn't > >even consider something so short as just 4095 states before repeating. > >I often use a Mersenne Twister, which has a period of 2^19937. Yes > >that's correct. And it is easy to implement and free code exist on the > >web for it. > > Turns out that engineering requirements come in all forms > and sometimes you do not want, or cannot use, the more > elaborate solution. > > For example, with a maximal-length sequence formed from a > polynomial over GF(2), it's often practical to jump to > a prescribed point in the middle of the sequence, or to > examine the register contents and figure out where you > are in the sequence. &#4294967295;Can a Mersenne twister do that? > > Steve
Hello Steve, Yes you can start the twister anywhere you want in the sequence. Likewise a small number (compared to the length) of observations can tell you the starting state. It is not for cryptographic use because of these properties. I'm not sure how one would measure the distance a current state is away from a defined starting state without clocking it through all of the intervening states. Here its long period makes it take a while! Clay
Reply by Steve Pope July 7, 20092009-07-07
Clay  <clay@claysturner.com> wrote:

>On Jul 4, 12:55&#4294967295;am, Nicholas Kinar <n.ki...@usask.ca> wrote:
>> I am trying to generate a Maximum Length Sequence (MLS) using a Linear >> Feedback Shift Register (LFSR).
>When I think about generating a MAXIMUM length sequence, I woudn't >even consider something so short as just 4095 states before repeating. >I often use a Mersenne Twister, which has a period of 2^19937. Yes >that's correct. And it is easy to implement and free code exist on the >web for it.
Turns out that engineering requirements come in all forms and sometimes you do not want, or cannot use, the more elaborate solution. For example, with a maximal-length sequence formed from a polynomial over GF(2), it's often practical to jump to a prescribed point in the middle of the sequence, or to examine the register contents and figure out where you are in the sequence. Can a Mersenne twister do that? Steve
Reply by Clay July 7, 20092009-07-07
On Jul 4, 12:55&#4294967295;am, Nicholas Kinar <n.ki...@usask.ca> wrote:
> Hello-- > > I am trying to generate a Maximum Length Sequence (MLS) using a Linear > Feedback Shift Register (LFSR). &#4294967295;Assuming that the taps have been loaded > into variable "taps," and that "lfsr" is the variable being used in the > &#4294967295; shift register computation, I am trying to generate the sequence using > code similar to that found on Wikipedia at the pagehttp://en.wikipedia.org/wiki/Linear_feedback_shift_register. &#4294967295;Here is a > code snippet: > > // generate sequence > for(int i = 0; i < L; i++) > { > &#4294967295; &#4294967295; &#4294967295; &#4294967295; lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & taps); > > &#4294967295; &#4294967295; &#4294967295; &#4294967295; // if I have an output array with L elements, > &#4294967295; &#4294967295; &#4294967295; &#4294967295; // what do I set it equal to in this loop? > &#4294967295; &#4294967295; &#4294967295; &#4294967295; // output[i] = ?? > > } > > However, how do I determine the output of the LFSR? &#4294967295;For m = 12, it > follows that L = (2^m) - 1 = 4095. &#4294967295;How would I generate an MLS sequence > with a length of 4095 using the above code? &#4294967295;The loop should repeat 4095 > times. &#4294967295;What is the "output stream"? Is it simply the lowest bit in the > sequence? &#4294967295;Is this the bit that is fed back into the sequence after > passing through the logic gates? > > Is there a way to test if my output is an MLS? &#4294967295;Does the Galois LFSR > generate exactly the same output as a Fibonacci LFSR?
Hello Nicholas, When I think about generating a MAXIMUM length sequence, I woudn't even consider something so short as just 4095 states before repeating. I often use a Mersenne Twister, which has a period of 2^19937. Yes that's correct. And it is easy to implement and free code exist on the web for it. The inventor (Makoto Matsumoto ) put it (code and algorithm) into the public domain, so you are free to use it without worry about IP issues. And statistically, the Twister's output fairs better on statistics tests than stuff from a simple loopback of a shift register with some exclusive ors. You may want to look into this. Clay