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.
- Github: prng_6502 - source code, unit tests, development history, commentary.
- Wiki: Random number generator - has the 16-bit version.
- Wiki: advanced LFSR - has the 24/32-bit versions.
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.