FFT — The tough made simple.

Revision en1, by sidhant, 2016-03-02 10:41:33

Aim — To multiply 2 n-degree polynomials in instead of the trivial O(n2)

I have poked around a lot of resources to understand FFT (fast fourier transform), but the math behind it would intimidate me and I would never really try to learn it. Finally last week I learned it from some pdfs and CLRS by building up an intuition of what is actually happening in the algorithm. Using this article I intend to clarify the concept to myself and bring all that I read under one article which would be simple to understand for others struggling with fft.

Let’s get started - Here A(x) and B(x)are polynomials of degree n-1. Now we want to retrieve C(x) in O(n*logn)

So our methodology would be this Convert A(x) and B(x) from coefficient form to point value form. (FFT) Now do theO(n) convulsion in point value form to obtain C(x) in point value form, ie. basically C(x) = A(x) * B(x) in point value form. Now convert C(x) from point value from to coefficient form (Inverse FFT).

Now, what is point value form ?

Tags fft, math, divide and conquer, polynomials, fast multiplication

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en19 English sidhant 2016-12-15 15:43:01 68 Tiny change: 'y/48798)\n\nRefere' -br
en18 English sidhant 2016-12-02 10:11:30 11
en17 English sidhant 2016-12-02 10:08:00 6 Tiny change: '2k}*(cos(2) + i*sin(2)) = w_{n}' - (published)
en16 English sidhant 2016-12-02 10:06:22 124 (saved to drafts)
en15 English sidhant 2016-10-17 12:10:22 3897 Tiny change: 'n - 1} \\ w_n^{2} &' -
en14 English sidhant 2016-03-12 13:12:08 269
en13 English sidhant 2016-03-11 20:36:36 20 Typo - Convulsion is actually Convolution.
en12 English sidhant 2016-03-11 17:34:46 0 (published)
en11 English sidhant 2016-03-11 15:48:16 287 Tiny change: ' for $A(x) and $B(x).\nThis co' -
en10 English sidhant 2016-03-11 12:22:09 182 Tiny change: ' A(x) * B(X)$ \nH' -br
en9 English sidhant 2016-03-11 12:16:47 1195 Tiny change: ' $w_{n} = $ e^{2\pii\n}$ \n5' -br
en8 English sidhant 2016-03-11 10:59:08 181 Tiny change: ' to RIGHT.\nIntuitiv' -br
en7 English sidhant 2016-03-11 10:55:44 2737 Tiny change: 'm in $O(n*\logn)$ usi' -
en6 English sidhant 2016-03-11 10:29:11 14 Tiny change: 'us_bi.png)\nQ) What ' -br\nQ) What '
en5 English sidhant 2016-03-11 10:26:18 2616 Tiny change: '^{2\pii/n}\nNow let ' -
en4 English sidhant 2016-03-11 09:14:22 2751 Tiny change: '$ \n$\n\begin{pma' -br
en3 English sidhant 2016-03-02 11:31:21 3540 Tiny change: '(x) * B(x)$ \n$C' -br
en2 English sidhant 2016-03-02 10:57:18 2132 Tiny change: 't started -\n$\displa' -br
en1 English sidhant 2016-03-02 10:41:33 1180 Initial revision (saved to drafts)