CORDICアルゴリズムが私の心の中にただで住みついている理由
Fixed Pointを使ってFloating Pointを回避
- Floating PointではなくFixed Pointを使うことで実数を表現できる
- 32ビット整数型を使い、上位16ビットを整数部、下位16ビットを小数部として分けて使う
- これにより約 -32768.99997 から 32767.99997 まで表現可能
- プログラマが小数点の位置を指定して精度を調整できる
- FloatをFixed Pointに変換するには 2^16 を掛けてから
int32_t にキャストする
- Fixed PointをFloatに変換するには 2^16 で割る
- 加算と減算はそのまま動作し、乗算と除算はScaling Factorを調整する必要がある
CORDICアルゴリズム概要
- CORDICは "Co-ordinate Rotation Digital Computer" の略で、1950年代半ばに開発された
- 単位円上のベクトルを段階的に小さな角度で回転させてサインとコサインの値を求める方法
- 二分探索に似ており、目標角度に近づくように大きな角度で移動した後、時計回りまたは反時計回りに角度を半分ずつ減らしながら収束する
- 最大回転角を90度（π/2 radian）とし、16回反復して目標角度に近づけて収束させる
- 収束したベクトルのy値はおおよそ
sin(a) であり、x値はおおよそ cos(a) である
定数乗算だけを使うように行列を単純化
- 回転行列にはサイン、コサイン、タンジェント関数が含まれており、計算が複雑になる
- タンジェント関数は固定角で回転するため、あらかじめ計算してテーブルに保存できる（約64バイト程度）
- コサイン項はすべての反復で発生するが、収束値が定数（約 0.6366）なので最後に1回だけ掛ければよい
ShiftとAdd演算だけを使う
- タンジェント関数に使う角度をアークタンジェント関数で
2^-i の値として選ぶ
- これにより乗算をビットシフト演算で置き換えられる
- コサイン項の収束値も再計算して約 0.60725 となり、初期ベクトルのx値として設定する
- CORDICアルゴリズムの各反復は次のように単純化される
- zが0以上なら反時計回りに回転（xから
y>>i を引き、yに x>>i を足す）
- zが0未満なら時計回りに回転（xに
y>>i を足し、yから x>>i を引く）
- テーブルから角度値を引くか足してzを更新する
- これにより定数乗算とビットシフト、加算演算だけで三角関数を計算できるようになる
GN⁺の意見
- CORDICは、組み込みシステムやFPGAなど、限られたハードウェア資源しか持たない環境で有用に活用できるアルゴリズムに見える。特に浮動小数点演算がサポートされていない場合には検討する価値がある方法。
- タンジェント関数の角度を戦略的に選んで乗算をビットシフトに置き換えるアイデアが印象的。数学的な洞察とコンピュータアーキテクチャへの理解が結びついた好例。
- 三角関数だけでなく、対数、指数、平方根など多様な関数計算にも活用できる点も興味深い。関連アルゴリズムであるBKMもあわせて見てみるとよさそう。
- ただし最新のハードウェアにはすでにFPUが内蔵されている場合が多く、固定小数点演算を使うと精度損失が生じる可能性があるため、適用時には注意が必要に思える。
- 似たような計算を大量に実行するシステムであれば、CORDIC専用ハードウェア設計を検討してみるのもよさそう。
1件のコメント
Hacker Newsの意見
CORDICアルゴリズムはFPGAだけでなく、ゲーム開発や分散物理シミュレーションなどにも活用できる。浮動小数点演算はプラットフォーム間で決定論的な動作を保証しにくいため、固定小数点の物理エンジンを実装し、CORDICで三角関数を実装することが一つの解決策になりうる。
CORDICはサイン、コサインだけでなく、対数、指数、平方根、ベクトルの大きさ、極座標-直交座標変換、ベクトル回転など多様な演算に活用できる。クォータニオンを使えば、CORDICベースの演算をより効率的かつ正確に実行できそうだ。
高校のプレ微積分の授業で電卓の三角関数実装について学んだが、テイラー級数ではなく実はCORDICだったと知り、TI Basicで自分で実装してみた体験談の共有。
2023年時点ではSTM32G4のような低価格MCUにもFPUが内蔵されており、固定小数点の代わりに浮動小数点を自由に使える。しかしG4には専用ハードウェアとして実装されたCORDIC周辺機器もあり、これは浮動小数点の精度損失を避けるためのものと思われる。
22.75°の回転は45°回転の後に-22.5°回転するのと同じ、という説明には誤りがあるように思える。22.5°が正しいようだ。
Meagherのオクツリーシステムは、整数の乗算・除算なしに整数演算だけで実装されていた。これはオクツリー表現のための高速で専用設計のVLSIグラフィックスアクセラレータハードウェアの製作を容易にする。
CORDICは、角度に対するFarey数列（あるいはmediant、素朴な分数和）に似た概念と見ることができる。
CORDICは4ビットCPUを搭載したビンテージのプログラマブルHP電卓でも実装されていた。サイン関数のテイラー展開を使った近似法もプログラミング可能だ。
この記事が気に入ったなら、数学アルゴリズムを例とともに解説したドナルド・クヌースの名著『The Art of Computer Programming』を読んでみるのもよい。
CORDICは、かつてDSP分野で大きな人気を集めたアルゴリズムだ。
すばらしいアルゴリズムであり、低性能なハードウェアでニューラルネットワークを実行するのに役立ちそうだ。