In a sense, they do exactly that! But since there are only two single-digit numbers in binary, it makes for a pretty short table.
In a sense, they do exactly that! But since there are only two single-digit numbers in binary, it makes for a pretty short table.
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.
Carry propagation is indeed quite slow. With so much math for AI, is it finally time to go back to analog? Superposition is instant.
If carry propagation is so expensive, why are the mathematicians, like Karatsuba, ignoring it? It seems like we need a better complexity measure.
> 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 base 5 then. It needs to go from -2 to +1 if you want base 4
It's still a modified base 4, because the significance of the i'th digit is 4^i, not 5^i.
Edited to add: I'm also not sure whether real-life implementations have -0 as an option. Of course -0 could be normalized to +0, but it might be cheaper not to bother if the sign is applied after the digit selection.
No, balanced ternary, for example, uses {-1, 0, 1}. The system you're discussing is balanced quinary (base 5).
https://en.wikipedia.org/wiki/Signed-digit_representation
It isn't balanced quinary, but rather redundant balanced quaternary (base 4). In balanced quinary (base 5), each digit has 5x the significance of the previous one, but in Booth's encoding algorithm it's 4x.
If digit i has significance b^i, then b (the base of the exponentiation) is the base (or radix) of the number system.
The page you linked explicitly mentions the binary version of Booth encoding as having base b=2 and three signed digits {-1, 0, 1}. The quaternary version similarly has b=4 and five signed digits {-2, -1, 0, 1, 2} ... and possibly sometimes -0 in practice, not sure.