数学の記事一覧

数論変換(NTT)を用いた多項式乗算 ① 〜離散フーリエ変換と多項式乗算〜

この記事は数論変換(NTT)を用いた多項式乗算について 1 から丁寧に解説することを目標としています。この記事を書こうと思ったきっかけは学校で｢円周率を 1000 桁計算する｣というレポートが出たからです。いわゆる多倍長演算のレポートなのですが、乗算の速度をなんとかして上げようと思い、高速フーリエ…