快速复数论变换
上的 NTT 常用于替代 FFT 以提高效率,但是严重依赖模数: 是 型(如费马质数)时能快速计算,是 型(如梅森质数)时却难以进行;对此,Number theoretic transforms to implement fast digital convolution 中的快速复数论变换(complex NTT, CNTT)即 上的 DFT 能解决,但未被重视。
DFT 可逆的条件
交换环 上的 DFT 可逆的充要条件是:存在 次本原单位根 ,且 可逆。
模 高斯整数环
为便捷,以下用 表示 型质数, 表示 型质数。
是高斯整数 的素元而 不是,因此 是域而 不是,但 上仍可进行 CNTT。
常用模数的单位根
时 的 次单位根 ;
时 的 次单位根 ;
时 的 次单位根 。
务必注意 不一定成立。
性能和应用
洛谷 P3803 评测记录 显示,按照Optimization of number-theoretic transform in programming contests实现的 NTT 及与其同构的 CNTT, FFT 进行 长度的变换用时分别约为 毫秒。
因此,对于模 型质数的卷积问题,CNTT 明显优于三模数 NTT 和拆系数 FFT。
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用