By Long Luo
任何一款科学计算器上都可以计算三角函数,三角函数应用于生活工作中的方方面面,但计算机是如何计算三角函数值的呢?
三角函数本质上是直角三角形的3条边的比例关系 ,计算并没有很直观,那么计算机是如何计算三角函数值的呢?
在微积分中我们学习过 泰勒公式 ,我们知道可以使用泰勒展开式来对某个值求得其近似值,例如:
sin ∠ 1 8 ∘ = 5 − 1 4 ≈ 0.3090169943 \sin \angle 18^{\circ} = \frac{\sqrt {5} - 1}{4} \approx 0.3090169943
sin ∠ 1 8 ∘ = 4 5 − 1 ≈ 0 . 3 0 9 0 1 6 9 9 4 3
利用泰勒公式,取前 4 4 4 项:
sin x ≈ x − x 3 3 ! + x 5 5 ! − x 7 7 ! \sin x \approx x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!}
sin x ≈ x − 3 ! x 3 + 5 ! x 5 − 7 ! x 7
代入可得:
sin ∠ 1 8 ∘ = sin π 10 = π 10 − 1 6 ( π 10 ) 3 + 1 120 ( π 10 ) 5 − 1 5040 ( π 10 ) 7 ≈ 0.30903399538 \sin \angle 18^{\circ} = \sin \frac{\pi}{10} = \frac{\pi}{10} - \frac{1}{6} (\frac{\pi}{10})^3 + \frac{1}{120} (\frac{\pi}{10})^5 - \frac{1}{5040} (\frac{\pi}{10})^7 \approx 0.30903399538
sin ∠ 1 8 ∘ = sin 1 0 π = 1 0 π − 6 1 ( 1 0 π ) 3 + 1 2 0 1 ( 1 0 π ) 5 − 5 0 4 0 1 ( 1 0 π ) 7 ≈ 0 . 3 0 9 0 3 3 9 9 5 3 8
可见取前 4 4 4 项时精度已经在 1 0 − 5 10^{-5} 1 0 − 5 之下,对于很多场合精度已经足够高 了。
在没有了解 CORDIC(Coordinate Rotation Digital Computer) Algorithm 算法之前,我一直以为计算器是利用泰勒公式去求解,最近才了解到原来在计算机中,CORDIC 算法远比 泰勒公式高效。
下面我们就来了解下泰勒公式的不足之处和 CORDIC 算法是怎么做的。
泰勒公式的缺点
上一节我们使用泰勒公式去计算三角函数值时,需要做很多次乘法运算,而计算器中乘法运算是很昂贵 的,其缺点如下所示:
展开过小则会导致展开精度不够,展开过大则会导致计算量过大;
幂运算需要使用乘法器,存在很多重复计算;
需要很多变量来存储中间值。
在之前的文章 矩阵乘法的 Strassen 算法 ,就是通过减少乘法,多做加法 ,从而大大降低了运算量,那么我们可以用相同的思想来优化运算吗?
当然可以,让我们请出今天的主角:CORDIC 算法 。