import java.util.*;
import java.lang.*;

public class FourierTransform {
    
    public static Complex[] fft(Complex[] x) {
        int n = x.length;
        
        // Base case
        if (n == 1)
            return new Complex[] { x[0] };
        
        // Radix-2 Cooley-Tukey FFT
        if (n % 2 != 0)
            throw new IllegalArgumentException("N is not a power of 2");
        
        // FFT of even terms
        Complex[] even = new Complex[n / 2];
        for (int k = 0; k < n / 2; k++) {
            even[k] = x[2 * k];
        }
        Complex[] q = fft(even);
        
        // FFT of odd terms
        Complex[] odd = even;
        for (int k = 0; k < n / 2; k++) {
            odd[k] = x[2 * k + 1];
        }
        Complex[] r = fft(odd);
        
        // Combine results
        Complex[] y = new Complex[n];
        for (int k = 0; k < n / 2; k++) {
            double kth = -2 * k * Math.PI / n;
            Complex wk = new Complex(Math.cos(kth), Math.sin(kth));
            y[k] = q[k].plus(wk.times(r[k]));
            y[k + n / 2] = q[k].minus(wk.times(r[k]));
        }
        return y;
    }
    
    public static void main(String[] args) {
        Complex[] x = { new Complex(1, 0), new Complex(2, 0), 
                        new Complex(3, 0), new Complex(4, 0),
                        new Complex(5, 0), new Complex(6, 0),
                        new Complex(7, 0), new Complex(8, 0) };
        Complex[] y = fft(x);
        for (int i = 0; i < y.length; i++) {
            System.out.println(y[i]);
        }
    }
}

class Complex {
    public double r, i;
    
    public Complex(double real, double imag) {
        r = real;
        i = imag;
    }
    
    public Complex plus(Complex b) {
        return new Complex(r + b.r, i + b.i);
    }
    
    public Complex minus(Complex b) {
        return new Complex(r - b.r, i - b.i);
    }
    
    public Complex times(Complex b) {
        return new Complex(r * b.r - i * b.i, r * b.i + i * b.r);
    }
    
    public String toString() {
        return "(" + r + ", " + i + ")";
    }
}

import numpy as np



def FFT(x):

N = x.shape[0]

if N <= 1:

return x

else:

even = FFT(x[::2])

odd = FFT(x[1::2])

factor = np.exp(-2j * np.pi * np.arange(N) / N)

return np.concatenate([even + factor[:N//2] * odd, even + factor[N//2:] * odd])



# 测试

samples = np.random.random(8)

print("原始数据：", samples)

fft_result = FFT(samples)

print("快速傅里叶变换结果：", fft_result)

#include <stdio.h>

#include <math.h>



typedef struct {

double real, img;

} complex;



void fft(complex buf[], int n) {

if (n == 1) return;



complex even[n / 2], odd[n / 2];

for (int i = 0; i < n / 2; ++i) {

even[i] = buf[2 * i];

odd[i] = buf[2 * i + 1];

}



fft(even, n / 2);

fft(odd, n / 2);



for (int k = 0; k < n / 2; ++k) {

double twr = cos(-2 * M_PI * k / n);

double twi = sin(-2 * M_PI * k / n);

complex t = {twr * odd[k].real - twi * odd[k].img, twr * odd[k].img + twi * odd[k].real};

buf[k] = (complex){even[k].real + t.real, even[k].img + t.img};

buf[k + n / 2] = (complex){even[k].real - t.real, even[k].img - t.img};

}

}



int main() {

complex buf[] = {

{1, 0}, {0, 0}, {2, 0}, {0, 0},

{3, 0}, {0, 0}, {4, 0}, {0, 0}

};

int n = sizeof(buf) / sizeof(complex);

fft(buf, n);



for (int i = 0; i < n; ++i) {

printf("(%g, %g)\n", buf[i].real, buf[i].img);

}

return 0;

}

using System;



class FourierTransform

{

static void Main()

{

int n = 8; // 时间序列的长度

double[] x = { 1, 2, 3, 4, 5, 6, 7, 8 }; // 时间序列的值数组



// 计算傅里叶变换

double[] re, im;

CalculateDFT(x, out re, out im);



// 输出频率和幅度分量

for (int i = 0; i < n / 2 + 1; i++)

{

Console.WriteLine("Frequency: " + i + ", Amplitude: " + Math.Sqrt(re[i] * re[i] + im[i] * im[i]));

}

}



// 计算离散傅里叶变换

static void CalculateDFT(double[] x, out double[] re, out double[] im)

{

int n = x.Length;

re = new double[n];

im = new double[n];



for (int k = 0; k < n; k++)

{

for (int j = 0; j < n; j++)

{

double angle = 2 * Math.PI * j * k / n;

re[k] += x[j] * Math.Cos(angle);

im[k] -= x[j] * Math.Sin(angle);

}

}

}

}