知识卡片
模运算FFT可避免浮点舍入
复数DFT在浮点实现中可能引入舍入误差。
若目标结果是整数,并能选出适合变换长度的模数和单位根,可把变换放在模环中做,以获得精确的模运算结果;还须处理取值范围与还原。
这里“适合”至少包含这些条件:对长度为N的变换,要在模p下找到阶恰为N的元素ω(即ωᴺ≡1,但更小的正指数不能得到1),并且N在模p下可逆,逆变换才能乘以N⁻¹。书中题目取N为2的幂、p=kN+1为素数,再由模p乘法群的生成元构造ω。
模运算得到的是系数对p的余数。若已知真实整数系数落在一个不会发生混淆的范围内,可直接选唯一代表;若可能越界,则要选更大的模数,或用多个模数的结果经中国余数定理还原。这样“没有浮点误差”才等于“恢复了原整数答案”。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第30章 多项式与快速傅里叶变换 · 查看原书依据
As defined, the discrete Fourier transform requires computation with complex numbers, which can result in a loss of precision due to round-off errors. For some problems, the answer is known to contain only integers, and a variant of the FFT based on modular arithmetic can guarantee that the answer is calculated exactly. An example of such a problem is that of multiplying two
参考来源
- 位置:《算法导论(第4版)》第30章《多项式与快速傅里叶变换》(OEBPS/chapter030.xhtml,文本字符[35000,40000))。
- 结论依据:原文问题30-5明确令N为2的幂,寻找p=kN+1的素数,并由模p乘法群生成元构造主N次单位根;逆变换的可逆条件及整数范围还原是对该机制的必要说明。
- 原始内容:As defined, the discrete Fourier transform requires computation with complex numbers, which can result in a loss of precision due to round-off errors. For some problems, the answer is known to contain only integers, and a variant of the FFT based on modular arithmetic can guarantee that the answer is calculated exactly. An example of such a problem is that of multiplying two