1980年，英特尔推出8087，让IBM PC等系统的浮点运算快了一大截。这颗芯片的正切指令背后，用的是一套把两种算法拼起来的方案。
三角函数计算有两条常见路子。一条叫CORDIC，另一条是多项式逼近。8087把两者结合，同时拿到了高精度和高性能。相比8086微处理器，它的提速相当夸张：算一次正切只要90微秒，而不是13000微秒。
要弄清正切指令FPTAN背后的算法，得先看芯片的电路和微码。有人用凿子撬开芯片顶盖，再用显微镜拍出高分辨率图像。微码ROM是芯片中央那块大矩形区域，装着控制整颗芯片的1648条微指令。芯片下半部分（红框）是数据通路，负责对80位数值做浮点计算。
数据通路里有什么
放大数据通路，能看到几个关键功能单元。指数ROM存放算法需要的固定指数值；常量ROM存放常量，其中包括CORDIC算法用到的那些常量。移位器是个大部件，能把64位值左右移动任意位数。加法器是8087计算的核心，除了加减，还被用在循环里做乘法、除法和平方根。B寄存器保存加法器的一个输入，另一个输入可以有多个来源。和寄存器保存加法器的输出。八个栈寄存器和临时寄存器存放浮点数。移位寄存器则保存CORDIC计算用的16个状态位。
CORDIC是怎么来的
CORDIC是个巧妙的算法，用简单硬件就能快速算超越函数：靠移位、加法和查表，不需要乘法或除法。它诞生于1956年，最初是为B-58 Hustler研制的——那是第一架能以2马赫飞行的轰炸机。飞机上装的是模拟导航计算机，但模拟元件精度有限。工程师Jack Volder接到的任务，是设计一台数字计算机来替换模拟计算机。
一个关键难题是：模拟计算机用叫分解器的机电装置就能轻松生成正弦和余弦，但三角函数在数字电路里很难做，尤其在那个晶体管还很慢的年代。Volder想出了用简单硬件快速计算三角函数的方法，他把算法和实现它的计算机都命名为CORDIC，即"坐标旋转数字计算机"。
CORDIC把角度转成向量，向量的坐标就给出所需的三角函数值。诀窍在于把角度拆成一串特殊角度，这些角度能让向量旋转变得容易。特殊角度预先算好存在表里，所以即使在1950年代的硬件上，CORDIC计算也能跑得很快。每次迭代多提供一位精度，算法收敛得很快。CORDIC后来流行起来，科学计算器也在用，只不过用的是十进制CORDIC而非二进制。
角度怎么变成坐标
三角函数和点的坐标关系很直接。给定角度θ，它对应单位圆上一点(X, Y)，基本公式是X=cos θ、Y=sin θ、Y/X=tan θ。所以只要能确定坐标(X, Y)，就能确定三角函数值。如果点不在单位圆上，比如(X', Y')，仍然能轻松求出tan θ——8087做的正是这件事。但这时sin θ和cos θ就变得麻烦了。
做过计算机图形的人大概见过旋转矩阵怎么把点旋转一个角度。把点(X, Y)乘上旋转矩阵，就得到新点(X', Y')。麻烦在于旋转矩阵本身需要sin和cos，看起来帮不上忙。把矩阵除以cos θ也没好到哪去，因为矩阵里出现了tan，而这正是想求的东西，而且向量长度还会变长。
CORDIC的关键是使用特殊角度αn = arctan(2⁻ⁿ)。把这种特殊角度代入矩阵，得到的矩阵在硬件里很容易算：乘以2的幂，移位就行。把结果作用到点(X, Y)上，得到的方程只涉及加法、减法和二进制移位，在机器语言或硬件里都又快又简单。
有了这些铺垫，CORDIC的流程就清楚了。先把输入角度拆成一串特殊角度的组合，让它们加起来等于目标角度。然后从单位向量(1, 0)出发，对每个特殊角度套用上面的旋转公式。最后得到的点(X, Y)就落在目标角度上，所求的正切就是Y/X。由于特殊角度表是预先算好的，arctan运算并不会拖慢整个过程。顺带一提，特殊角度在头几项之后会趋近于2⁻ⁿ，所以每一步大约缩小一半。
热门跟贴