FFT

缘起

高精度乘法，以前给出过O(n^2)的朴素算法和O(n^log3)的karatsuba优化. 但是还有更好更快的优化——FFT（快速傅里叶变化(fast Fourier transform)） 它是基于 DFT（discrete fourier transform 离散傅里叶变换）

fft是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使dft时所需要的乘法次数大幅减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。fft的复杂度是 O(nlogn)的.

fft是dft的快速算法. 它是根据dft的奇、偶、虚、实等特性，对dft算法进行改进获得的. 所以说啊, 算法的根本性的改进总来自于数学理论的突破啊~ 所以学好数学真的重要——不然只能CRUD一辈子~

fft用来加速多项式乘法（高精度乘法只是顺便的结果而已）

Read More