CORDIC

CORDICでsin/cosを求める方法をちょこっと使ってみようと、お勉強したのでまとめ。

点(x, y)から点(x', y')への角度θの回転＋r倍の拡大変換は、
\begin{pmatrix} x' \\ y' \end{pmatrix} = r \begin{pmatrix} cos \theta & sin \theta \\ -sin \theta & cos \theta \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}
となる。

(x, y)=(1, 0), r=1としてx', y'を計算すると、cos θ=x', sin θ=y'と、sin, cosを同時に求めることが出来る。

角θを
\theta=\sum \limits_k \theta_k
と分解すると、
\begin{pmatrix} x' \\ y' \end{pmatrix} = r \prod \limits_k \begin{pmatrix} cos \theta_k & sin \theta_k \\ -sin \theta_k & cos \theta_k \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}
となる。

ここで、 \theta_k=arctan 2^{-k}とおくと、
\begin{pmatrix} cos \theta_k & sin \theta_k \\ -sin \theta_k & cos \theta_k \end{pmatrix} = cos \theta_k \begin{pmatrix} 1 & 2^{-k} \\ -2^{-k} & 1 \end{pmatrix}
となり、上式は
\begin{pmatrix} x' \\ y' \end{pmatrix} = r \prod \limits_k cos \theta_k \prod \limits_k \begin{pmatrix} 1 & 2^{-k} \\ -2^{-k} & 1 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}