利用快速傅里叶变换(FFT)计算多项式乘法11页.docx

利用快速傅里叶变换(FFT)计算多项式乘法作者:宋振华摘要本文将讨论快速傅里叶变换(FFT),利用FFT设计一种算法,使多项式相乘的时间复杂度降低为,以便在计算机上高效计算多项式乘法.关键词:快速傅里叶变换、多项式乘法目录1、 引言2、 算法概述三、引理1、多项式的表示(1)系数表达形式(2)点值表达形式(3)插值2、利用离散傅里叶变换(DFT)与FFT导出结果的点值表达形式(1)单位复数根(2)离散傅里叶变换(DFT)(3)通过快速傅里叶变换(FFT)计算向量3、 利用FFT计算逆DFT,将结果的点值表达形式化为系数表达形式(1)在单位复数根处插值(2)利用FFT计算逆DFT四、算法具体流程五、算法的实际应用:计算大整数乘法六、参考文献1、 引言基于FFT的离散傅里叶变换(DFT)技术,是当今信息传输、频谱分析等领域中最重要的数学工具之一.在计算机编程中,我们经常需要计算两个多项式函数的乘积.对于两个次多项式函数,计算其乘积最直接方法