Mathematicians still don't know the fastest way to multiply numbers

I don't know what age range "grade school" is, but I remember being taught that method when I was about 7 or 8, although it didn't really "land" properly until I read the short story "The Feeling of Power" by Isaac Asimov.

What I'm surprised to see left out here (unless I missed it in the page's horrible formatting) is a mention of the way that computers multiply two integers. They use a technique I saw described in a book when I was about 11 as the "Russian Farmer Method" (or something like that, it was in English and I might have misremembered it).

In that you shift the multiplier right and multiplicand left, halving one and doubling the other. If the multiplier is odd, add the multiplicand to the total.

It's really doing the same thing as "long multiplication" like you're taught in primary school but in binary so when you add a 0 to the right for the higher order digits you're doubling, not multiplying by ten. If you write code to do it you'd shift the multiplier first then consider whether or not to add by testing the Carry flag, or "Link bit" if like the author of the book I read you're demonstrating it on a PDP8 ;-)

But let's have a worked example, picking two numbers at random 205 * 707, use the smaller as the multiplier:

  205, 707   odd, add   707 to total
  102, 1414  even, disregard
  51,  2828  odd, add  2828 to the total
  25,  5656  odd, add  5656 to the total
  12,  11312 even, disregard
  6,   22624 even, disregard
  3,   45248 odd, add 45248 to the total
  1,   90496 odd, add 90496 to the total
  --------------------------------------
                     144935

If we're disregarding shifts and adds as completing in negligible time, well, this whole thing is just done with shifts and adds, and you can predict how many of them by identifying the leftmost bit set in the multiplier.

Why do we make computers multiply single digit numbers, instead of taking the result from a lookup table, like humans do? To answer my own question, I am assuming it would be because multiplying would still be faster than reading from a lookup table? Any ideas?

2 ^ (713 739 807 325 663 489 766 475 852 620 783 120 641) digits. Nope, an implementation of that algorithm will never be directly useful.

I disagree. 1 step is a finite sequence of instructions.

Hardware multipliers often use a sort of base-4-ish lookup table trick as well, using the Booth-Wallace algorithm. Booth's idea is to rewrite one of the inputs in base (usually) "4", except that the digits go from -2 to +2 instead of 0 to 3. (That's five possible digits! This helps the rewriting stage not have to propagate carries. Carry propagation is very expensive.) You can use Booth in a base higher than 4, especially if you know one of the multiplicands before the other, but you run into tradeoffs pretty quickly.

Then for each digit, you select between the other input multiplied by 0 (all zeros), +1 (identity), +2 (shift left by one bit), or -1 or -2 (flip all the bits of +1 or +2, plus a correction). Since a number has about half as many digits in base 4 as in base 2, you have about half as many digits to sum as if you'd done this in base 2.

Then you sum up all those results, but since carry propagation is expensive, you mostly use "compressors", e.g. you sum up three intermediates at a time, but you do it bit-by-bit, where three 1-bit numbers add up to a 2-bit number (from 0 to 3). This is called a Wallace Tree. The point is that you are generating carries, but you aren't propagating them, just adding them back into the set of things to be summed.

At the end of the tree step, you have just two numbers left, and you add them conventionally. That's the only step that needs full carry propagation.

If you are implementing a multiply-add, or multiplying several numbers and adding up all the results or similar, then you usually only need one full carry propagation stage.

The overall circuit has quadratic area but only a logarithmic depth in gates. IIRC whether to do Booth or not is a tradeoff: at least in some circumstances the rewrite steps make it slower but smaller. Hardware tool vendors have done a lot of work to tune these circuits very tightly, using e.g. specialized gates like AOI, heuristics for how to set up the tree, etc.