知识卡片

普通读书笔记卡 · 3692.a.1.a

快速乘法先变换再逐点相乘

理解等级:中级
  1. 先把两个输入的次数界补到2n,用FFT在2n次单位根处求值;
  2. 再逐点相乘,
  3. 最后用逆变换插值得到乘积系数。

补零与逐点乘为Θ(n),两次变换主导为Θ(n lg n),从而加速系数表示的多项式乘法。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第30章 多项式与快速傅里叶变换 · 查看原书依据

      The following procedure takes advantage of the FFT to multiply two polynomials A(x) and B(x) of degree-bound n in Θ(n lg n)-time, where the input and output representations are in coefficient form. The procedure assumes that n is an exact power of 2, so if it isn’t, just add high-order zero coefficients. Double degree-bound: Create coefficient representations of A(x) and B(x) as degree-bound 2n

    参考来源

    - 位置:《算法导论(第4版)》第30章《多项式与快速傅里叶变换》(OEBPS/chapter030.xhtml,文本字符[10000,15000))。 - 结论依据:原文定义信号表示、多项式点值与系数表示、插值及FFT乘法流程;相应公式图已核对。 - 原始内容:The following procedure takes advantage of the FFT to multiply two polynomials A ( x ) and B ( x ) of degree-bound n in Θ( n lg n )-time, where the input and output representations are in coefficient form. The procedure assumes that n is an exact power of 2, so if it isn’t, just add high-order zero coefficients. Double degree-bound: Create coefficient representations of A ( x ) and B ( x ) as degree-bound 2 n