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 ++;
にできるのはわかったんですけど、他にビットシフトで対応できる個所ってどこなんでしょうか？

回答No.3

noname#11476

>テーブル作成時に　arctan使わんといかんのですか。
そうなんですよ。でもこのテーブルは与える角度には関係なく一定だから数個くらいなのテーブルで持つしかないですね。
（要求精度にもよるけどsohさんの場合なら10個程度だから)
このテーブルは1/2^(n-1)で小さくなるからそんなに沢山必要ないですよね。

あとは、
if ( z > 0.0 ) s = -1.0; else s = 1.0;

tmp = x + s * d * y;
y = y - s * d * x;
上記の式で、sは結局 +1 or -1 だから上のifに入れ込むと sub,addどちらかを使うようにすれば s* はいらないですよね。
d はお気づきのようにシフト演算ですね。

x = tmp;
z = z + s * tbl[i];
ここの掛け算も +1, -1 だから ifの中に入れてしまえば掛け算はいらない。

d = d / 2.0;
これはシフト演算に吸収されると。

となると結局 s* は add　か　sub に分岐すればよくてなくなるし、 d* はシフト命令になってひとつも乗算はなくなるわけですね。

z の符号はMSBのbit見てあげればよいだけだから簡単だし。

では～。

お礼

な～るほど、Zの符号も確かに第一bitで判定できますね
気が付かなかった！

うぅ～ん、奥が深いなぁ
度重なる質問にも丁寧にお答えいただきありがとうございましたm(__)m

回答No.1

imogasi

読んだ人は「一体何のこっちゃ」と思いますでしょう。私も全然判らないものですが、引っかかっチャッた。
下記のページを読ませて頂いて、何をおしゃっているのか判りました。
● http://www.inh.co.jp/~inasaims/cordic/cordic.html
引用「つまり、 1, 1/2, 1/4, 1/8, 1/16, ......
この部分の計算が、ビットシフトだけで実現できるのがCORDICのミソです。
つまり、計算自体が、ｘ’＝ｘ＋1/(2^n)y、のように
ビットシフトと加算だけで非常に簡単にできるようになっています.」
●昔アッセンブラを使っていた時、ビット演算を良く使いましたが　、レジスター等で1ビットシフト左シフトは２倍に、（回転式でない内）右シフトは１／２になりますよね。シフト回路は組みやすい。加算回路も基本的で、２種類の回路ロジックで済めば、組みこみ回路に重用される気がします。
●上記ページに出てきた恒等変換の回転式に対比された、
回転マトリックスのｇの［１　－ｐＤ、ｐＤ　１］、Ｄ＝１／２＾（ｎ－１）
の意味が（なぜＳＩＮの値を出せるのに使えるのか）判れば良いのでしょうね。疑問掲載分野としては、数学系の方が適当では？あとは専門家さまよろしく。

お礼

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

うん、わしもそのページは見つけて
いみわから～ん　って感じだったんですよ（＾＾；
数学とどっちにしようかも悩んだんですが
1970年代に一世を風靡したアルゴリズムらしいのでプログラミング関係にしとこっかなぁ・・　って。
そんな考えだったんですけど、やっぱり数学にしとけばよかったかしら。。。。