← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3693.c.3

模运算FFT可避免浮点舍入

理解等级:中级

复数DFT在浮点实现中可能引入舍入误差。

若目标结果是整数,并能选出适合变换长度的模数和单位根,可把变换放在模环中做,以获得精确的模运算结果;还须处理取值范围与还原。

这里“适合”至少包含这些条件:对长度为N的变换,要在模p下找到阶恰为N的元素ω(即ωᴺ≡1,但更小的正指数不能得到1),并且N在模p下可逆,逆变换才能乘以N⁻¹。书中题目取N为2的幂、p=kN+1为素数,再由模p乘法群的生成元构造ω。

模运算得到的是系数对p的余数。若已知真实整数系数落在一个不会发生混淆的范围内,可直接选唯一代表;若可能越界,则要选更大的模数,或用多个模数的结果经中国余数定理还原。这样“没有浮点误差”才等于“恢复了原整数答案”。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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