This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together
preface
FFT is a fast (O(nlogn)) algorithm for finding the product of two polynomials. Before reading this article, please read 1. This article is an explanation and supplement to 1, with two main contributions:
- Fill in the theoretical part that the original text did not say clearly;
- Through recursion, the idea of the original text is reorganized, so that the theory and code are better understood.
In addition, only the source code is placed in the appendix of this article, and it is mentioned in this article.
Theory: The theoretical basis of IFFT
To understand the code logic of the FAST Fourier transform, you need to understand the following five topics:
1. Polynomial coefficient representation and point value representation 2. NTH unit root 3.DFT 4
The first four parts of the theory constitute the theoretical basis of FFT. So one has all of these four points, and it’s easy to understand. Please read the original article to familiarize yourself with the first four theories.
The fifth point (theoretical basis of IFFT) is mainly discussed below.
FFT essentially solves a multiplication problem
All the following notations correspond to 1, and note wi=ωni=exp(I ∗2π I /n)w_i = \omega_n^ I =exp(\mathbf{I}*2\ PI I /n) Wi =ωni=exp(I ∗2π I /n), corresponding to the n-degree unit root. (I \mathbf{I} I is an imaginary unit.)
Write down the power matrix W of the NTH unit root, the coefficient vector C, and the value vector V as follows:
The WC = VWC = VWC = V.
FFT essentially solves the problem of multiplying V given W and C, and gives an O(nlogn)O(nlogn)O(nlogn) O(nlogn) method for this problem.
IFFT can be represented as a similar multiplication problem
IFFT can be represented as a similar multiplication problem and solved in a similar way. This section refers to 2.
So let’s first take the inverse of W. Remember the vi = conj (wi) = exp (- I ∗ 2 PI I/n) v_i = conj (w_i) = exp (- \ mathbf {I} * 2 \ PI I/n) = vi conj (wi) = exp (- I ∗ 2 PI I/n), namely wiw_iwi conjugate. (I \mathbf{I} I is an imaginary unit.)
Let’s call the matrix W prime
Find WW ‘ ‘W = W = nIWW’ = W W = nIWW ‘ ‘W = W = nI (easy), then the inverse matrix is W W’ n \ frac {W ‘} {n} ‘nW, W = cl-ncw-2 under’ V ‘ ‘V = cl-ncw-2 under’ V = nC. Therefore, as long as the NTH unit root is changed into its conjugate in the implementation algorithm of FFT, it can be solved from vector V to vector C in O(Nlogn)O(Nlogn)O(nlogn)O(nlogn), that is, the IFFT algorithm is realized.
To sum up, the same logic is used to implement IFFT and FFT, but different NTH unit roots are used.
The basic implementation of FFT algorithm
The following is the basic implementation of the FFT algorithm. Fft_logic is the common master logic of FFT and IFFT. FFT and IFFT are two shells of FFT_Logic. Read the code for FFt_logic with comments. See Appendix 1 for the complete program, including the main functions for the test. See 3 for the use of the complex class.)
#include <iostream>
#include <cmath>
#include <complex>
using namespace std;
const double pi = 3.14159265358979323846;
const int N = 8; // The maximum number of digits supported by the polynomial
complex<double> b[N]; // An array used as a temporary adjustment space
void fft_logic(complex<double> *a, int n, int inv){
/ / parameters:
// When inv = 1, a is the coefficient polynomial, n is the current array length (a power of 2), the function effect is in place to become a point value polynomial
// When inv = -1, a is the point-valued polynomial, and n is the current array length (a power of 2). The effect of the function is to become a polynomial of coefficients in place, but the resulting coefficients are n-fold, which needs to be adjusted in the wrapped function
if (n == 1) return; // Why? Since omega_1^0=1, the point value polynomials and coefficient polynomials are represented exactly the same.
A [0] a[2] a[0] a[2]... a[n-2] a[1] a[3] .. A [N-1], front and back
for(int i = 0; i < n/2; i ++){
b[i] = a[i * 2];
b[i + n/2] = a[i * 2 + 1];
}
for(int i = 0; i < n; i ++)
a[i] = b[i];
// divide and conquer A1 and A2
fft_logic(a, n/2, inv);
fft_logic(a + n/2, n/2, inv);
// Calculate A from A1 and A2
double unit_rad = 2 * pi / n; // Unit Angle amplitude value
for(int i = 0; i < n/2; i ++){
complex<double> x(cos(i * unit_rad), inv*sin(i * unit_rad)); // x = omega_n^i
complex<double> tmp1 = a[i];
complex<double> tmp2 = x * a[i + n/2];
a[i] = tmp1 + tmp2;
a[i + n/2] = tmp1 - tmp2; }}void fft(complex<double> *a, int n){
// Input coefficient polynomial and its length, in situ conversion to point value polynomial
fft_logic(a, n, 1);
}
void ifft(complex<double> *a, int n){
// Input point value polynomial and its length, in situ conversion to coefficient polynomial
fft_logic(a, n, - 1);
for(int i = 0; i < n; i ++)
a[i] /= n;
}
Copy the codeAs the author said, the disadvantage of this method is that the constants are too large and need to be optimized…
Iterative version of FFT: optimization constant
Recursion-based version
To address the shortcomings of the algorithm in the previous section, we noticed that the ffp_logic function “rearranges recursion every time”, and optimized it to “rearranges recursion directly after order”.
The idea of optimization is that for every time A1 and A2 are interspersed in the original algorithm, the original array can be rearranged in advance instead. Take a picture from the original text to illustrate:
At n=8, the original order is eventually interwoven into 0, 4, 2, 6, 1, 5, 3, 7, and at n=4, 0, 2, 1, 3. This sequence depends only on n, so we can use a function to generate such an interspersed sequence.
void fft_rearrange_decidesequence_logic(int *rev, int n){
// Given the array rev and the array length n, the function writes the desired order to the array, such as 0, 2, 1, 3 to the array rev when n = 4
if(n == 1){
rev[0] = 0;
return;
}
// The order in which n/2 is obtained is temporarily placed after rev
fft_rearrange_decidesequence_logic(rev + n/2, n/2);
// use the order n/2 to construct the order n/2
for(int i = 0; i < n/2; i ++){
rev[i] = 2 * rev[i + n/2];
rev[i + n/2] = 2 * rev[i + n/2] + 1; }}Copy the codeThe fft_rearrange_decidesequence_logic function naturally describes interspersed logic in a recursive manner, resulting in the correct rearrangement order.
void fft_rearrange_logic(complex<double> *a, int n){
// Rearrange a into an order that can recursively go up
// Calculate bit: pow(2, bit) = n
int bit = 0;
while((1 << bit) < n) bit ++;
// rev: determine the final rearrange of A
int* rev = new int[n];
fft_rearrange_decidesequence_logic(rev, n);
// Adjust the order of a according to rev sequence
complex<double>* tmp_a = new complex<double>[n];
for(int i = 0; i < n; i ++) tmp_a[i] = a[rev[i]];
for(int i = 0; i < n; i ++) a[i] = tmp_a[i];
delete[] rev;
}
Copy the codeFft_rearrange_logic obtains a rearrangement sequence based on the n value and rearranges the input.
void fft_merge_logic(complex<double> *a, int n, int inv){
if(n == 1) return;
fft_merge_logic(a, n/2, inv);
fft_merge_logic(a + n/2, n/2, inv);
double unit_rad = 2 * pi / n;
for(int i = 0; i < n/2; i ++){
complex<double> x(cos(i * unit_rad), inv*sin(i * unit_rad)); // x = omega_n^i
complex<double> tmp1 = a[i];
complex<double> tmp2 = x * a[i + n/2];
a[i] = tmp1 + tmp2;
a[i + n/2] = tmp1 - tmp2; }}void fft_logic(complex<double> *a, int n, int inv){
/ / parameters:
// When inv = 1, a is the coefficient polynomial, n is the current array length (a power of 2), the function effect is in place to become a point value polynomial
// When inv = -1, a is the point-valued polynomial, and n is the current array length (a power of 2). The effect of the function is to become a polynomial of coefficients in place, but the resulting coefficients are n-fold, which needs to be adjusted in the wrapped function
// Adjust the order of the elements in a to the order required by the algorithm
fft_rearrange_logic(a, n);
// adjust the sequence of a to merge
fft_merge_logic(a, n, inv);
}
Copy the codeAfter unifying the rearrangements, the FFT_logic function is shown above. Here, FFt_MERge_logic extracts the rearranged merged logic from the previous section.
See Appendix 2 for the complete, runnable code.
The purpose of this section is to write an easy-to-understand, readable implementation of the FFT algorithm that is modified at the speed of the original text.
Rearrange logic: Changes recursion to non-recursion
Comparing the code in Appendices 2 and 3, fft_rearrange_decidesequence_logic is cut out and replaced with a concise loop. In addition, the part of adjusting the order of A according to the rev sequence has been modified with respect to original text 1. I don’t think there is much difference in efficiency between the two methods, and both are easier to understand.
Since there is a conclusion that the final position of each position after partition and conquer is the position obtained after its binary inversion (i.e. the well-used butterfly algorithm), this formula can be used to generate rev directly without writing recursion.
void fft_rearrange_logic(complex<double> *a, int n){
// Rearrange a into an order that can recursively go up
// Calculate bit: pow(2, bit) = n
int bit = 0;
while((1 << bit) < n) bit ++;
// rev: determine the final rearrange of A
int* rev = new int[n];
for(int i = 0; i < n; i ++){
rev[i]=(rev[i>>1] > >1)|((i&1)<<(bit- 1));
}
// Adjust the order of a according to rev sequence
for(int i = 0; i < n; i ++){
if (i<rev[i])swap(a[i],a[rev[i]]);// If does not swap twice
}
delete[] rev;
}
Copy the codeThe complete code is shown in Appendix 3.
Get rid of all the recursion in the algorithm
Let’s consider the recursive structure (forgive me for being too lazy to draw a new graph) :
The eight depends on the completion of two fours, each of which depends on the completion of the following two twos, each of which depends on the completion of the following two ones. Thus, you can go through a loop that completes eight ones (no action required), then four twos, then two fours, and finally eight.
Write the logic out in a loop, and you get an algorithm for eliminating recursion. This algorithm corresponds to the final board of text 1.
void fft_logic(complex<double> *a,int n,int inv){
// bit: pow(2, bit) = n
int bit = 0;
while((1 << bit) < n) bit ++;
// rev: determines the final rearrange position sequence
int* rev = new int[n];
for(int i = 0; i < n; i ++){
rev[i]=(rev[i>>1] > >1)|((i&1)<<(bit- 1));
}
// Adjust the order of a according to rev sequence
for(int i = 0; i < n; i ++){
if (i<rev[i])swap(a[i],a[rev[i]]);// If does not swap twice
}
delete[] rev;
// adjust the sequence of a to merge
for (int mid=1; mid<n; mid*=2) {// Inside the mid loop, we are ready to merge two mid sequences into a 2 * mid sequence
double unit_rad = 2 * pi / (2 * mid); // Unit Angle amplitude value
for (int i=0; i<n; i+=mid*2) {// merge two sequences of length mid at I ~ I +mid*2 into 2 * mid
for (int j = 0; j < mid; j ++){
// the logical sum within the j loop
complex<double> x(cos(j * unit_rad), inv*sin(j * unit_rad)); // x = omega_n^i
complex<double> tmp1 = a[i+j];
complex<double> tmp2 = x * a[i+j+mid]; a[i+j] = tmp1 + tmp2; a[i+j+mid] = tmp1 - tmp2; }}}}Copy the codeThe complete code is shown in Appendix 4.
The appendix
Appendix 1
#include <iostream>
#include <cmath>
#include <complex>
using namespace std;
const double pi = 3.14159265358979323846;
const int N = 8; // The maximum number of digits supported by the polynomial
complex<double> b[N]; // An array used as a temporary adjustment space
void fft_logic(complex<double> *a, int n, int inv){
/ / parameters:
// When inv = 1, a is the coefficient polynomial, n is the current array length (a power of 2), the function effect is in place to become a point value polynomial
// When inv = -1, a is the point-valued polynomial, and n is the current array length (a power of 2). The effect of the function is to become a polynomial of coefficients in place, but the resulting coefficients are n-fold, which needs to be adjusted in the wrapped function
if (n == 1) return; // Why? Since omega_1^0=1, the point value polynomials and coefficient polynomials are represented exactly the same.
A [0] a[2] a[0] a[2]... a[n-2] a[1] a[3] .. A [N-1], front and back
for(int i = 0; i < n/2; i ++){
b[i] = a[i * 2];
b[i + n/2] = a[i * 2 + 1];
}
for(int i = 0; i < n; i ++)
a[i] = b[i];
// divide and conquer A1 and A2
fft_logic(a, n/2, inv);
fft_logic(a + n/2, n/2, inv);
// Calculate A from A1 and A2
double unit_rad = 2 * pi / n; // Unit Angle amplitude value
for(int i = 0; i < n/2; i ++){
complex<double> x(cos(i * unit_rad), inv*sin(i * unit_rad)); // x = omega_n^i
complex<double> tmp1 = a[i];
complex<double> tmp2 = x * a[i + n/2];
a[i] = tmp1 + tmp2;
a[i + n/2] = tmp1 - tmp2; }}void fft(complex<double> *a, int n){
// Input coefficient polynomial and its length, in situ conversion to point value polynomial
fft_logic(a, n, 1);
}
void ifft(complex<double> *a, int n){
// Input point value polynomial and its length, in situ conversion to coefficient polynomial
fft_logic(a, n, - 1);
for(int i = 0; i < n; i ++)
a[i] /= n;
}
// Main function test
complex<double> A1[N], A2[N]; // The polynomial in the multiplication
complex<double> C[N]; // The result of the multiplication
int main(a){
// Initializes two multiplying polynomials. Note: Both multiplying polynomials and the final product polynomial need to have the same number of terms
for(int i = 0; i < N; i ++){
A1[i] = A2[i] = 0;
}
A1[0] = 1, A1[1] = 1, A1[2] = 3, A1[3] = 2; // A1(x) = 2x3 + 3x2 + x + 1
A2[0] = 4, A2[1] = 3, A2[2] = 5, A2[3] = 1; // A2(x) = x3 + 5x2 + 3x + 4
// F times F inverse
fft(A1, N);
fft(A2, N);
/* for(int i = 0; i < N; i ++) cout << A1[i] << " "; cout << endl; for(int i = 0; i < N; i ++) cout << A2[i] << " "; cout << endl; * /
for(int i = 0; i < N; i ++)
C[i] = A1[i] * A2[i];
ifft(C, N);
/ / output
for(int i = 0; i < N; i ++)
cout << C[i] << endl;
return 0;
}
Copy the codeAppendix 2
#include <iostream>
#include <cmath>
#include <complex>
using namespace std;
const double pi = 3.14159265358979323846;
const int N = 8; // The maximum number of digits supported by the polynomial
complex<double> b[N]; // An array used as a temporary adjustment space
void fft_merge_logic(complex<double> *a, int n, int inv){
if(n == 1) return;
fft_merge_logic(a, n/2, inv);
fft_merge_logic(a + n/2, n/2, inv);
double unit_rad = 2 * pi / n;
for(int i = 0; i < n/2; i ++){
complex<double> x(cos(i * unit_rad), inv*sin(i * unit_rad)); // x = omega_n^i
complex<double> tmp1 = a[i];
complex<double> tmp2 = x * a[i + n/2];
a[i] = tmp1 + tmp2;
a[i + n/2] = tmp1 - tmp2; }}void fft_rearrange_decidesequence_logic(int *rev, int n){
// Given the array rev and the array length n, the function writes the desired order to the array, such as 0, 2, 1, 3 to the array rev when n = 4
if(n == 1){
rev[0] = 0;
return;
}
// The order in which n/2 is obtained is temporarily placed after rev
fft_rearrange_decidesequence_logic(rev + n/2, n/2);
// use the order n/2 to construct the order n/2
for(int i = 0; i < n/2; i ++){
rev[i] = 2 * rev[i + n/2];
rev[i + n/2] = 2 * rev[i + n/2] + 1; }}void fft_rearrange_logic(complex<double> *a, int n){
// Rearrange a into an order that can recursively go up
// Calculate bit: pow(2, bit) = n
int bit = 0;
while((1 << bit) < n) bit ++;
// rev: determine the final rearrange of A
int* rev = new int[n];
fft_rearrange_decidesequence_logic(rev, n);
// Adjust the order of a according to rev sequence
complex<double>* tmp_a = new complex<double>[n];
for(int i = 0; i < n; i ++) tmp_a[i] = a[rev[i]];
for(int i = 0; i < n; i ++) a[i] = tmp_a[i];
delete[] rev;
}
void fft_logic(complex<double> *a, int n, int inv){
/ / parameters:
// When inv = 1, a is the coefficient polynomial, n is the current array length (a power of 2), the function effect is in place to become a point value polynomial
// When inv = -1, a is the point-valued polynomial, and n is the current array length (a power of 2). The effect of the function is to become a polynomial of coefficients in place, but the resulting coefficients are n-fold, which needs to be adjusted in the wrapped function
// Adjust the order of the elements in a to the order required by the algorithm
fft_rearrange_logic(a, n);
// adjust the sequence of a to merge
fft_merge_logic(a, n, inv);
}
void fft(complex<double> *a, int n){
// Input coefficient polynomial and its length, in situ conversion to point value polynomial
fft_logic(a, n, 1);
}
void ifft(complex<double> *a, int n){
// Input point value polynomial and its length, in situ conversion to coefficient polynomial
fft_logic(a, n, - 1);
for(int i = 0; i < n; i ++)
a[i] /= n;
}
// Main function test
complex<double> A1[N], A2[N]; // The polynomial in the multiplication
complex<double> C[N]; // The result of the multiplication
int main(a){
// Initializes two multiplying polynomials. Note: Both multiplying polynomials and the final product polynomial need to have the same number of terms
for(int i = 0; i < N; i ++){
A1[i] = A2[i] = 0;
}
A1[0] = 1, A1[1] = 1, A1[2] = 3, A1[3] = 2; // A1(x) = 2x3 + 3x2 + x + 1
A2[0] = 4, A2[1] = 3, A2[2] = 5, A2[3] = 1; // A2(x) = x3 + 5x2 + 3x + 4
// F times F inverse
fft(A1, N);
fft(A2, N);
/* for(int i = 0; i < N; i ++) cout << A1[i] << " "; cout << endl; for(int i = 0; i < N; i ++) cout << A2[i] << " "; cout << endl; * /
for(int i = 0; i < N; i ++)
C[i] = A1[i] * A2[i];
ifft(C, N);
/ / output
for(int i = 0; i < N; i ++)
cout << C[i] << endl;
return 0;
}
Copy the codeThe appendix 3
#include <iostream>
#include <cmath>
#include <complex>
using namespace std;
const double pi = 3.14159265358979323846;
const int N = 1024; // The maximum number of digits supported by the polynomial
complex<double> b[N]; // An array used as a temporary adjustment space
void fft_merge_logic(complex<double> *a, int n, int inv){
if(n == 1) return;
fft_merge_logic(a, n/2, inv);
fft_merge_logic(a + n/2, n/2, inv);
double unit_rad = 2 * pi / n;
for(int i = 0; i < n/2; i ++){
complex<double> x(cos(i * unit_rad), inv*sin(i * unit_rad)); // x = omega_n^i
complex<double> tmp1 = a[i];
complex<double> tmp2 = x * a[i + n/2];
a[i] = tmp1 + tmp2;
a[i + n/2] = tmp1 - tmp2; }}void fft_rearrange_logic(complex<double> *a, int n){
// Rearrange a into an order that can recursively go up
// Calculate bit: pow(2, bit) = n
int bit = 0;
while((1 << bit) < n) bit ++;
// rev: determine the final rearrange of A
int* rev = new int[n];
for(int i = 0; i < n; i ++){
rev[i]=(rev[i>>1] > >1)|((i&1)<<(bit- 1));
}
// Adjust the order of a according to rev sequence
for(int i = 0; i < n; i ++){
if (i<rev[i])swap(a[i],a[rev[i]]);// If does not swap twice
}
delete[] rev;
}
void fft_logic(complex<double> *a, int n, int inv){
/ / parameters:
// When inv = 1, a is the coefficient polynomial, n is the current array length (a power of 2), the function effect is in place to become a point value polynomial
// When inv = -1, a is the point-valued polynomial, and n is the current array length (a power of 2). The effect of the function is to become a polynomial of coefficients in place, but the resulting coefficients are n-fold, which needs to be adjusted in the wrapped function
// Adjust the order of the elements in a to the order required by the algorithm
fft_rearrange_logic(a, n);
// adjust the sequence of a to merge
fft_merge_logic(a, n, inv);
}
void fft(complex<double> *a, int n){
// Input coefficient polynomial and its length, in situ conversion to point value polynomial
fft_logic(a, n, 1);
}
void ifft(complex<double> *a, int n){
// Input point value polynomial and its length, in situ conversion to coefficient polynomial
fft_logic(a, n, - 1);
for(int i = 0; i < n; i ++)
a[i] /= n;
}
// Main function test
complex<double> A1[N], A2[N]; // The polynomial in the multiplication
complex<double> C[N]; // The result of the multiplication
int main(a){
// Initializes two multiplying polynomials. Note: Both multiplying polynomials and the final product polynomial need to have the same number of terms
for(int i = 0; i < N; i ++){
A1[i] = A2[i] = 0;
}
A1[0] = 1, A1[1] = 1, A1[2] = 3, A1[3] = 2; // A1(x) = 2x3 + 3x2 + x + 1
A2[0] = 4, A2[1] = 3, A2[2] = 5, A2[3] = 1; // A2(x) = x3 + 5x2 + 3x + 4
// F times F inverse
fft(A1, N);
fft(A2, N);
/* for(int i = 0; i < N; i ++) cout << A1[i] << " "; cout << endl; for(int i = 0; i < N; i ++) cout << A2[i] << " "; cout << endl; * /
for(int i = 0; i < N; i ++)
C[i] = A1[i] * A2[i];
ifft(C, N);
/ / output
for(int i = 0; i < N; i ++)
cout << C[i] << endl;
return 0;
}
Copy the codeAppendix 4
#include <iostream>
#include <cmath>
#include <complex>
using namespace std;
const double pi = 3.14159265358979323846;
const int N = 8; // The maximum number of digits supported by the polynomial
complex<double> b[N]; // An array used as a temporary adjustment space
void fft_logic(complex<double> *a,int n,int inv){
// bit: pow(2, bit) = n
int bit = 0;
while((1 << bit) < n) bit ++;
// rev: determines the final rearrange position sequence
int* rev = new int[n];
for(int i = 0; i < n; i ++){
rev[i]=(rev[i>>1] > >1)|((i&1)<<(bit- 1));
}
// Adjust the order of a according to rev sequence
for(int i = 0; i < n; i ++){
if (i<rev[i])swap(a[i],a[rev[i]]);// If does not swap twice
}
delete[] rev;
// adjust the sequence of a to merge
for (int mid=1; mid<n; mid*=2) {// Inside the mid loop, we are ready to merge two mid sequences into a 2 * mid sequence
double unit_rad = 2 * pi / (2 * mid); // Unit Angle amplitude value
for (int i=0; i<n; i+=mid*2) {// merge two sequences of length mid at I ~ I +mid*2 into 2 * mid
for (int j = 0; j < mid; j ++){
// the logical sum within the j loop
complex<double> x(cos(j * unit_rad), inv*sin(j * unit_rad)); // x = omega_n^i
complex<double> tmp1 = a[i+j];
complex<double> tmp2 = x * a[i+j+mid]; a[i+j] = tmp1 + tmp2; a[i+j+mid] = tmp1 - tmp2; }}}}void fft(complex<double> *a, int n){
// Input coefficient polynomial and its length, in situ conversion to point value polynomial
fft_logic(a, n, 1);
}
void ifft(complex<double> *a, int n){
// Input point value polynomial and its length, in situ conversion to coefficient polynomial
fft_logic(a, n, - 1);
for(int i = 0; i < n; i ++)
a[i] /= n;
}
// Main function test
complex<double> A1[N], A2[N]; // The polynomial in the multiplication
complex<double> C[N]; // The result of the multiplication
int main(a){
// Initializes two multiplying polynomials. Note: Both multiplying polynomials and the final product polynomial need to have the same number of terms
for(int i = 0; i < N; i ++){
A1[i] = A2[i] = 0;
}
A1[0] = 1, A1[1] = 1, A1[2] = 3, A1[3] = 2; // A1(x) = 2x3 + 3x2 + x + 1
A2[0] = 4, A2[1] = 3, A2[2] = 5, A2[3] = 1; // A2(x) = x3 + 5x2 + 3x + 4
// F times F inverse
fft(A1, N);
fft(A2, N);
/* for(int i = 0; i < N; i ++) cout << A1[i] << " "; cout << endl; for(int i = 0; i < N; i ++) cout << A2[i] << " "; cout << endl; * /
for(int i = 0; i < N; i ++)
C[i] = A1[i] * A2[i];
ifft(C, N);
/ / output
for(int i = 0; i < N; i ++)
cout << C[i] << endl;
return 0;
}
Copy the codereference
- Very straightforward FFT (Fast Fourier Transform)↩
- Fast Fourier Transform (FFT) and inverse Fast Fourier Transform (IFFT)↩
- Complex c + + class↩