Jump to content
  • Advertisement


This topic is now archived and is closed to further replies.


Linear-feedback shift registers

This topic is 5463 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I just found out about these and wrote a little test program which has curious behaviour. For those who don't know, the basic algorithm is this
track a variable holding the last result
shift it one to the right
mask off a few bits and count the set ones
if an odd number are set, set the msb of the variable  
The code I used was simply this
shr EAX, 1
test EAX, lfsrmask
jnp @F
	or EAX, 2147483648
push EAX
dec ECX
jnz loop_top  
With an initial value of 3544756459 for EAX, and a mask of 1174405121 (this mask is supposed to make the algo visit every possible number at least once before looping) I dumped a meg of the stack noise to the disk to see how random it was. At a first glance in a hex editor it didn't look too promising, there were clear diagonal repeats of symbols in groups, but it isn't so straitforward. For a start the repeats are seperated by 33 bytes so the stream of DWORDs is actually very diverse. Secondly the groups of four symbols which repeated changed slightly each time. Typical example: xNYû 29 bytes of other stuff xNYV 29 bytes of other stuff xNÜV 29 bytes of other stuff xEÜV and so on... And that's not just the occasional bit change, eg û to V is 0xEA to 0x56, or, in binary 11101010 01010110 So why are the other 3 bytes unchanged? And why should *every * pattern be (almost) repeated exactly 33 bytes later? Wierd. But these pattern's aren't just occational, they aren't even all over the place, they ARE the output. Thousands of unique patterns overlapping. Look at this typical selection
3-byte groups always appear exactly twice. I just ran this thing ten million times and i haven't found a single repeated DWORD so I suspect the claim that this particular bit mask does visit every possible number is true. I ran it again with the "test EAX, lfsrmask" line edited out, so the parity check is on the whole value, not just a few bits. Naturally the output was different but it behaves exactly the same way, same style of repetition exactly and I still haven't found repeated DWORDs in several megabyte files. I don't know about you but I find this mildly fascinating. It's certainly a good algo for games: it's fast and even when a number partially repeats it's a byte out of place and 8 DWORDs after it's previous. Do you like this as much as I do? EDIT: This output is every eigth iteration, so you can beter see the semi-repeats
ä ,½
yä ,
yä l
******** I am not the Iraqi information minister. GSACP : GameDev Society Against Crap Posting To join: Put these lines in your signature and don't post crap! [edited by - walkingcarcass on August 6, 2003 4:30:53 PM]

Share this post

Link to post
Share on other sites
It could come in useful sometimes, but many applications (esp random location generation) may be quite sensitive to numbers appearing too near each other too often.

Say if you randomly generate power-ups on a level, there will be definate (although migratory) hot-spots.

I use the mersenne twister for my random numbers, which is also quite fast, and is vastly superior (AFAIK) to any other fast software random number generator in common use in terms of randomness. (At least that''s what I found in lectures and the web).

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!