07-12-2012, 02:33 PM
The Fast Fourier Transform
1The Fast Fourier.ppt (Size: 1.25 MB / Downloads: 54)
Polynomial Interpolation & Polynomial Multiplication
Given a set of n points in the plane with distinct x-coordinates, there is exactly one (n-1)-degree polynomial going through all these points.
Alternate approach to computing p(x)q(x):
Calculate p() on 2n x-values, x0,x1,…,x2n-1.
Calculate q() on the same 2n x values.
Find the (2n-1)-degree polynomial that goes through the points {(x0,p(x0)q(x0)), (x1,p(x1)q(x1)), …, (x2n-1,p(x2n-1)q(x2n-1))}.
Unfortunately, a straightforward evaluation would still take O(n2) time, as we would need to apply an O(n)-time Horner’s Rule evaluation to 2n different points.
The “magical” FFT will do it in O(n log n) time, by picking 2n points that are easy to evaluate…
Convolution
The DFT and the inverse DFT can be used to multiply two polynomials
So we can get the coefficients of the product polynomial quickly if we can compute the DFT (and its inverse) quickly…
Multiplying Big Integers
Given N-bit integers I and J, compute IJ.
Assume: we can multiply words of O(log N) bits in constant time.
Setup: Find a prime p=cn+1 that can be represented in one word, and set m=(log p)/3, so that we can view I and J as n-length vectors of m-bit words.
Finding a primitive root of unity.
Find a generator x of Z*p.
Then w=xc is a primitive n-th root of unity in Z*p (arithmetic is mod p)
Apply convolution and FFT algorithm to compute the convolution C of the vector representations of I and J.
Then compute
K is a vector representing IJ, and takes O(n log n) time to compute.
Non-recursive FFT
There is also a non-recursive version of the FFT
Performs the FFT in place
Precomputes all roots of unity
Performs a cumulative collection of shuffles on A and on B prior to the FFT, which amounts to assigning the value at index i to the index bit-reverse(i).
The code is a bit more complex, but the running time is faster by a constant, due to improved overhead