乗算なしで sin を計算する：CORDIC の話

sin や cos を計算するとき、ソフトウェアならライブラリに任せればいい。でも FPGA や古いマイコンで「乗算器がない」「ルックアップテーブルを置くメモリが少ない」という状況になると、話が変わってくる。

そういう場面で使われるのが CORDIC（Coordinate Rotation Digital Computer）だ。1959年にJack Volderが考案した方法で、加算・減算・ビットシフトだけで三角関数を計算できる。

核心アイデア：回転の分解

2Dのベクトル回転を思い出すと：

\begin{pmatrix} x' \\ y' \end{pmatrix} = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}

このまま計算すると cos と sin の乗算が必要になる。CORDICのアイデアは、この回転を「少しずつ近づけていく」形に分解することだ。

具体的には、回転角 $\theta_i = \arctan(2^{-i})$ の回転を繰り返す。 $i = 0, 1, 2, \ldots$ と増やしていくと、各ステップの回転角はどんどん小さくなる。このステップ角は事前に計算してテーブルとして持っておける。

各ステップでは、現在の角度の残差を見て「正方向に回すか、負方向に回すか」を $d_i \in \{+1, -1\}$ で決める：

x_{i+1} = x_i - d_i \cdot 2^{-i} \cdot y_i

y_{i+1} = y_i + d_i \cdot 2^{-i} \cdot x_i

z_{i+1} = z_i - d_i \cdot \theta_i

$z_i$ は「残り何ラジアン回せばいいか」を追跡する変数で、 $z_i > 0$ なら正方向（ $d_i = +1$ ）、負なら逆方向（ $d_i = -1$ ）に回す。 $2^{-i}$ の乗算はビットシフトで実現できるから、ここで乗算器は不要だ。

スケーリング定数

ただし、ここに一つ罠がある。上の式をよく見ると、 $\cos(\theta_i)$ で割ることをサボっているため、各ステップで $1/\cos(\theta_i)$ 倍ずつスケールが乗ってしまう。 $n$ ステップ繰り返すと：

K_n = \prod_{i=0}^{n-1} \frac{1}{\cos(\arctan(2^{-i}))}

$n \to \infty$ の極限でこれは約 $1.6468$ に収束する。つまり、CORDIC の出力には定数スケールがかかっている。あらかじめ初期値を $1/1.6468 \approx 0.6073$ にしておくか、最後にスケール補正を入れればいい。

使い方：2つのモード

CORDICには2つの使い方がある。

回転モード（Rotation mode）：目標角度 $z_0 = \theta$ として $(x_0, y_0) = (K^{-1}, 0)$ から始めると、収束後に $(x_n, y_n) \approx (\cos\theta, \sin\theta)$ が得られる。

ベクトリングモード（Vectoring mode）： $z_0 = 0$ として任意のベクトルを初期値に入れると、 $y$ 成分がゼロに近づくようにアルゴリズムが動く。収束時の $z_n$ に元のベクトルの角度 $\arctan(y_0/x_0)$ が入る。逆三角関数や極座標変換に使える。

なぜ今でも使われるのか

FPGA では今でも CORDIC が選ばれることがある。乗算器を消費しないから、リソースの使い方として合理的な場面がある。

ただ最近は DSP スライスが豊富な FPGA だと、素直に乗算とテーブルを使う実装のほうが速くてシンプルになることも多い。CORDIC は「乗算器が貴重だった時代の産物」という側面もあるかもしれない。でも収束の仕組みが数学的にきれいだし、引数がほぼどんな値でも動くという柔軟性は今でも価値があると思う。

ビットシフトの積み重ねで任意の角度に収束していく様子は、一度プログラムで動かしてみると面白い。数ステップで急速に精度が上がっていくのが視覚的にわかる。

— ランキン