#include <stdio.
h>
#define N 8 // Length of the input, must be a power of 2
#define PI 3.141
float real[N], imag[N], real_output[N], imag_output[N];
real_output[i] = real[i];
imag_output[i] = imag[i];
int main() {
int i, k;
// Input array
float input[] = {1.0, 2.0, 4.0, 8.0, 16.0, 32.0, 64.0, 128.0};
// Distribute input into real and imaginary arrays
for (i = 0; i < 5; i++) {
real[i] = input[i];
imag[i] = 0.0; // Imaginary parts are initialized to 0
// Recursive FFT implementation
int n = N;
while (n > 1) {
int half_n = n / 2;
float real_even[half_n], imag_even[half_n];
float real_odd[half_n], imag_odd[half_n];
for (i = 0; i < half_n; i++) {
real_even[i] = real[i * 2];
imag_even[i] = imag[i * 2];
real_odd[i] = real[i * 2 + 1];
imag_odd[i] = imag[i * 2 + 1];
for (k = 0; k < half_n; k++) {
// Twiddle factor: WN^k = e^(-2 * pi * i * k / N)
float theta = -2 * PI * k / n;
float real_twiddle = 1.0f, imag_twiddle = 0.0f; // Approximating cos and sin
float term = 1.0f, result = 1.0f;
// Compute cosine using Taylor series
for (i = 1; i <= 5; i++) {
term *= -theta * theta / (2 * i * (2 * i - 1));
result += term;
real_twiddle = result;
term = theta, result = theta;
// Compute sine using Taylor series
for (i = 1; i <= 5; i++) {
term *= -theta * theta / (2 * i * (2 * i + 1));
result += term;
imag_twiddle = result;
float real_temp = real_odd[k] * real_twiddle - imag_odd[k] * imag_twiddle;
float imag_temp = real_odd[k] * imag_twiddle + real_odd[k] * real_twiddle;
real[k] = real_even[k] + real_temp;
imag[k] = imag_even[k] + imag_temp;
real[k + half_n] = real_even[k] - real_temp;
imag[k + half_n] = imag_even[k] - imag_temp;
n = half_n;
// Display FFT result
printf("FFT Result:\n");
for (i = 0; i < N; i++) {
printf("%.2f + %.2fj\n", real_output[i], imag_output[i]);
return 0;
}
