２. 式の変形
N の値が特別な場合には，上記の式をうまく変形することによって，これらの計算を効率よく行えるはずである。ここでは，(A-1) 式の変形を行うことにする。（(A-2) 式については，(A-1) 式とほぼ同様の変形が行えるだろう。）
ただし，ここでの変形は，主に N の値が 2 の累乗( 2s の形)のときに『効率が良い』ものであって，その他の場合では，必ずしも最も『効率が良い』わけではないことを注意しておく。[→A. 参考文献など (2)]
なお (B) からは，以下のような関係式が得られる。(ただし α,β≠0)
 ………(B-1a)
 ………(B-1b)
 ………(B-1c)
(1) N が整数 α(α≧2) で割り切れるとき (２個の整数の積に分解)
N／α も整数だから，(A-1) 式の k , n について，
とおけて，このとき (A-1) 式は次のように変形できる。
ここで (B-1a, b) を使うと，
 ………(C-1)
(A-1) では，W の計算を除くと，N2 回程度の複素数の掛け算があるのに対し，(C-1) では，
 のところで αN 回程度,
 のところで N2／α 回程度,
なので，通常は，掛け算の回数がかなり減ることになる。したがって，Σ をさらに『分解』していけば，掛け算の回数がどんどん減っていくと思われる。
(2) N が整数 α1,α2(α1,α2≧2) で割り切れるとき (３個の整数の積に分解)
N／α1α2も整数だから，(A-1 )式の k , n について，
とおけて，このとき (A-1) 式は，(C-1) 式と同様の手順を踏めば，次のように変形できる。
 ………(C-2)
(3) N = α1α2 ……αs, (α1,α2,……,αs≧2) のとき (s 個の整数の積に分解)
(1) (2) と同様にすれば，(A-1) 式の k , n について，
とおけて，このとき (A-1) 式は，次のように変形できる。
………(C)
ここで，(C) 式の W の部分に着目する。
nm (2≦m≦s) の和をとるところの W の部分は，(B-1b) を使って次のように変形できる。
こうすると，例えば，αm= 2, 4, 8のとき，(C) 式の計算量がかなり減るのがわかるだろう。
なぜなら，(B-1c) 式からわかるように  をかけることは，
- ・符号を変える。
- ・複素数の実部と虚部の加減算をする，入れ替える。
- ・少しだけ掛け算をやる。
にほかならず，残りの部分，
は km によらない数になっているからである。また，
(α1α2…αm-2km-1+……+α1k2+ k1)nm ＜α1α2…αm
であることに注目しよう。これは, を考えなければ，計算に使う W の値は，せいぜい N 個の複素数を用意しておけば良いことを示している。
ここで (C) 式を次のように変形しておく。
………(C-a)
(C-a) 式からわかるように， から計算をしていくと， ， と進むにつれて，『n の変数』が(n1から)減り，それにともない『k の変数』が(k1から)増えているのがわかる。
以上は，W の指数部を nm についてまとめた場合であるが，今度は km についてまとめてみる。
このとき，(C-a) に相当する式は次のようになる。
………(C-b)
なお nm の和をとるところの W の部分
は，nm によらない数になっている。また，
km(nm+1αm+2…αs-1αs+……+ns-1αs+ns) ＜αmαm+1…αs-1αs
だから， を考えなければ，計算に使う W の値は，せいぜい N 個の複素数を用意しておけば良い。このことを含めその他のことも，(C-a) 式のときと同様である。
さて，以上のことをふまえて (C-a, b) 式から， 実際の計算で使いやすいであろう漸化式を作ってみる。
|
TOPページ