如何使用FFT实际实现多项式乘法？

我一直在算法教科书中研究这个话题。如何使用FFT实际实现多项式乘法？

统一的复杂根源的巧妙使用似乎是数学上的工作。但是，我不明白如何在电脑中实际表示这一点。

我能想到的两件事情：

使用实/虚分解来表示复数。但是这意味着使用浮点数，这意味着我打开我的算法数值误差，即使我想用整数系数乘以两个多项式，我也会失去精度。
将exp（i 2pi/n）表示为n。所以，我最终会得到一个欧米茄中的元组，如果我必须保持这种形式，我基本上会在欧米茄中进行多项式乘法运算，并将我们带回原点。

我真的很希望看到用熟悉的编程语言实现这个算法。

来源

2017-08-10 Agnishom Chattopadhyay

“C中的数字食谱”在其所有的荣耀中都有FFT实现。 NumPy/SciPy将拥有Python版本。有Java开源库。找到您认识的语言并下载源代码。 – duffymo

也许https://math.stackexchange.com/questions/764727/concrete-fft-polynomial-multiplication-example？ –

确实如你所说，团结的根源通常不是很好的数字，可以很好地存储在计算机中。由于数值误差很小，如果您知道输出应该是整数，舍入通常会产生正确的结果。

如果你不想（或不能）依赖那个，一个确切的选项是数值理论变换。它将复合平面中的统一根替换为有限域上的统一根ℤ/pℤ，其中ρ是一个合适的素数。 p必须足够大才能存在所有必要的根，效率受p的性质影响。如果您选择费马素数，那么统一的根源便于形式，并且有一种技巧可以比平常更有效地进行模数p的减法。这就是所有精确的整数运算，并且这些值保持很小，所以在计算机中实现它没有问题。

该技术在Schönhage-Strassen算法中使用，因此您可以查看其中的细节。

来源

2017-08-10 15:26:35 harold

$ p $不需要是一个素数，而且Schönhage确实不讨论素数。只有看起来像费马素数的形式很重要，因为它很容易提供相当于团结的根源。 – LutzL

是的，一些复合材料很好，我们真正需要的是根部的存在。但我认为这样的细节会在这里进一步恶化。 – harold

是的NTT是可能的方式为整数看到[模块化算法和NTT（有限域DFT）优化]（https://stackoverflow.com/q/18577076/2521214）为C + +字符串乘法的例子。 – Spektre

如何使用FFT实际实现多项式乘法？

回答

相关问题