Arctan的快速近似算法

博客:博客园 | CSDN | blog

写在前面

如果$arctan$的计算成为了瓶颈,那么是时候对其进行优化了。

Arctangent.png
Arctangent.png

$arctan$的近似计算本质上是在所需精度范围内对$arctan$曲线进行拟合,比较直接的想法是泰勒展开

根据需要的精度,确定展开多少项,但$arctan$的泰勒展开在$x$接近1时,收敛较慢,并不高效。

另一个直接的想法是查表,根据所需精度,正切值定点化后,将其对应的角度保存成表,计算时,根据最近的正切值查表,一般需要较大的内存空间。

需要注意的是,$arctan(x)$返回的是$(-\pi/2, \pi/2)$, $arctan2(y, x)$返回的范围是$(-\pi, \pi ]$,因为后者可以根据$x$和$y$的正负确定位于哪个象限。实际上,只需近似或存储$[0, \pi/4]$即可(即八象限中的第一象限),若输入向量$(x, y)$,根据$x$和$y$的正负和大小关系,可以折算到所有的八个象限。

此外,CORDIC(COordinate Rotation DIgital Computer)算法也是个选择,仅涉及移位和加法操作,但仍需要迭代。

Arctan快速近似计算

这里,罗列paper 《Efficient Approximations for the Arctangent Function 》中的7种近似算法,这些近似算法通过Lagrange interpolation和minimax optimization techniques得到,最大近似误差和所需计算如下所示,

error-and-computational-workload.png
error-and-computational-workload.png

从上到下依次为,

  • 线性近似,最大近似误差 $0.07 \ rad = 4^{\circ}$,
  • 二阶近似,最大近似误差 $0.0053 \ rad = 0.3^{\circ}$,
  • 搜索更佳的系数,最大近似误差 $0.0038 \ rad = 0.22^{\circ}$,
  • $\alpha x^{3}+\beta x$形式的三阶近似,最大近似误差 $0.005 \ rad = 0.29^{\circ}$,
  • $x(x-1)(\alpha x-\beta)$形式的三阶近似,最大近似误差 $0.0015 \ rad = 0.086^{\circ}$,
  • $x /\left(1+\beta x^{2}\right)$形式的近似,最大近似误差 $0.0047 \ rad = 0.27^{\circ}$,
  • 另一个近似,最大近似误差 $0.0049 \ rad = 0.28^{\circ}$,

实际使用时,可先定点化,按需选取。

以上。

参考

0%