Current version

v1.10.4 (stable)

Navigation

Main page
Archived news
Downloads
Documentation
   Capture
   Compiling
   Processing
   Crashes
Features
Filters
Plugin SDK
Knowledge base
Contact info
 
Other projects
   Altirra

Archives

Blog Archive

Computers are fast

It's amazing how much faster computers have become. Sure, they can never be fast enough for some purposes -- like, uh, video processing -- but for others, it's getting a bit ridiculous.

A linear feedback shift register is a type of sequence generator that is useful for quickly generating psuedo-random sequences of numbers. It's not a great generator, but because it only requires shifts and XORs, it's very fast. It also easily generates a maximal non-repeating sequence of size 2^N-1, which means it's also useful for generating exact coverage patterns without duplicates or dropouts, especially since the sequence is generated on the fly and isn't stored. It can be used for real-time image dissolves and static noise generation... on a 1MHz Apple II! I haven't used it in VirtualDub yet, but there are a few places where I could, such as if I needed a random dither for audio sample conversion from 16-bit to 8-bit (although I'd probably try error diffusion first).

Anyway, today I needed a 32-bit LFSR generator. An LFSR generator basically shifts new bits in that are XORs of a series of taps on the shift register, and the position of those taps is critical: if they aren't correct, the generator won't produce the maximum possible sequence. I'm too lazy to actually look up a list of primitive polynomials, though, so I usually just try a bunch of tap combinations until I get one that works. So I picked four taps and just let a test app measure the length of the sequence. It then dawned on me that in less than a minute, the computer had run through all four billion bits in the sequence. And I didn't even optimize the algorithm.

Basically, computers have gotten fast enough that sometimes it's better just to brute force test all inputs to an algorithm... it's easy, it's harder to screw up, and a passing result from one is fairly convincing. And it's lazy. I like it when companies like Intel and NVIDIA help me be lazy. I look forward to my next upgrade, which will probably include some dual core and DX10 goodness and help me be more lazy.

(Sharp readers will note that since I was able to run through the 32-bit sequence in less than a minute, I probably need a longer generator, and I can't really brute force test a 64-bit LFSR... but hey, at least it'll still be damn fast.)

Comments

This blog was originally open for comments when this entry was first posted, but was later closed and then removed due to spam and after a migration away from the original blog software. Unfortunately, it would have been a lot of work to reformat the comments to republish them. The author thanks everyone who posted comments and added to the discussion.