Embarrassing confession time: I never learned my multiplication tables in grade school. Sure, I had the easy tables like the twos and the fives down, but if asked what 4 x 7 or 8 x 6 was, I’d draw a blank. As you can imagine, that made me a less than stellar math student, and I was especially handicapped on time-limited tests with lots of long multiplication problems. The standard algorithm is much faster when you’ve committed those tables to memory, as I discovered to my great woe.
I was reminded of this painful memory as I watched Charles Lohr’s 2019 Supercon talk on the usefulness and flexibility of lookup tables, or LUTs, and their ability to ease or even completely avoid computationally intensive operations. Of course most LUT implementations address problems somewhat more complex than multiplication tables, but they don’t have to. As Charles points out, even the tables of sines and logarithms that used to populate page after page in reference books have been ported to silicon, where looking up the correct answer based on user input is far easier than deriving the answer computationally.
One of the most interesting examples of how LUTs can achieve the seemingly impossible lies in an old project where Charles attempted to build a Minecraft server on an ATMega168. Sending chunks (the data representations of a portion of the game world) to clients is the essential job of a Minecraft server, and on normal machines that involves using data compression. Rather than trying to implement zlib on an 8-bit microcontroller, he turned to a LUT that just feeds the raw bytes to the client, without the server having the slightest idea what any of it means. A similar technique is used by some power inverters, which synthesize sine wave output by feeding one full cycle of values to a DAC from a byte array. It’s brute force, but it works.
Another fascinating and unexpected realization is that LUTs don’t necessarily have to be software. Some can be implemented in completely mechanical systems. Charles used the example of cams on a shaft; in a car’s engine, these represent the code needed to open and close valves at the right time for each cylinder. More complicated examples are the cams and gears once found in fire control computers for naval guns, or the programming cards used for Jacquard looms. He even tips his hat to the Wintergatan marble machine, with its large programming drum and pegs acting as a hardware LUT.
I found Charles’ talk wide-ranging and fascinating. Originally I thought it would be an FPGA-heavy talk, but he didn’t actually get to the FPGA-specific stuff until the very end. That worked out fine, though — just hearing about all the cool problems a LUT can solve was worth the price of admission.
And for the curious, yes, I did eventually end up memorizing the multiplication tables. Oddly, it only clicked for me after I started playing with numbers and seeing their relationships using my first calculator, which ironically enough probably used LUTs to calculate results.
Continue reading “Using Lookup Tables To Make The Impossible Possible”
