内容提要 多项式的表示方式 多项式与FFT 清华大学 多项式的基本运算 宋斌恒 运算的效率分析 FFT思想与实现 多项式 多项式加法 B(x) 在代数域F上的变量为x的多项式 n是幂次( degree)的上界,我们称k是上述多项 式的幂次,如果幂次最大的非零系数是a C(x) C=A+B 例1 若A(x)=6x3+7x2-10X+9 B(x)=2X3+4X-5, 则C(x)=4x3+7x2-6x+4 a,+b, for j1 多项式与FFT 清华大学 宋斌恒 内容提要 • 多项式的表示方式 – 系数 – 值 • 多项式的基本运算 – 加减乘除 • 运算的效率分析 • FFT思想与实现 多项式 • 在代数域F上的变量为x的多项式 • n是幂次（degree）的上界，我们称k是上述多项 式的幂次，如果幂次最大的非零系数是ak， ∑ − = = 1 0 ( ) n j j j A x a x 多项式加法 ∑ − = = 1 0 ( ) n j j j B x b x ∑ − = = 1 0 ( ) n j j j C x c x C=A+B c = a + b for j = 0,...,n −1 j j j 示例1 • 若A(x) = 6x3 + 7x2 - 10x + 9 • B(x) = -2x3+ 4x - 5, • 则 C(x) = 4x3 + 7x2 - 6x + 4