inamori https://blog.hatena.ne.jp/inamori/ inamori’s diary https://inamori.hateblo.jp/ 数学 プログラミング C++ 大きな整数の掛け算にはFFTを使うとよいのだそうだ。多項式の掛け算を考えればよい。 f(x) = a0 + a1x + ... + amxm g(x) = b0 + b1x + ... + bnxn 各項の係数は、畳込みで計算できる。畳込みはフーリエ変換すると単なる掛け算に変わる。これをまた逆変換する。計算量は、項数をnとすると、ふつうに掛け算すればO(n2)。フーリエ変換にFFTを使うと、O(nlogn)程度（本当は違うらしいが、実用的には問題ないだろう）なので、こちらのほうが速くなる。しかし、整数のフーリエ変換はどのようにしたらいいのだろうか。 そう思って検索してみたら、やっぱり実数計算し… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finamori.hateblo.jp%2Fentry%2F20090302%2Fp1" title="整数のフーリエ変換（1） - inamori’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2009-03-02 00:00:00 rich https://inamori.hateblo.jp/entry/20090302/p1 1.0 100%