使用 FFT 和 IFFT 计算 (x^2 + 1)^3
Compute (x^2 + 1)^3 using FFT and IFFT
到目前为止，我设法 运行 FFT 并且我得到了下一个 table 系数：
[2, 1 + i, 0, 1 - i, 2, 1 + i, 0, 1 - i]
我遇到的问题是计算逆并获得系数形式的多项式。你能帮我解释一下如何确定我需要使用的单位根的倒数吗？以及对如何应用 IFFT 的更广泛的解释。
非常感谢！
您 FFT/IFFT 的具体用途是什么？
如果 x 是 bignum
- 参见 fast bignum sqr 特别是 Schönhage-Strassen 乘法
- 对于
^2 和 ^3 你可以计算 NTT/FFT 一次而不是 2 和 3 次
x^2+1是多项式
p(x)=1 + 0*x + 1*x^2=(1,0,1)- 见multiply polynomials with FFT
[备注]
- 对于这两种情况，使用 NTT 而不是 FFT 更好
- 由于精度损失（舍入误差）
到目前为止，我设法 运行 FFT 并且我得到了下一个 table 系数：
[2, 1 + i, 0, 1 - i, 2, 1 + i, 0, 1 - i]
我遇到的问题是计算逆并获得系数形式的多项式。你能帮我解释一下如何确定我需要使用的单位根的倒数吗？以及对如何应用 IFFT 的更广泛的解释。
非常感谢！
您 FFT/IFFT 的具体用途是什么？
如果
x是bignum- 参见 fast bignum sqr 特别是 Schönhage-Strassen 乘法
- 对于
^2和^3你可以计算 NTT/FFT 一次而不是 2 和 3 次
x^2+1是多项式p(x)=1 + 0*x + 1*x^2=(1,0,1)- 见multiply polynomials with FFT
[备注]
- 对于这两种情况，使用 NTT 而不是 FFT 更好
- 由于精度损失（舍入误差）