私はAlgorithmsのテキストでこのトピックを勉強しています。実際にFFTを使用して多項式乗算を実装するにはどうすればよいですか？
結束の複雑なルーツの巧妙な使い方は、数学的に作用しているようです。しかし、私は実際にどのようにコンピュータでこれを表すことができるか分かりません。
私は2つのことを考えることができます：
このアルゴリズムの実装は、おなじみのプログラミング言語で見たいと思っています。
実際、あなたが確認したように、団結のルーツは、通常、コンピュータにうまく収まる素敵な数字ではありません。数値エラーは小さいので、出力が整数であることがわかっている場合は、通常、丸めを行うと正しい結果が得られます。
これに頼りたくない（またはできない）場合、正確なオプションはNumber Theoretic Transformです。それは、複素平面内の単一性の根を、有限体ρ/ p in（ここで、pは適切な素数である）の単一性の根で置き換える。 pはすべての必要な根が存在するのに十分な大きさでなければならず、効率はpの性質に影響される。フェルマープライムを選択した場合、単一性のルーツは便利な形になり、通常よりも効率的にモジュロpを減少させるトリックがあります。これはすべての整数演算であり、値は小さく留まるので、コンピュータに実装するのに問題はありません。
この技法はSchönhage-Strassenアルゴリズムで使用されているので、そこでの詳細を調べることができます。
$ p $は素数である必要はなく、実際にSchönhageは素数性について論じていません。フェルマーの素数のように見える形式だけが重要です。これは、単一性の根と同等のものを容易に提供するからです。 – LutzL
はい、いくつかの複合材は問題ありません。本当に必要なのは、根が存在することだけです。しかし、私は、そのような細部が不必要にウサギの穴のところでここに来ていると思う。 – harold
はい文字列乗算のC++の例では、[Modular arthmeticsとNTT（Finite Field DFT）最適化]（https://stackoverflow.com/q/18577076/2521214）を参照してください。 – Spektre
「Numerical Recipes in C」は、すべての栄光の中でFFTを実装しています。 NumPy/SciPyにはPythonのバージョンがあります。 Javaのオープンソースライブラリがあります。あなたが知っている言語を見つけ、ソースをダウンロードしてください。 – duffymo
おそらくhttps://math.stackexchange.com/questions/764727/concrete-fft-polynomial-multiplication-example？ –