突然ですが、問題です。コンピュータや電卓を使わずに、
人様が任意の角度の三角関数の値を求めるには、
どうするでしょうか。
答え）高校の数学の教科書にもあるように、
適当な基準線から分度器を使って求めたい角度を持つ直角三角形を書き、
その三辺の長さをはかって割り算をする。
ということで、この考えを応用したのが CORDIC です。 とりあえず、基準線の方向として、x 軸上の点 P0(1,0) から出発し、 z 度回転させた点 P (x,y) の座標を求めれば、三角関数の値を求めることができます。 しかし、そのような座標を求めるには回転行列を (x0,0) に掛け合わせる必要があり, そして回転行列を求めるのに sin z や cos z が必要になるので、 堂々めぐりになってしまいます。
そこで一度に座標を求めるのではなく、何度かに分けて座標を求めることを考えます。
例えば, a° 回転を行なう行列を用意します。この行列を P0 ベクトルに n 回掛け合わせれば, na° 回転した点の座標がわかり, そこから cos na, sin na を求めることができます。 これだけでは a°単位の精度しかでませんので, 最後に一次補間
を使って精度をあげます。逆にいうと, この一次補間が使える程度に γ を小さくできるように, a を小さく設定する必要が出てきます。sin (z0 + γ) = sin(z0) + γcos(z0) cos (z0 + γ) = cos(z0) + γsin(z0)
が, 刻み a を小さくすると大きな z の時に余りにも計算時間がかかるので、 こんな間抜けなことはせず, 45 , 22.5 , 11.25 , ... という風に、ai = (90 / 2^i)°の回転を表す行列を用意し、
という形に a を分解します。 そして, 分解した各角度の回転を表す行列を、 基準点の位置ベクトルに順次掛け合わせることによって座標を求めるようにします。 たとえば、30 = 90/4+90/16+90/64+90/256+... と分解できるので、 90/4 , 90/16 , 90/256 … 度の回転を表す行列を掛け合わして P の座標を求めるわけです。 なおこの場合, 最終刻みである an が十分に小さくなるように n の値を決め, その数だけ行列を用意することになります。a=w0 a0 + w1 a1 + w2 a2 + ... + wi ai + .... + wn an where wi = 0 or 1
しかし行列の掛け算を行うとなると、 ひとつの行列の掛け算に整数の掛け算が 8 回必要なので、 無茶苦茶遅そうです。回転行列の対称性を生かせば、 ある程度は減らせそうですが、掛け算がたくさんいるという点では変わりません。 そこで、回転行列そのものを見直すことにします。 回転を表す一次変換は、
と表されます。対角成分が 1 になるように cos ai で割り算して、┌ ┐ ┌ ┐┌ ┐ ┌ ┐ ｜ x'｜ ｜ cos ai sin ai ｜｜ x ｜ ｜ x cos ai + y sin ai ｜ ｜ y'｜=｜-sin ai cos ai ｜｜ y'｜=｜-x sin ai + y cos ai ｜ └ ┘ └ ┘└ ┘ └ ┘
とします。そして、さらに ai = 90/(2^n) ではなく, ai=arctan 2^-n ととれば (ai をこのように定めても任意の角度 x を ai の和で表すことができます), tan ai = 2^-n となるので、┌ ┐ ┌ ┐┌ ┐ ┌ ┐ ｜ x'｜ ｜ 1 tan ai ｜｜ x ｜ ｜ x + y tan ai ｜ ｜ y'｜=cos ai ｜-tan ai 1 ｜｜ y'｜=cos ai ｜-x tan ai + y ｜ └ ┘ └ ┘└ ┘ └ ┘
となり、掛け算をシフトに置き換えることができます。 いうまでもないことですが ai や cos ai は毎回計算するのではなく、 事前に計算しておいてプログラム中にテーブルとして記述しておきます。┌ ┐ ┌ ┐ ｜ x'｜ ｜ x + (2^-n)y ｜ ｜ y'｜=cos ai ｜-(2^-n)x + y ｜ └ ┘ └ ┘
ここで最後に残るのが cos ai のかけ算です。 できることならこいつもなくしたいですね。
ということで, なくしてしまいましょう。
とします。すると, この変換にともなって原点から (x',y') までの距離 r が変化してしまいます。 したがって, この時出てくる (x',y') から cos, sin を求めるには, 単に sin z = x', cos z = y' とすることはできず, r = sqrt(x'^2 + y'^2) を 計算し, x'/r, y'/r を計算する必要が出てきます。┌ ┐ ┌ ┐ ｜ x'｜ ｜ x + (2^-n)y ｜ ｜ y'｜=｜-(2^-n)x + y ｜ └ ┘ └ ┘
かけ算, 平方根, 割算と, 非常に時間のかかりそうな処理のオンパレードですね。 これでは cos ai のかけ算をなくすメリットが完全に消えてしまいそうです。
ところが, この平方根計算などもなくすことができます。 平方根計算がいるのは, 回転処理にともなって r が変化するからです。 そして, 数列 wi の値によって変化の仕方が違うために, 毎回平方根を計算しないといけないわけです。
数列 wi の各要素は 0 か 1 しかとらないので, wi の内容によって r がどう変化するかのテーブルを作ってしまえば, 毎回平方根を計算する必要はなくなります。しかし, この方法ではテーブルは 2^n のオーダーのサイズになるので, 精度を高くしようとするとテーブルが大きくなり過ぎるという問題があります。
ここで問題になるのは r の変化の仕方が wi によって異なるからです。 wi にかかわらず, 常に同じように変化するのであれば r を計算する必要はありません。 そこで, wi = 1 or 0 ではなく wi = 1 or -1 で, つまり
という形に a を分解します。そして, いままでは wi が 0 の時は回転処理を行なわず, 1 の時は ai だけ回転させる, ということを行なっていましたが, これからは, wi が 1 の時は ai, -1 の時は -ai 回転させるようにすることにします。a=w0 a0 + w1 a1 + w2 a2 + ... + wi ai + .... + wn an where wi = -1 or 1
いままでは wi の値によって回転処理を行なったり行なわなかったりしていたので, wi の値によって r の値が変化の仕方が異なり, 毎回 r を求める必要がありましたが, いまは常に変換を行なうので, n 回の変換を行なった時点での r の値は常に一定値 r' = cos a1・cos a2・cos a3・…・cos an になります。
これで平方根はいらなくなりました。 そして, 回転を始める前のスタート地点 P0 を (1, 0) ではなく, (1/r', 0) にとれば割算も必要なくなります。
ということで, sin, cos をほげることができました。 これらの値を割算その他すれば容易に tan, cosh, sinh なども求められます。