Lattice Multiplication

[davidn]

Why on earth didn't anyone teach me about this when I was in school! I've been covering the whiteboard in these ever since I saw this going past on Facebook (I haven't yet found definitive proof that it's of Japanese origin).

After a couple of fascinated scribbles (please excuse the mouse handwriting), I realized that by counting the intersections, you're doing exactly the same thing as the normal long multiplication method of multiplying each position by each other position, just laying it out visually... but it's so satisfying to see it fall out of a tartan picnic rug like that. Besides, it's prettier than a column of numbers.

I will have to remember this for when I next have paper to hand but not a calculator, which in today's environment will be round about never.

Comments

[premchaia_pre4]

It's much more elegant in binary where the choice is between writing a 1 or a 0 and the test is a basic comparison. You can partially emulate that in decimal: precompute (8B, 4B, 2B, B) for divisor B, then add bits to the result digit, which is at least an optimized “whittling-down” because not-adding a bit is very cheap. (5B, 2B, B) also works in a sort of mixed-base intermediary representation. Or, more commonly (I think?), you can round to two significant digits over one and get your initial estimate that way by inverted single-digit multiplication tables, then count up or down from there (there's probably a guaranteed error bound in there but I'm too lazy to compute it just now).

[davidn]

I do remember that I only truly understood long division the first time that I had to use the same technique for binary division. However, after that explanation I'm pretty sure I understand it less again.