Fast multiplication of integers using tables

I want to tell readers about a programmer trick I met in some kind of transfer book containing a selection of such tricks, in those days when they hadn’t invented anything but a byte, but it’s scary to say - the stack, and the great Dijkstra has not yet cursed the operator GOTO (sic, in uppercase).

I liked the trick so much by its simplicity and grace that even in this millennium I was happy to tell students about it in the following task.

Imagine that in the process of returning from the moon in 2030, you suddenly discovered that your on-board computer incorrectly performs the operations of integer multiplication, and this will certainly lead to an accident during landing.
')
In this story there is nothing particularly fantastic. Let us recall, for example, what problems happened once with Pentium processors , and by the time you were sent to the Moon you had not yet achieved full import substitution. In general, it is necessary to check whether the processors were drilled specifically.

But to the point. You need to urgently implement the multiplication programmatically to work quickly in real time and fit into an available resource.

From the school course of arithmetic, we recall that multiply numbers can be multiplied by a column, and the result of multiplying individual numbers can be taken from the multiplication table.

But if you choose short digits (for example, 0 and 1), the multiplication table will be short, and the bars will be long, and their calculation will take a lot of time.

If, on the contrary, we take long digits (for example, from 0 to 65535), then for 16-bit arithmetic
the result is taken directly from the table, but there are no bars. However, the size of the classical table of Pythagoras at the same time is about 17GB (4 * 65536 * 65536), if we take into account the symmetry with respect to the diagonal, then the half is about 8.5GB.

It may be a bit much.

We strain and recall algebra.

$$$(a + b) ^ 2 = a ^ 2 + b ^ 2 + 2ab$(one)

$$$(a - b) ^ 2 = a ^ 2 + b ^ 2 - 2ab$(2)

Subtract (2) from (1)

$$$(a + b) ^ 2 - (a - b) ^ 2 = 4ab$

and further

$$$a b = ((a + b) ^ 2 - (a - b) ^ 2) / 4$

Thus, having a table of squares in the sqr array, we get

a * b = (sqr [a + b] - sqr [a - b]) / 4 (*)

The size of the table 8 * (65535 + 65535) is about 8.4MB, which may already be acceptable.

The size of an element of a table of 8 bytes is due to the fact that at maximum a and b the square of their sum of 4 bytes does not fit - 2 bits are missing.

Further I will describe some improvement, which was not in the book, I came up with it myself when I wrote this article.

Note that the two lower bits of the square of an even number are always 00, and the square of an odd number is always 01. On the other hand, for any pair of numbers, their sum and difference have the same parity.
Therefore, in our formula (*), the process of subtraction in brackets cannot have hyphenation,
associated with two lower bits. Therefore, the contents of the elements of the table of squares
you can advance two bits to the right in advance and thereby save half the memory.

We finally have

a * b = sqr4 [a + b] - sqr4 [a - b] (**)

where sqr4 is a modified table of squares.

In our example, its size is about 4.2 MB.

Below to illustrate this approach is the text of the program in the language of Lua.

function create_multiplier(N) -- N     local sqr4 = {} --   for i = 1, 2 * N - 1 do local temp = 0 for j = 1, i - 1 do --    temp = temp + i - 1 --    end -- ..  "" sqr4[i] = math.floor(temp / 4) --  2  end return --   () function (i, j) if i < j then i, j = j, i end return sqr4[1 + i + j] - sqr4[1 + i - j] end end N = 256 mpy = create_multiplier(N) for i = 0, N - 1 do for j = 0, N - 1 do if i * j ~= mpy(i,j) then print("", i, j, i * j, mpy(i,j)) end end end print(" .") 

For modern processors, it seems reasonable to have a digit size multiple of a byte size for easy access to them. With numbers of 1 byte in size, the size of the table is only 1022 bytes, which may allow using this trick in 8-bit processors that do not have hardware multiplication.

I would be grateful to all readers of this note for corrections and comments.