今天给大家介绍一篇1962年的论文《Computer Multiplication and Division Using Binary Logarithms》^[1]，作者是John N. Mitchell，他在里边提出了一个相当有意思的算法：在二进制下，可以完全通过加法来近似完成两个数的相乘，最大误差不超过1/9。整个算法相当巧妙，更有意思的是它还有着非常简洁的编程实现，让人拍案叫绝。然而，笔者发现网上居然找不到介绍这个算法的网页，所以在此介绍一番。

你以为这只是过时的玩意？那你就错了，前不久才有人利用它发了一篇NeurIPS 2020呢！所以，确定不来了解一下吗？

快速对数与指数

说到乘法变加法，大家应该很自然能联想到对数和指数，即

本文是基于二进制的，所以a=2。问题在于上式虽然确实将乘法转为加法了，但是对数和转换后的指数算起来都不是一件容易的事情。所以要利用这个等式做乘法，关键在于要实现快速对数和指数运算。

对于十进制的非负数p，我们假设它的二进制表示为

其中且各个，那么我们就有

记，我们得到

在这里，Mitchell做了一个相当果断而美妙的近似，那就是（后面我们会再进行误差分析），于是得到

这个结果妙在何处呢？首先n是一个整数，等于p的二进制的整数部分的位数减去1，它转换为二进制自然自然也是整数；那x呢？根据x的定义我们不难看出，实际上x的二进制表示就是

也就是说x其实就是上述近似的小数部分，它的二进制表示只不过是p的二进制表示的简单变形（小数点平移）。

综上所述，我们得到对数的Mitchell近似算法：

将上述过程逆过来，就得到了指数的Mitchell近似算法：所以，在二进制下对数和指数的近似计算就只是数数和拼接操作而已！惊艳不？神奇不？

一个乘法的例子

有了快速的（近似的）对数和指数算法，我们就可以乘法了，现在我们就用这个思路来算一个具体例子，由此加深我们对上述过程理解。

我们要算的是12.3×4.56，计算流程如下表（近似指数是对求和的结果算的）：其中p,qp,qp,q二进制表示为无限循环小数，这里只截断了有限位，如果保留精确的二进制表示，那么最终结果是53.68，跟上表的53.625相差不大。可以看到，整个过程的主要计算量有两部分：求和、十进制与二进制之间的转换。然而，尽管十进制与二进制之间的转换对于我们人来说是计算量比较大的操作，但对于计算机来说，它本身就是二进制存储的，我们可以认为两者之间的转换计算量可以忽略不计；又或者说，只要我们还是以十进制为输出，那么不管什么算法这部分计算量都是必然存在的，因此我们不把它算进去算法的复杂度中。所以，整个算法的计算量就只有求和这一步，实现了将乘法（近似地）转化为加法运算。

神奇的C++实现

更妙的是，上述过程有一个非常简单的C++实现，参考如下：

 plt

x = np.arange(0, 1, 0.001)
y = np.arange(0, 1, 0.001)

X, Y = np.meshgrid(x, y)
Z1 = (1 + X + Y) / (1 + X + Y + X * Y)
Z2 = 2 * (X + Y) / (1 + X + Y + X * Y)
Z = (X + Y < 1) * Z1 + (X + Y >= 1) * Z2
plt.figure(figsize=(7, 6))
contourf = plt.contourf(X, Y, Z)
plt.contour(X, Y, Z)
plt.colorbar(contourf)
plt.show()

其实这个误差本质上取决于的近似程度，我们知道x是自然对数的一阶泰勒展开式，而e=2.71828更加接近于3，所以如果计算机使用3进制的话，本算法会有更高的平均精度。事实上，确实有一些理论分析表明，对于计算机来说其实最理想是e进制，而3比2更接近于e，所以三进制计算机在不少方面会比二进制更优，我国和前苏联都曾研究过三进制计算机，不过由于二进制实现起来更加容易，所以当前还是二进制计算机的天下了。

搬到深度学习中

Mitchell近似的介绍就到这里了。读者可能会困惑，这不该是计算机基础和数据机构那一块的东西吗？你研究它干嘛？还能在深度学习中有什么应用吗？

笔者学习它的原因有两个：一是它确实很漂亮，值得学习；二是它还真的可以用到深度学习中。事实上，笔者是NeurIPS 2020的一篇论文《Deep Neural Network Training without Multiplications》^[2]中发现它的，该论文在“ImageNet+ResNet50”验证了直接将神经网络中的乘法换成Mitchell近似的加法形式，准确率只有轻微的下降，甚至可能不下降。

当然，作者目前的实现只是验证了这种替换在效果上是可接受的，在速度上其实是变慢了的。这是因为虽然从理论上来讲乘法换成近似加法速度一定会有提升，但要实现这个提升需要从硬件底层进行优化才行，所以作者是提供了未来深度学习硬件优化的一个方向吧。此外，Mitchell近似在深度学习中的应用分析，也不是第一次被讨论了，直接Google就可以搜到两篇，分别是《Efficient Mitchell’s Approximate Log Multipliers for Convolutional Neural Networks》^[3]和《Low-power implementation of Mitchell's approximate logarithmic multiplication for convolutional neural networks》^[4]。

可能读者联想到了华为之前提出的加法神经网络AdderNet，其目的确实有类似之处，但方法上其实差别很大。AdderNet是将神经网络的内积换成了距离，从而去掉了乘法；这篇论文则是修改了乘法的实现，降低了乘法的计算量，已有的神经网络运算可能都可以保留下来。

也把新瓶装旧酒

本文介绍了1962年发表的Mitchell近似算法，它是一种近似的对数和指数计算，基于此我们可以将乘法转化为加法，并保持一定的精度。看上去已经过时，但将这个算法“新瓶装旧酒”一下，就成为了NeurIPS 2020中一篇论文了。

所以，你还发现了哪些可以装到新瓶的“旧酒”呢？ 

[1] https://ieeexplore.ieee.org/document/5219391

[2] https://arxiv.org/abs/2012.03458

[3] https://ieeexplore.ieee.org/document/8532287

[4] https://ieeexplore.ieee.org/document/8297391