CORDICアルゴリズム

質問

こんにちわ、sohです

三角関数をビットシフト演算と加減算のみで求められるという噂をききつけ
CORDICアルゴリズムを調べてたんですが いまいちよくわからないんです（T^T
やっぱり複素数平面をちゃんと勉強しなおさないと理解不能？（＾＾；

誰か簡単に説明していただけないでしょうか？

とりあえずマイクロな（浮動小数点無しで非力なCPU＆きつきつなメモリ)環境にて
θ もしくは radianからsinθ（or radian)の値を有効小数点桁２桁くらいまでで、高速に求められば目的は達成できるのですが・・・・

回答No.2

noname#11476 · ベストアンサー

昔なつかしのアセンブラーで色々遊んだことを思い出しました。
固定小数点でインラインアセンブル使ってずいぶん高速処理させましたねぇ。

では、理論はおいておいて、簡単に。
まず、テーブルを用意します。
double delta, x;

/* make table */
delta = 1.0;
for (i = 0; i < 10; i++) {
　tbl[i] = atan(delta);
　delta = delta / 2.0;
};

計算は、いま与える角度をa[radian]とすると、
int i;
double x, tmp, y, z, d, s;

x = 0.607252935;
y = 0.0;
z = a;
d = 1.0;

for (i = 0; i < 10; i++) {
　if ( z > 0.0 ) s = -1.0; else s = 1.0;
　tmp = x + s * d * y;
　y = y - s * d * x;
　x = tmp;
　z = z + s * tbl[i];
　d = d / 2.0;
};

これで、xにはcosの値、yにはsinの値です。
n = 10位で２桁位の精度は出るでしょう。
あとは、上記を見ればわかるとおり、乗算部分はビットシフトで計算できますから、固定小数点にするなり、ぎりぎりまで繰り返し回数を減らすなりしてください。
あ、ちなみに計算する角度の範囲は０～９０degreeにしておきます（つまり第1象限）。
それ以外はx, yから計算できますよね。

では。

お礼

回答ありがとうございます。

あぁ、なーるほど
ソースがあるとどういうシーケンスで動くのかわかりますわ（笑
まじでサンクスです。

始めのテーブルは回転角度を入れとくためのテーブルで
目標とする角度の近似になるよう収束させるんですね。

＋－のぶれを
if ( z > 0.0 ) s = -1.0; else s = 1.0;
で修正しつつ収束させると。
テーブル作成部分も一応ビットシフトで高速化ができるかな、ってあれ・・・・？
テーブル作成時に　arctan使わんといかんのですか。
ん～っと。。。　そうか収束させるための回転角度の計算してるんですよねこのテーブル。
むむむ～～～、atanも持ってないから仕方ない
データ数12個くらいのテーブルなら作っても大してメモリ圧迫しないで済むからつくっちゃうしかないのかなぁ？

＞あとは、上記を見ればわかるとおり、乗算部分はビットシフトで計算できますから

ごめんなさい、ここがわからない
tmp = x + s * d * y;
　y = y - s * d * x;

を tmp = x + ((s * y) >> d);
　y = y - ((s * x) >> d);
d ++;
にできるのはわかったんですけど、他にビットシフトで対応できる個所ってどこなんでしょうか？