我一直在算法教科书中研究这个主题。
单位复根的巧妙使用似乎在数学上可行。但是，我不明白如何在计算机中实际表示这一点。
我能想到两件事:
- 使用实数/虚数分解来表示复数。但这意味着使用 float ，这意味着我的算法容易出现数值错误，即使我想乘法也会失去精度具有整数系数的两个多项式。
- 将 exp(i 2pi/n) 表示为 n。所以，我最终会在 omega 中得到一个元组，如果我必须以这种形式保留它，我基本上会再次在 omega 中进行多项式乘法，让我们回到原点。
我真的很想看到用熟悉的编程语言实现这个算法。
最佳答案
确实如您所见，单位根通常不是可以很好地存储在计算机中的好数字。由于数值误差很小，如果您知道输出应该是整数，则四舍五入通常会产生正确的结果。
如果您不想(或不能)依赖它，一个确切的选择是数论变换。它将复平面中的单位根替换为有限域 ℤ/pℤ 中的单位根，其中 p 是合适的素数。 p 必须足够大才能存在所有必要的根，并且效率受 p 的属性影响。如果您选择费马素数，则单位根具有方便的形式，并且有一个技巧可以比平时更有效地进行模 p 归约。这都是精确的整数运算，并且值保持很小，因此在计算机中实现它没有问题。
Schönhage–Strassen 算法中使用了该技术，因此您可以在那里查看具体信息。
关于algorithm - 如何使用 FFT 实际实现多项式乘法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45616502/