a * b = qs[a + b] - qs[|a - b|] where qs[n] is n squared over four
because (a+b)^2/4 minus (a-b)^2/4 is exactly a*b, and the halves the
flooring throws away cancel between the two terms. A multiply is two
lookups and a subtract.
AND THE TABLE IS BUILT BY ADDING, which is the part that makes it fit a
machine with no multiplier at all. A table of squares would need squaring
to fill; this one does not, because qs[n] = qs[n-1] + n/2, and n/2 goes 0,
1, 1, 2, 2, 3 - a number that steps up on every even n. So the whole thing
is a running total and a toggle, and nothing harder than an add appears
anywhere in building the thing that does the multiplying.
511 entries of two bytes, because a byte plus a byte reaches 510. That is
1,022 bytes of Data Memory, and it is the price: a kilobyte traded for an
operation the hardware has not got.
The operands go in memory rather than in registers. B cannot be stored and
a product does not fit in one byte anyway, so two in and two out would
spend more instructions shuffling than the multiply costs.
Checked against nought, the commutation both ways round, a square, and 255
times 255 - which is 0xFE01 and the largest product two bytes hold. The
square is the case the identity leans on hardest: the difference term is
nought and the whole answer comes out of one entry.
Wanted for Lunar Porter's orbit, where the trade between height and speed
has to be proportional to vx times vy and could not be. Useful well beyond
it: this is the routine every fixed point sum on this machine has been
doing without.
Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01E2JrLzFvuFX9fgi1LDRjrW
AnachronautandClaude Opus 5
Anachronaut