整数のフーリエ変換(1)

大きな整数の掛け算にはFFTを使うとよいのだそうだ。多項式の掛け算を考えればよい。


f(x) = a0 + a1x + ... + amxm
g(x) = b0 + b1x + ... + bnxn
 f(x)g(x) = \sum_i{a_ib_{k-i}x^k}

各項の係数は、畳込みで計算できる。畳込みはフーリエ変換すると単なる掛け算に変わる。これをまた逆変換する。計算量は、項数をnとすると、ふつうに掛け算すればO(n2)。フーリエ変換FFTを使うと、O(nlogn)程度(本当は違うらしいが、実用的には問題ないだろう)なので、こちらのほうが速くなる。しかし、整数のフーリエ変換はどのようにしたらいいのだろうか。
そう思って検索してみたら、やっぱり実数計算して整数化するらしい。


http://almond.cs.uec.ac.jp/papers/pdf/2004/syunji-VLD.pdf


フィボナッチ数をべき乗の計算で求めるようなものか。


// 本題に関係あるのは最後のみ
// 残りはテンプレート版
#include
#include

using namespace std;

template
struct Fib {
enum { value = Fib::value + Fib::value };
};

template<>
struct Fib<0> {
enum { value = 0 };
};

template<>
struct Fib<1> {
enum { value = 1 };
};

int main() {
const int n = 40;
cout << Fib::value << endl;
cout << (int)(pow( (1 + sqrt(5.)) / 2, n) / sqrt(5.) + 0.5) << endl;
}

だから精度が問題になる。この論文によると、100万桁程度ならいけるらしい。たった100万桁か、という気もする。
ところで、計算量の話はおいといて、整数の範囲でフーリエ変換というのはどうしたらいいのだろうか。