algorithm - 高速フーリエ変換多項式乗算?

Question

FFT を使用して特定の点で多項式を評価し、値表現を使用して表現できるようにしています。(次数に等しい点数で表現)

ただし、次数 d の 2 つの多項式を乗算するには、両方を 2d + 1 点で評価する必要があります。ただし、評価に FFT を使用する (1 の d 乗根を掛ける) と、d 点での多項式のみが評価されます。したがって、d 点でのみ多項式を評価する場合、多項式評価の評価に FFT をどのように使用できますか? (2d + 1 とは対照的に)

Answer 1

-1 のどの n 乗根で評価するかを選択できます。2d-1 ポイントが必要な場合 (私はあなたがそうしていると思います)、-1 の (2d-1) 乗根を使用します。実際、通常は -1 の 2^k 乗根を使用します。ここで、2^k は 2 の最初の累乗 >= 2d-1 です。これは、2 の累乗の高速 FFT を取得する方がはるかに簡単だからです。 O の定義では一定の因数が許容されるため、O(d log d) のままです。