package com.maths;
import java.util.ArrayList;
import java.util.Collections;
/**
* Class for calculating the Fast Fourier Transform (FFT) of a discrete signal using the Cooley-Tukey algorithm.
*
* @author Ioannis Karavitsis
* @version 1.0
* */
public class FFT
{
/**
* This class represents a complex number and has methods for basic operations.
*
* More info:
* https://introcs.cs.princeton.edu/java/32class/Complex.java.html
* */
static class Complex
{
private double real, img;
/**
* Default Constructor.
* Creates the complex number 0.
* */
public Complex()
{
real = 0;
img = 0;
}
/**
* Constructor. Creates a complex number.
*
* @param r The real part of the number.
* @param i The imaginary part of the number.
* */
public Complex(double r, double i)
{
real = r;
img = i;
}
/**
* Returns the real part of the complex number.
*
* @return The real part of the complex number.
* */
public double getReal()
{
return real;
}
/**
* Returns the imaginary part of the complex number.
*
* @return The imaginary part of the complex number.
* */
public double getImaginary()
{
return img;
}
/**
* Adds this complex number to another.
*
* @param z The number to be added.
* @return The sum.
* */
public Complex add(Complex z)
{
Complex temp = new Complex();
temp.real = this.real + z.real;
temp.img = this.img + z.img;
return temp;
}
/**
* Subtracts a number from this complex number.
*
* @param z The number to be subtracted.
* @return The difference.
* */
public Complex subtract(Complex z)
{
Complex temp = new Complex();
temp.real = this.real - z.real;
temp.img = this.img - z.img;
return temp;
}
/**
* Multiplies this complex number by another.
*
* @param z The number to be multiplied.
* @return The product.
* */
public Complex multiply(Complex z)
{
Complex temp = new Complex();
temp.real = this.real*z.real - this.img*z.img;
temp.img = this.real*z.img + this.img*z.real;
return temp;
}
/**
* Multiplies this complex number by a scalar.
*
* @param n The real number to be multiplied.
* @return The product.
* */
public Complex multiply(double n)
{
Complex temp = new Complex();
temp.real = this.real * n;
temp.img = this.img * n;
return temp;
}
/**
* Finds the conjugate of this complex number.
*
* @return The conjugate.
* */
public Complex conjugate()
{
Complex temp = new Complex();
temp.real = this.real;
temp.img = -this.img;
return temp;
}
/**
* Finds the magnitude of the complex number.
*
* @return The magnitude.
* */
public double abs()
{
return Math.hypot(this.real, this.img);
}
/**
* Divides this complex number by another.
*
* @param z The divisor.
* @return The quotient.
* */
public Complex divide(Complex z)
{
Complex temp = new Complex();
temp.real = (this.real*z.real + this.img*z.img) / (z.abs()*z.abs());
temp.img = (this.img*z.real - this.real*z.img) / (z.abs()*z.abs());
return temp;
}
/**
* Divides this complex number by a scalar.
*
* @param n The divisor which is a real number.
* @return The quotient.
* */
public Complex divide(double n)
{
Complex temp = new Complex();
temp.real = this.real / n;
temp.img = this.img / n;
return temp;
}
}
/**
* Iterative In-Place Radix-2 Cooley-Tukey Fast Fourier Transform Algorithm with Bit-Reversal.
* The size of the input signal must be a power of 2. If it isn't then it is padded with zeros and the output FFT will be bigger than the input signal.
*
* More info:
* https://www.algorithm-archive.org/contents/cooley_tukey/cooley_tukey.html
* https://www.geeksforgeeks.org/iterative-fast-fourier-transformation-polynomial-multiplication/
* https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
* https://cp-algorithms.com/algebra/fft.html
*
* @param x The discrete signal which is then converted to the FFT or the IFFT of signal x.
* @param inverse True if you want to find the inverse FFT.
* */
public static void fft(ArrayList