起きっぱで眠いテンションに任せて色々書いてみた。

>>33
データ構造は結局どうなってるの？構造決まらないとFFTで積でないよ？
多倍長浮動小数だとしたら指数部を記録しないと。

>>45
そんなことは既に考えられている。というより実質ω^iの全配列を作るようなのは無駄。

>>75
加減乗除のうち加減乗は各要素が整数になることは間違いない。
なので浮動小数を使った一般的なFFTを使っても整数化誤差が例えば0.1未満など保証されていれば問題ない。
除算については除算をどう行うか（筆算のようなやり方か、ニュートン法を使うか）、どの程度の誤差を
認めるか（整数演算でキッチリ末尾までか、浮動小数演算として末尾が１違うくらいは認めるか）次第で変わる。
（>>79を書いてるということは浮動小数型？）

>>90,92-94
自分が引用してきたサイトでも見直して配列と多倍長数とがどう対応してるか再考したほうがいい。
ついでにいうと>>98や>>122の発言を見てるとB進数という言葉を勘違いしてる気がする。

>>120-122
N(要素数)が任意でp固定なんてあり得ない。ωは1の原始p乗根のはずなのでFFTに使う要素数は
p-1で固定しなきゃいけない。ということはNがどんなに小さくてもサイズp-1のFFTと同じ時間がかかる。

>>1
ついでなので。リバーシのときと同じく他人の言うことをちゃんと聴くこと。聞くではなく聴くこと。
「まずは動くモノを作る」というのなら再帰使おうが％使おうが、FFTWやGMPより遅かろうが問題ないんだから。
まずはデバグのしやすさ、見易さ優先。アルゴリズムと違うレベルでの速度を求めるのはそれから。