基本信息
辽宁省沈阳市第十五中学2013年高中数学论文 图形计算器应用能力测试活动学生 用快速傅立叶变换实现多项式乘法
宁波效实中学 1502班 周杨
input:expand((x+2)(x+3))
output:x2+5•x+6
在classpad330中，main模块中interactive栏目transformation中的expand一直是广大高中生喜闻乐见的好功能。用法简洁易懂。
但是，当你需要算两个很长很长的多项式的乘积的时候，我相信你一定会被冗长的表达式输入问题伤透脑筋（我*，怎么要输这么多的“xm”……各种残念）。今天，我就带大家认识一种高贵冷艳的计算多项式乘法的方法。
在进入正式介绍之前，我们先要普及一些前提知识。那就是fft。
fft。俗称“法法塔”。学名快速傅立叶变换。fft有什么用呢？它可以在o(nlogn)的时间复杂度内完成一个函数对n个单位虚根的求值，比朴素的o(n2)要厉害得多。下面的几段是关于fft具体操作过程的介绍，如果没有兴趣可以跳过，因为对我们的实际操作没有太大影响,classpad330将会为我们完成它的具体工作的。
单位根定义n次单位根为满足wn=1的复数w。恰好有n个单位根e2πik/n(k=0, 1, ...,n-1)，其中i是虚数单位(i2=-1)，而eiu = cos u + i sin u
定义wn=e2πik/n，称为n次主单位根(pri
