多倍長演算のアルゴリズムに Schönhage-Strassen Algorithm というものがあります。 これは、n桁の数同士の積が畳み込み演算で表わされることから、畳み込み定理を用いて乗算を高速化するアルゴリズムです。 畳み込み定理を利用するために剰余環上で離散フー…

前にFFTの式を導いたので，C++で実装してみました。 前準備 前の記事から，をデータ数としてDFTした結果は と書くことができます。 なお，，です。 このまま実装してもいいですが，これだと少しわかりにくいしやりにくいので少し式を書き換えます。 まず，2…

FFTについてgoogle先生にお聞きしてみると，実装できるところまで解説したらおしまい，という形をとってるものが多い気がします。 実際，実装できればいいというのはそのとおりだと思いますが，やはりアルゴリズムの理解という意味では自分で手を動かして計…