NTT相关
一种快速数论变换算法，这种算法是以数论为基础，对样本点为的数论变换，按时间抽取的方法，得到一组等价的迭代方程，有效高速简化了方程中的计算公式·与直接计算相比，大大减少了运算次数。（见快速傅里叶变换）。
在计算机实现多项式乘法中，我们所熟知的快速傅里叶变换(FFT)是基于n次单位根 (omega) 的优秀性质实现的，而由于其计算时会使用正弦函数和余弦函数，在不断运算时无法避免地会产生精度误差。而多项式乘法有些时候会建立在模域中，在对一些特殊的大质数取模时，便可以考虑用原根g来代替 ，而这些特殊的大质数的原根恰好满足 的某些性质，这使得多项式乘法在模域中也可以快速的分治合并。
——百度百科
NTT（Number Theoretic Transform），中文名快速数论变换
和 F F T FFT FFT一样， N T T NTT NTT也用来加速多项式乘法，不过 N T T NTT NTT最大的优点是可以取模
或者可以理解为 N T T NTT NTT是 F F T FFT FFT取模升级版
- 看这篇 N T T NTT NTT之前确保你已经会了 F F T FFT FFT→ F F T FFT FFT相关
- 好像 N T T NTT NTT比起 F F T FFT FFT来难的知识点更少了emm
NTT的优缺点
优点
- 能取模， F F T FFT FFT的复数你给我来取个模
- 没有精度差， F F T FFT FFT浮点数的精度怎么也会出一点问题
- 由于均为整数操作（虽然取模多）， N T T NTT NTT常数小，通常比一大堆浮点运算的 F F T FFT FFT要快
（其实这是放屁）
我只能说 N T T NTT NTT小数据下表现良好…
缺点
- 多项式的系数都必须是整数
- 模数有限制， N T T NTT NTT题的模数通常都是相同的 998244353
- 其实这些模数的原根通常都是 3 3
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/25234.html