使用表进行快速整数乘法

我想向读者介绍我在某种翻译书中遇到的编程技巧，其中包含一些在遥远的时代精选出来的技巧，当时还不仅是字节的发明，而且还很难说堆栈，而且伟大的Dijkstra还没有诅咒运算符GOTO（原文如此，大写）。

我非常喜欢这个技巧的简单性和优雅性，以至于在本世纪已经很高兴以以下任务的形式向学生介绍这个技巧。

想象一下，在2030年从月球返回的过程中，您突然发现车载计算机未正确执行整数乘法运算，这肯定会导致着陆时发生事故。

在这个故事中，没有什么特别奇妙的。 例如，让我们回想一下， 奔腾处理器曾经发生了什么问题，到您被送上月球时，您还没有达到完全的进口替代。 通常，必须检查处理器是否经过特殊钻孔。

但是要点。 您迫切需要以编程方式实现乘法，以使其实时快速运行并适合可用资源。

从学校的数学课程中，我们记得多值数可以乘以一列，而各个数相乘的结果可以从乘法表中得出。

但是，只有选择短数字（例如0和1）时，乘法表才会短而列较长，并且它们的计算将花费大量时间。

相反，如果我们采用长整数（例如，从0到65535），则进行16位算术运算
结果直接从表中获取，并且缺少列。 但是，经典毕达哥拉斯表的大小约为17GB（4 * 65536 * 65536），如果考虑到对角线的对称性，则一半约为8.5GB。

可能有点太多。

上紧并记住代数。

$$$（a + b）^ 2 = a ^ 2 + b ^ 2 + 2ab$（1）

$$$（a-b）^ 2 = a ^ 2 + b ^ 2-2ab$（2）

从（1）减去（2 ）

$$$（a + b）^ 2-（a-b）^ 2 = 4ab$

并进一步

$$$a b =（（a + b）^ 2-（a-b）^ 2）/ 4$

因此，在sqr数组中有一个正方形表，我们得到

a * b =（平方[a + b]-平方[a-b]）/ 4 （*）

8 *表（65535 + 65535）的大小约为8.4MB，这可能已经可以接受了。

8个字节的表元素的大小是由于以下事实：对于最大a和b，它们4个字节的和的平方不适合-2位是不够的。

接下来，我将描述一些改进，但本书并未对此进行介绍。 我已经在写本笔记时自己想到了。

请注意，偶数平方的两个最低有效位始终为00，奇数平方始终为01。另一方面，对于任何一对数字，它们的和和差具有相同的奇偶校验。
因此，在我们的公式（*）中，括号中的减法过程不能包含连字符，
与两个最低有效位相关联。 因此，平方表元素的内容
您可以向右移两位，从而节省一半的内存。

最后我们有

a * b = sqr4 [a + b]-sqr4 [a-b] （**）

其中sqr4是修改后的平方表。

在我们的示例中，其大小约为4.2 MB。

下面说明了这种方法，其中包含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(" .") 

对于现代处理器，为了方便访问它们，将数字大小设置为字节大小的倍数似乎是合理的。 对于1字节的数字，表的大小仅为1022字节，这可能使该技巧可以在没有硬件乘法的8位处理器中使用。

在此感谢所有读者的纠正和评论。