FFT (the most detailed and popular introductory manual)

statement

First of all, I need to declare that this article is slightly modified on the basis of reprinting. It was reprinted and modified with the permission of the original author ZLH_HHHH (Sori Hui elder sister) . Since I am a beginner and a scumbag in mathematics, so my elder sister Suggest that I write a handbook for the disabled, of course I readily accept it! ! !

text:

The article is a bit urgent.
I hope to point out where there are mistakes, my learning FFT is a relatively slow process. Repeatedly during this period. I wrote this blog post only a very simple understanding. It can also help beginners when learning FFT. Somewhat biased. Avoid too much mental burden.

Go straight to the topic:

FFT is a fast algorithm for DFT. (Divide and conquer improves efficiency)

<script id="MathJax-Element-4" type="math/tex; mode=display"></script>

So then use the inverse operation of FFT to quickly transform back

<script id="MathJax-Element-7" type="math/tex; mode=display"></script>

Let us remember: The inverse operation of FFT is FFT 1

<script id="MathJax-Element-10" type="math/tex; mode=display"></script>

B(x)= i=0n 1bixi

For a polynomial of degree n. The complexity of the naive method of randomly finding n different points is O(n2)

<script id="MathJax-Element-34" type="math/tex; mode=display"></script>

If for a set of numbers with an even number of elements. After each element is squared. The new collection obtained. After removing duplicate elements. The collection size can be halved. And if the new set is even. The new collection still satisfies the above properties. We call this set the nature of halving.

<script id="MathJax-Element-47" type="math/tex; mode=display"></script>

summary:

stencil

Give an iterative structure of the FFT template:

Define the plural:

struct  Complex
{
double x,y;
Complex ( double x1= 0.0 , double y1= 0.0 )
{
x=x1;
y=y1;
}
Complex operator -( const Complex &b) const
{
return  Complex (xb.x,yb.y);
}
Complex operator +( const Complex &b) const
{
return  Complex (x+bx,y+by);
}
Complex operator *( const Complex &b) const
{
return  Complex (x*bx-y*by,x*b.y+y*bx);
}
};
Copy code

To recurse:

void  change (Complex y[], int len)
{
int i,j,k;
for (i= 1 ,j=len/ 2 ;i<len -1 ;i++)
{
if (i<j) swap (y[i],y[j]);
k=len/2 ;
while (j>=k)
{
j-=k;
k/= 2 ;
}
j+=k;
}
}
Copy code

Iterative structure of FFT

When on==-1: FFT
void  FFT (Complex y[], int len, int on)
{
change (y,len);
for ( int h = 2 ;h<=len;h<<= 1 )
{
Complex wn (cos(on* 2 *pi/h),sin(on* 2 *pi/h)) ;
for ( int j = 0 ;j<=len;j+=h)
{
Complex w ( 1 , 0 ) ;
for ( int k=j;k<j+h/2 ;k++)
{
Complex u=y[k];
Complex t=w*y[k+h/2 ];
y[k]=u+t;
y[k+h/2 ]=ut;
w=w*wn;
}
}
}
if (on== -1 )
for ( int i= 0 ;i<len;i++)
y[i].x/=len;
}
Copy code

Handicapped Handbook

1. The naming part does not need to be too tangled, another more general term is to call the two processes forward and inverse of FFT as DFT and IDFT respectively.
2. The principle of "Introduction to Algorithms" is used here, so we will redefine it.
3. C(x)=A(x) B(x)=AiBi
4. Because the order is reduced during the split, we need to substitute x2i and add xi before the odd number.
5. The inverse matrix is the core of FFT . If there is no inverse matrix, the operation cannot be reversed.
6. In the inverse operation, because both sides are multiplied by n for the convenience of the operation, the final result is n times the result we need, just divide by.