三角学
历史（英语：History of trigonometry） 三角函数 (反三角函数) 广义三角函数（英语：Generalized trigonometry）
参考
恒等式 精确值 三角表（英语：Trigonometric tables） 单位圆
定理
正弦 余弦 正切 余切 勾股定理
微积分
三角换元法 积分 (反三角函数) 微分
查 论 编

CORDIC（英语：Coordinate rotation digital computer），也称为Volder算法（英语：Volder's algorithm），是一个可以计算三角函数，简单且有效率的算法，可以在任意进制下运算，一般会每次计算一位数字。因此CORDIC属于逐位计算（Digit-by-digit）方法中的一个例子。

CORDIC算法还有其他的名称，像是圆形CORDIC (Jack E. Volder)^[1][2]、线性CORDIC、双曲线CORDIC(John Stephen Walther)^[3][4]、及泛用双曲线CORDIC（GH CORDIC, Yuanyong Luo et al.）^[5][6]。用类似的方式也可以计算双曲函数、平方根、乘法、除法、指数及对数等。

CORDIC和一些名为“伪乘法”（pseudo-multiplication）、“伪除法”（pseudo-division）及factor combining的方法，常用在没有乘法器的应用（像是简单的微控制器以及FPGA），其中会用到的运算是加法、减法、位元移位及查找表。这些算法可归类在“移位和相加”（shift-and-add）算法中。在计算机科学中，若CPU没有硬件的乘法器，常会用CORDIC来实现浮点数运算。

英国数学家亨利·布里格斯（英语：Henry Briggs (mathematician)）早在1624年时就已发现此算法^[7][8]，后来Robert Flower也在1771年时发现^[9]，不过后来是因为低复杂度的有限状态CPU，才针对CORDIC作较进一步的最佳化。

CORDIC是在1956年问世^[10][11]，是由康维尔空气电子部门的Jack E. Volder（英语：Jack E. Volder）发现，一开始是因为要取代B-58轰炸机（英语：B-58 Hustler）导航电脑上面的类比式解角器（resolver），更换成更准确而实时的数位方案^[11]。因此，有时也会将CORDIC称为数位解角器（digital resolver）^[12][13]。

Volder的研究，是因为1946年版CRC化学和物理手册中的公式而得到灵感^[11]：

${\displaystyle {\begin{aligned}K_{n}R\sin(\theta \pm \varphi )&=R\sin(\theta )\pm 2^{-n}R\cos(\theta ),\\K_{n}R\cos(\theta \pm \varphi )&=R\cos(\theta )\mp 2^{-n}R\sin(\theta ),\\\end{aligned))}$

其中${\displaystyle \varphi }$是使${\displaystyle \tan(\varphi )=2^{-n))$成立的值，且${\displaystyle K_{n}:={\sqrt {1+2^{-2n))))$。

他的研究最后产生了一个内部的技术报告，提到用CORDIC算法来求解正弦及余弦函数，以及一个实现此功能的原型电脑^[10][11]。报告中也提到用修改版的CORDIC算法计算双曲函数、座标旋转、对数及指数的可能性^[10][11]。用CORDIC来进行乘法和除法运算的想法也是在此时形成^[11]。依照CORDIC算法的原则，Volder的同事Dan H. Daggett发展了在二进制以及二进码十进数（BCD）之间转换的算法^[11][14]。

CORDIC用简单的移位和相加运算来处理像是三角函数、双曲函数、对数函数、实数及复数乘法、除法、方根计算、线性系统求解、特征值估测、奇异值分解、QR分解等。因此，CORDIC可以用在许多的应用中，像是信号处理、影像处理、通讯系统、机器人学及三维计算机图形等^[15][16]。

若没有硬件乘法器的话，CORDIC一般会比其他算法要快很多，若是用FPGA或ASIC的话，使用的逻辑门也会少很多。

CORDIC是FPGA开发应用程序（像是Xilinx的Vivado）中的标准半导体IP核，而不是使用特殊函数的幂级数实现，其原因是CORDIC IP的通用性，CORDIC可以计算许多不同的函数，而为特定函数开发的乘法器只能计算特定的函数。

另一方面，若有硬件乘法器（例如DSP），查表法及幂级数会比CORDIC快很多。近年来，CORDIC算法常用在生医应用中，尤其是用FPGA实现的应用^{[来源请求]}。

使用泰勒级数的问题是此方法可以产生小的绝对误差，但其中没有良态的相对误差^[17]。其他多项式近似法，例如Minimax近似算法（英语：Minimax approximation algorithm），可以同时控制这二种的误差。

在CPU只有整数运算的古老系统中，会将CORDIC放在其IEEE 754函式库的一部分。现代的通用CPU已有浮点运算暂存器，也有加法、减法、乘法、除法、三角函数、平方根、一般对数、自然对数等，几乎没有用到CORDIC的场合。只有一些有特殊安全性或是时间要求的应用程序才会用到CORDIC。

CORDIC可以用来计算许多不同的函数。以下说明如何在旋转模式（rotation mode）下的CORDIC计算角度的正弦函数和余弦函数，假设角度以弧度的定点格式表示。要找到一个角度${\displaystyle \beta }$的正弦函数和余弦函数，可以在单位圆上找到对应角度的y座标和座标。利用CORDIC，会从以下的向量${\displaystyle v_{0))$开始：

${\displaystyle v_{0}={\begin{bmatrix}1\\0\end{bmatrix)).}$

在第一次的迭代时，向量逆时针转45°，得到向量${\displaystyle v_{1))$。接着继续的迭代，每一次的角度渐渐变小，旋转方向可能顺时针，也可能逆时针，直到得到想要的角度为止。每一次的角度为${\displaystyle \gamma _{i}=\arctan {(2^{-i})))$，其中${\displaystyle i=0,1,2,\dots }$。

若以更正式的方式表示，每一次的迭代就是一次旋转，也就是将向量${\displaystyle v_{i))$乘以旋转矩阵${\displaystyle R_{i))$：

${\displaystyle v_{i+1}=R_{i}v_{i}.}$

旋转矩阵为

${\displaystyle R_{i}={\begin{bmatrix}\cos(\gamma _{i})&-\sin(\gamma _{i})\\\sin(\gamma _{i})&\cos(\gamma _{i})\end{bmatrix)).}$

利用以下两个三角恒等式：

${\displaystyle {\begin{aligned}\cos(\gamma _{i})&={\frac {1}{\sqrt {1+\tan ^{2}(\gamma _{i})))},\\\sin(\gamma _{i})&={\frac {\tan(\gamma _{i})}{\sqrt {1+\tan ^{2}(\gamma _{i})))},\end{aligned))}$

旋转矩阵变成

${\displaystyle R_{i}={\frac {1}{\sqrt {1+\tan ^{2}(\gamma _{i})))}{\begin{bmatrix}1&-\tan(\gamma _{i})\\\tan(\gamma _{i})&1\end{bmatrix)).}$

旋转向量${\displaystyle v_{i+1}=R_{i}v_{i))$就会变成下式

${\displaystyle {\begin{bmatrix}x_{i+1}\\y_{i+1}\end{bmatrix))={\frac {1}{\sqrt {1+\tan ^{2}(\gamma _{i})))}{\begin{bmatrix}1&-\tan(\gamma _{i})\\\tan(\gamma _{i})&1\end{bmatrix)){\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix)),}$

其中${\displaystyle x_{i))$和${\displaystyle y_{i))$是${\displaystyle v_{i))$的分量，若将角度${\displaystyle \gamma _{i))$限制在使${\displaystyle \tan(\gamma _{i})=\pm 2^{-i))$的值，和tangent的乘法就以变成乘（或除）2的幂次，在数位电脑硬件中可以快速的用位元右移或左移来计算。因此上法会变成

${\displaystyle {\begin{bmatrix}x_{i+1}\\y_{i+1}\end{bmatrix))=K_{i}{\begin{bmatrix}1&-\sigma _{i}2^{-i}\\\sigma _{i}2^{-i}&1\end{bmatrix)){\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix)),}$

其中

${\displaystyle K_{i}={\frac {1}{\sqrt {1+2^{-2i)))),}$

且${\displaystyle \sigma _{i))$是用来判断旋转方向的。若角度${\displaystyle \gamma _{i))$为正，则${\displaystyle \sigma _{i))$为+1，否则则为−1。

所有的${\displaystyle K_{i))$因子可以在迭代过程中忽略，最后再一次乘以${\displaystyle K(n)}$因子即可：

${\displaystyle K(n)=\prod _{i=0}^{n-1}K_{i}=\prod _{i=0}^{n-1}{\frac {1}{\sqrt {1+2^{-2i)))),}$

此数可以事先计算好存在表格中，若迭代次数是固定的，只需计算一个常数且储存即可，甚至此修正也可以事先进行，将常数先乘以${\displaystyle v_{0))$，可以节省一次乘法。另外，可以注意到^[18]

${\displaystyle K=\lim _{n\to \infty }K(n)\approx 0.6072529350088812561694}$

因此可以简化算法的复杂度。有些应用会避免修正${\displaystyle K}$，因此此算法本身会带一个增益${\displaystyle A}$^[19]：

${\displaystyle A={\frac {1}{K))=\lim _{n\to \infty }\prod _{i=0}^{n-1}{\sqrt {1+2^{-2i))}\approx 1.64676025812107.}$

在够多次的迭代后，向量的角度会接近想要的角度${\displaystyle \beta }$。以一般的应用来说，40次的迭代（n = 40）已可以有小数10位的精度。

唯一未解决的问题是判断每一次迭代要顺时针旋转或逆时针旋转（选择${\displaystyle \sigma }$的值）。这可以记录每一次旋转的角度，从还需要旋转的角度中减去此一角度，会得到下一个还需要旋转的角度${\displaystyle \beta }$。若${\displaystyle \beta _{n+1))$为正，需要顺时针旋转，否则，就需要顺时针旋转：

${\displaystyle \beta _{0}=\beta }$

${\displaystyle \beta _{i+1}=\beta _{i}-\sigma _{i}\gamma _{i},\quad \gamma _{i}=\arctan(2^{-i}).}$

${\displaystyle \gamma _{n))$的值需要事先计算且记录下来。不过若是小角度，根据小角度近似，在定点数下可得${\displaystyle \arctan(\gamma _{n})=\gamma _{n))$，因此可以节省储存用的空间。

如以上所述，角度${\displaystyle \beta }$的正弦函数为其y坐标，余弦函数为其x坐标。

上述旋转模式的算法，是旋转原来位在x轴上的单位向量。但此算法可以用来旋转角度在−${\displaystyle \pi /2}$及${\displaystyle \pi /2}$之间的任意向量，旋转的方向则依${\displaystyle \beta _{i))$的正负号决定。

向量模式下的算法和旋转模式略有不同。其启始向量的x坐标要为正值，y坐标则为任意值。持续转动的目的是将向量旋转到x轴（因此y座标为0）。每一步里的旋转方向会由y的值决定。${\displaystyle \beta _{i))$的最终值包括了总旋转角度。x的最终值是原向量的大小，再乘以K。因此，可以看出向量模式可以进行直角坐标到极坐标的转换。

Java的Math类别中有scalb(double x,int scale)方法可以实现二进制的移位^[20]，C语言有ldexp函数^[21]，x86处理器有fscale浮点运算^[22]。

from math import atan2, sqrt, sin, cos, radians

ITERS = 16
theta_table = [atan2(1, 2**i) for i in range(ITERS)]

def compute_K(n):
    """
    Compute K(n) for n = ITERS. This could also be
    stored as an explicit constant if ITERS above is fixed.
    """
    k = 1.0
    for i in range(n):
        k *= 1 / sqrt(1 + 2 ** (-2 * i))
    return k

def CORDIC(alpha, n):
    K_n = compute_K(n)
    theta = 0.0
    x = 1.0
    y = 0.0
    P2i = 1  # This will be 2**(-i) in the loop below
    for arc_tangent in theta_table:
        sigma = +1 if theta < alpha else -1
        theta += sigma * arc_tangent
        x, y = x - sigma * y * P2i, sigma * P2i * x + y
        P2i /= 2
    return x * K_n, y * K_n

if __name__ == "__main__":
    # Print a table of computed sines and cosines, from -90° to +90°, in steps of 15°,
    # comparing against the available math routines.
    print("  x       sin(x)     diff. sine     cos(x)    diff. cosine ")
    for x in range(-90, 91, 15):
        cos_x, sin_x = CORDIC(radians(x), ITERS)
        print(
            f"{x:+05.1f}°  {sin_x:+.8f} ({sin_x-sin(radians(x)):+.8f}) {cos_x:+.8f} ({cos_x-cos(radians(x)):+.8f})"
        )

$ python cordic.py
  x       sin(x)     diff. sine     cos(x)    diff. cosine
-90.0°  -1.00000000 (+0.00000000) -0.00001759 (-0.00001759)
-75.0°  -0.96592181 (+0.00000402) +0.25883404 (+0.00001499)
-60.0°  -0.86601812 (+0.00000729) +0.50001262 (+0.00001262)
-45.0°  -0.70711776 (-0.00001098) +0.70709580 (-0.00001098)
-30.0°  -0.50001262 (-0.00001262) +0.86601812 (-0.00000729)
-15.0°  -0.25883404 (-0.00001499) +0.96592181 (-0.00000402)
+00.0°  +0.00001759 (+0.00001759) +1.00000000 (-0.00000000)
+15.0°  +0.25883404 (+0.00001499) +0.96592181 (-0.00000402)
+30.0°  +0.50001262 (+0.00001262) +0.86601812 (-0.00000729)
+45.0°  +0.70709580 (-0.00001098) +0.70711776 (+0.00001098)
+60.0°  +0.86601812 (-0.00000729) +0.50001262 (+0.00001262)
+75.0°  +0.96592181 (-0.00000402) +0.25883404 (+0.00001499)
+90.0°  +1.00000000 (-0.00000000) -0.00001759 (-0.00001759)

实现CORDIC需要的逻辑门大约和乘法器相当，两者都是用位元移位和加法所组合的。要选择乘法器或是CORDIC会随应用而定。若复数以其实部和虚部表示（直角座标），复数乘法会需要进行四次的乘法。但若复数以极座标表示，只要一个CORDIC即可处理，这更适合用在其乘积的量值不重要的应用（例如将向量和单位圆上的向量相乘的情形）。在数位下转换器（英语：digital down converter）之类的通讯相关电路中，常会用到CORDIC。

在Vladimir Baykov的二篇文献中^[23][24]，曾经提到用“双重迭代”（double iterations）来实现反正弦函数、反余弦函数、自然对数、指数函数以及双曲函数。双重迭代中的作法和传统的CORDIC算法不同，传统的CORDIC算法中，迭代变数会在每次迭代时加一。但在双重迭代中，迭代变数会先重复一次，然后才加一。因此双重迭代CORDIC算法的迭代变数会是${\displaystyle i=0,0,1,1,2,2\dots }$，而传统CORDIC算法的迭代变数是${\displaystyle i=0,1,2\dots }$。双重迭代法保证方法的收敛，不过其引数的有效范围会变化。

针对${\displaystyle R}$进制数字系统中，通用的CORDIC收敛问题，可以证明^[25]针对正弦、余弦及反正切函数，每一个i（i = 0或1到n，其中n是位数）进行${\displaystyle R-1}$次迭代就可以保证收敛。若是自然对数、指数、双曲正弦、双曲余弦及双曲反正切函数，每一个i需要进行${\displaystyle R}$次迭代。若是反正弦函数及反余弦函数，每一个i需要进行2 ${\displaystyle R-1}$次的迭代^[25]。

若是双曲反正弦及双曲反余弦函数，每一个i需要进行2R次的迭代。

CORDIC属于“移位及加法”（shift-and-add）的算法，就像Henry Briggs文献提到的对数和指数算法一样。BKM算法（英语：BKM algorithm）也是可以计算许多基本函数的移位及加法算法，是复数平面下对数和指数算法的推广。BKM可以计算实数角度${\displaystyle x}$（以弧度表示）的正弦和余弦，其方式是计算${\displaystyle 0+ix}$的指数，也就是${\displaystyle \operatorname {cis} (x)=\cos(x)+i\sin(x)}$。BKM算法比CORDIC要复杂一些，但其优点是不需考虑比例因子（K）。

• 计算方根的方法（英语：Methods of computing square roots）
• IEEE 754
• 浮点运算器