Updated random number generator (efficient 8-step LFSRs)

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems.

Moderator: Moderators

Post Reply
User avatar
rainwarrior
Posts: 7669
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Updated random number generator (efficient 8-step LFSRs)

Post by rainwarrior » Fri Sep 27, 2019 4:46 pm

I spent some time the last few days updating the random number generator example on the wiki with some new versions that more efficiently generate multiple bits:
There were some recent chat discussions about PRNGs, and jroatch showed me his very good 32-bit LFSR written a few years ago that was the same LFSR as I had used, but did 8 steps at once instead of iterating 1 bit at a time. I knew this was possible, as I'd seen it in some CRC implementations, but for some reason I guess I didn't want to follow up on it back then...

Anyway, I went through and updated all three LFSR RNGs with similar efficient 8-at-once operations. These all run in constant time, roughly more than twice as fast as the iterative version (69-83 cycles), and still very small code (35-44 bytes). This technique scaled extremely well to 24 and 32 bits.


The original iterative versions are still useful too, and you could actually mix and match them with the overlapped versions in the same code because they're really the same LFSR. When you want less than 8 bits, maybe up to about 4 bits, it's still faster just to use the iterative version, which might be handy especially if you want to do a bunch of 1-bit 50/50 decisions.

They're simpler and easier to understand, too, so beside the sub-8-bit usage I think they're also worth keeping around just for the learning example.


...but in the course of recent conversations I was realizing most people don't want to think about how many bits they need, and just want a copy-paste thing they can call and have return a random 8-bit number. The new stuff caters to this need. ;)

User avatar
pubby
Posts: 544
Joined: Thu Mar 31, 2016 11:15 am

Re: Updated random number generator (efficient 8-step LFSRs)

Post by pubby » Sun Sep 29, 2019 3:12 am

Sweet thanks for sharing.

User avatar
Lucradan
Posts: 99
Joined: Wed Sep 21, 2016 12:08 pm

Re: Updated random number generator (efficient 8-step LFSRs)

Post by Lucradan » Wed Nov 06, 2019 7:52 am

Most PRNGs (including LFSRs) work on the same idea of a moving along a fixed Hamiltonian cycle. Depending on the tuning parameters, LFSRs work on 1 of 16 different cycles. If you want the fastest PRNG, just create your own random permutation of the numbers 0 to 255 and use it as a look up table. It's topologically the same. The trade off is that it takes 256 bytes of PRGROM.

EDIT: I've not done the proof yet, but I'm fairly confident that if we had an N byte index that it would also be topologically equivalent to an N×8 bit LFSR.

User avatar
dougeff
Posts: 2614
Joined: Fri May 08, 2015 7:17 pm
Location: DIGDUG
Contact:

Re: Updated random number generator (efficient 8-step LFSRs)

Post by dougeff » Wed Nov 06, 2019 8:27 am

https://xkcd.com/221/

int GetRandomNumber()
{
return 4; // chosen by fair dice roll, guaranteed to be random
}
nesdoug.com -- blog/tutorial on programming for the NES

lidnariq
Posts: 8778
Joined: Sun Apr 13, 2008 11:12 am
Location: Seattle

Re: Updated random number generator (efficient 8-step LFSRs)

Post by lidnariq » Wed Nov 06, 2019 11:08 am

Lucradan wrote:Depending on the tuning parameters, LFSRs work on 1 of 16 different cycles.
???

There's no restriction on the number of bits in an LFSR, and for many sizes multiple maximal-period LFSRs are documented. For non-maximal-period LFSRs, they'll often break down into many shorter loops ... (edit) as far as I can tell always with periods of the form Π(2ⁿ-1) (e.g. tonal noise with period 31, or 93=3·31, or 2600 TIA periods of 15, 31, 511, or 465=15·31 ) There are 352 distinct cycles that the noise channel LFSR in tonal mode can fall into.

The Atari Lynx's sound uses this ability to configure taps and starting value to get a wide breadth of chip sounds ... but it's pretty difficult to use.
If you want the fastest PRNG, just create your own random permutation of the numbers 0 to 255 and use it as a look up table. It's topologically the same. The trade off is that it takes 256 bytes of PRGROM.
An 8 bit period PRNG may be adequate for a games where the total number of bits or samples needed per frame is pretty slow. But any game where you go through the entire table quickly will start being obvious to the person playing. And galois-implementation LFSRs scale up with very little computational load per extra byte of state in the LFSR.
Last edited by lidnariq on Wed Nov 06, 2019 12:48 pm, edited 2 times in total.

knight0fdragon
Posts: 10
Joined: Wed Sep 25, 2019 9:11 am

Re: Updated random number generator (efficient 8-step LFSRs)

Post by knight0fdragon » Wed Nov 06, 2019 11:19 am

dougeff wrote:https://xkcd.com/221/

int GetRandomNumber()
{
return 4; // chosen by fair dice roll, guaranteed to be random
}

Only if you are Sony lol

User avatar
Lucradan
Posts: 99
Joined: Wed Sep 21, 2016 12:08 pm

Re: Updated random number generator (efficient 8-step LFSRs)

Post by Lucradan » Wed Nov 06, 2019 11:24 am

lidnariq wrote:???
See the code here. They do a great job of explaining the LFSR

https://codebase64.org/doku.php?id=base ... 8-bit_prng

The "tuning parameter" is the value in the EOR command.

lidnariq
Posts: 8778
Joined: Sun Apr 13, 2008 11:12 am
Location: Seattle

Re: Updated random number generator (efficient 8-step LFSRs)

Post by lidnariq » Wed Nov 06, 2019 11:31 am

Oh. They're saying that there are 16 8-bit maximal period LFSRs. That's ... not the same as the words you used at all.

Post Reply