multiplication - 大きな多項式を評価するための最速のアルゴリズム

Question

かなり一般的な質問ですが、次数 400 から 500 の多項式を評価するための (時間計算量の点で) 最速のアルゴリズムは何ですか。

前もって感謝します。

Answer 1

多項式の評価について話している場合、特別な状況がある場合を除いて、おそらく線形時間ホーナー方式よりも高速になることはありません。

多項式の乗算について話している場合、カラツバ アルゴリズムは実装がかなり簡単で、そのサイズに対して非常に高速です。高速フーリエ変換ベースのアルゴリズムは、多項式が大きい場合にのみ使用する価値があると思います。

Answer 2

高速フーリエ変換 (FFT) の修正版は、通常、この種の問題に対して非常に良い結果をもたらします。ハイブリッド FFT アプローチの採用を提案しているこのペーパーをご覧ください。「高速一変量FFT」に沿った用語を探すことから研究を始めます。2 つの多項式の乗算は、基本的に 2 つの整数の乗算と同じ操作であることに注意してください。