网站建设的指导思想,寻找电销团队合作,调价智能关键词软件,外企网站建设公司文#xff1a;苏剑林编#xff1a;兔子酱单位#xff1a;追一科技今天给大家介绍一篇1962年的论文《Computer Multiplication and Division Using Binary Logarithms》[1]#xff0c;作者是John N. Mitchell#xff0c;他在里边提出了一个相当有意思的算法#xff1a;在二… 文苏剑林编兔子酱单位追一科技今天给大家介绍一篇1962年的论文《Computer Multiplication and Division Using Binary Logarithms》[1]作者是John N. Mitchell他在里边提出了一个相当有意思的算法在二进制下可以完全通过加法来近似完成两个数的相乘最大误差不超过1/9。整个算法相当巧妙更有意思的是它还有着非常简洁的编程实现让人拍案叫绝。然而笔者发现网上居然找不到介绍这个算法的网页所以在此介绍一番。你以为这只是过时的玩意那你就错了前不久才有人利用它发了一篇NeurIPS 2020呢所以确定不来了解一下吗快速对数与指数说到乘法变加法大家应该很自然能联想到对数和指数即本文是基于二进制的所以a2。问题在于上式虽然确实将乘法转为加法了但是对数和转换后的指数算起来都不是一件容易的事情。所以要利用这个等式做乘法关键在于要实现快速对数和指数运算。对于十进制的非负数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实现参考如下#includestdio.hint main() {float a 12.3f;float b 4.56f;int c *(int*)a *(int*)b - 0x3f800000;printf(近似结果%f\n, *(float*)c);printf(精确结果%f\n, a * b);return 0;
}
没有C编译环境的朋友也可以找个网页版的在线C运行程序试跑一下测试一下它的结果。就算是不懂C的朋友比如笔者大概也可以感觉到这段代码大概就是转化为两个数相加并且减去一个常数这怎么就能实现乘法了还有的读者可能问Python里边能这样写吗首先后一个问题的答案是不能因为Python的数据类型已经经过了高度封装了而上述C代码的可行性在于浮点数的IEEE754表示法一个十进制浮点数首先会被转化为二进制然后标准化为科学计数法最后用一个特定的结构将科学计数法的结果存下来。具体来说IEEE754用32个0/1表示一个浮点数其中1位表示正负号0为正8位表示科学计数法的指数23位表示科学计数法的小数以9.75为例它的二进制为1001.11写成科学计数法就是这里的10、11都是二进制对应十进制的注意指数部分我们还需要加上偏移量127即3次方实际上存的是130二进制表示为10000010因为前面126个数要用来表示负整数幂而主要部分1.00111由于第一位必然是1因此只需要把0.00111存下来所以9.75背后的表示方式为知道IEEE754表示法之后就可以理解上述代码了*(int*)a和*(int*)b其实就是把a,ba,ba,b的IEEE754表示拿出来当作普通的整数来运算两者相加其实正好对应着Mitchell近似对数后的相加结果但是指数部分会多出一个偏移量所以要减去整个偏移量由于偏移量是127并且后面还有23位所以减去偏移量相当于减去常数127×2^23表示为十六进制就是3f800000因为二进制表示太长了所以计算机一般用十六进制来代替二进制进行IO最后将加减后的结果恢复为浮点数。注其实笔者也不懂C上述理解是东拼西凑勉强得到的如果不当之处请大家指出。最大误差的分析标题写到这个算法的误差不超1/9现在我们就来证明这一点。证明需要全部转换到十进制来理解Mitchell近似实际上是用了如下近似式其中n是整数而x∈[0,1)所以分析误差也是从这两个近似入手。假设两个数为那么根据近似就有可见要分两种情况讨论第一种情况那么近似指数的结果就是因此近似程度就是第二种情况这时候近似指数的结果就是因此近似程度就是可以按部就班地证明上面两种情况的最小值都是在时取到其结果为8/9所以最大的相对误差为1/9如果是除法变成减法那么它的最大误差是12.5%。因为按部就班的证明有点繁琐我们这里就不重复了而是直接用软件画出它的等高线图看出误差最大的地方应该是中心处作图代码import numpy as np
import matplotlib.pyplot as pltx 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是自然对数的一阶泰勒展开式而e2.71828更加接近于3所以如果计算机使用3进制的话本算法会有更高的平均精度。事实上确实有一些理论分析表明对于计算机来说其实最理想是e进制而3比2更接近于e所以三进制计算机在不少方面会比二进制更优我国和前苏联都曾研究过三进制计算机不过由于二进制实现起来更加容易所以当前还是二进制计算机的天下了。搬到深度学习中Mitchell近似的介绍就到这里了。读者可能会困惑这不该是计算机基础和数据机构那一块的东西吗你研究它干嘛还能在深度学习中有什么应用吗笔者学习它的原因有两个一是它确实很漂亮值得学习二是它还真的可以用到深度学习中。事实上笔者是NeurIPS 2020的一篇论文《Deep Neural Network Training without Multiplications》[2]中发现它的该论文在“ImageNetResNet50”验证了直接将神经网络中的乘法换成Mitchell近似的加法形式准确率只有轻微的下降甚至可能不下降。当然作者目前的实现只是验证了这种替换在效果上是可接受的在速度上其实是变慢了的。这是因为虽然从理论上来讲乘法换成近似加法速度一定会有提升但要实现这个提升需要从硬件底层进行优化才行所以作者是提供了未来深度学习硬件优化的一个方向吧。此外Mitchell近似在深度学习中的应用分析也不是第一次被讨论了直接Google就可以搜到两篇分别是《Efficient Mitchell’s Approximate Log Multipliers for Convolutional Neural Networks》[3]和《Low-power implementation of Mitchells approximate logarithmic multiplication for convolutional neural networks》[4]。可能读者联想到了华为之前提出的加法神经网络AdderNet其目的确实有类似之处但方法上其实差别很大。AdderNet是将神经网络的内积换成了距离从而去掉了乘法这篇论文则是修改了乘法的实现降低了乘法的计算量已有的神经网络运算可能都可以保留下来。也把新瓶装旧酒本文介绍了1962年发表的Mitchell近似算法它是一种近似的对数和指数计算基于此我们可以将乘法转化为加法并保持一定的精度。看上去已经过时但将这个算法“新瓶装旧酒”一下就成为了NeurIPS 2020中一篇论文了。所以你还发现了哪些可以装到新瓶的“旧酒”呢后台回复关键词【入群】加入卖萌屋NLP/IR/Rec与求职讨论群后台回复关键词【顶会】获取ACL、CIKM等各大顶会论文集 [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
