FFT 4

Complex配列の代わりに、VirtualArrayという仮想的な配列クラスを作り、それを引数に取るようにした。VirtualArrayはDelegateを使って、配列を読み書きするクラス。なんでこんなものを作ったかというと、入力が関数でかけるものだったら、いちいち配列にするのは無駄だし、もっと必要だったのは、多次元配列の添え字の順番を変える必要に遭遇して、配列をいちいち書き換えるより、順番を変えて読み込む関数を作ったほうがメモリの節約になるからである。暗黙的にComplex配列からVirtualArrayにキャストできるようにしてある。このクラスのおかげで、コードがすっきりした。VirtualArrayのソースは載せていないが、コメントがあれば載せてもよい。そもそもこの日記どんな人に読まれているのだろう。。。w
ほかにPrimeFactorArgorithmで整数論が必要だったため、静的クラスIntegerLibraryを作った。このクラスには、素因数分解をする関数、ユークリッドの互除法で最大公約数を求める関数、拡張ユークリッドの互除法で最大公約数と整数的逆数をもとめる関数を作った。
PrimeFactorFFTはN1,N2を互いに素な自然数として、N=N1*N2とかけるときにN1とN2のFFTに分解できるというアルゴリズムである。Wikipediaの英語版にあったので実装してみた。N=N1*N2*N3*...でも作れるはずなので、作ってみよう。他にもアルゴリズムが乗っていたが、知識がたらなさそうだったので組んでいない。分かるのもあったが、計算量的には無駄が多いので、興味がなかった(爆)
まだまだ付け加えていきます。