与 ntt 不同,处理 fft 的单位根要更加复杂,主要原因是考虑精度的问题.
我们可以认为直接从三角函数计算出的单位根精度是最高的.
当然由于 \(\sin(x)\) 和 \(\cos(x)\) 的渐进估计涉及到高次项,因此使用 long double 计算单位根再转成 double 是一点点意义的(如果 long double 精度好于 double).
但是,全部使用三角函数计算显然过于昂贵.(三角函数是相当慢的.)
ps : 常见的 fft 写法对单位根做了 \(n\) 次乘法,可谓是精度飞天了.
一个很简单的想法说我们可以只计算 \(\log n\) 个单位根然后用它们的乘积组合出剩下所需的单位根.
一个比较合理的实现是计算 \(2^1\),\(2^2\),\(2^3\)... 次本原单位根然后按二进制组合.
这样只经过了 \(\log n\) 次乘法,是一种不错的办法.
这个思想是可以在线计算单位根而无需预处理出 \(O(n)\) 量级的表的.
另一个很简单的想法是我们可以使用光速幂的思路.
计算 \(\sqrt n\) 个单位根然后用它们的乘积组合出剩下所需的单位根.
这样只经过了 \(1\) 次乘法,能够维持相当高的精度.
当然用这个思想在线计算是很简单的,直接做即可.
对常规实现来说,在线计算的意义并不是很大,但有些实现中在线计算单位根能减少内存访问从而大大减少常数.
标签：计算,loj,double,fft,单位根,https,聊聊 From： https://www.cnblogs.com/QedDust/p/18018053