package at.priv.toastfreeware.jguitartuner;

import java.util.Vector;

public class Calculus {

	/** Calculates the discrete fourier transform. See Oppenheim, Schafer, page 543 */
	public static Vector<Complex> fft(Vector<Complex> x) {
		final int N = x.size();
		final Complex exponent = new Complex(0, -2 * Math.PI / N); // -j(2*pi/M)
		Vector<Complex> X = new Vector<Complex>(N);
		for (int k = 0; k != N; ++k) {
			Complex sum = new Complex();
			final Complex exponentk = new Complex(exponent);
			exponentk.multiply(k);
			for (int n = 0; n != N; ++n) {
				sum.add(Complex.multiply(x.get(n), Complex.exp(Complex.multiply(exponentk, n))));
			}
			X.add(sum);
		}
		return X;
	}

}