CORDIC(Coordinate Rotation Digital Computer)算法即坐标旋转数字计算,这个算法的神奇之处在于它可以借助加减法、移位以及查表完成常见的超越函数(三角函数,反三角函数,对数,开根号)的计算,而不用多项式展开或者浮点数的计算。
原理
所谓坐标旋转可以理解为在例如直角坐标系下的通过旋转矢量完成求解,对于一个坐标(x,y) 可以由初始(x_0,y_0)通过旋转矩阵得来,即
以计算正弦和余弦为例,CORDIC算法是预先求出(1/2)^n的反正切制成一个表,当我们输入一个预期角度时,通过比较当前角度与预期角度的大小确定旋转的方向d(仅代表正负符号),然后计算
巧妙的一点是,(1/2)^n恰好可以用右移来完成,而cos(theta)则是作为一个缩放因子,在迭代次数固定时也可以累乘预先计算。
这个迭代每次都会查表并且把反正切对应的角度加入当前角度,直到指定的迭代次数。这时计算出的角度应该非常接近对应角度,而旋转出的x_(n+1),y_(n+1)则应该是分别对应经过缩放的正弦值和余弦值。