## Challenge Overview

Our client **BG100 **has a vector of samples representing Complex numbers with real and imaginary parts in the range -1.0 <= x < 1.0, mapped to 16 bit integers as int(x * 2^15), so that -1.0 is mapped to -32768 and (1.0 – 1.0/32768.0) is mapped to 32767.

As part of this challenge, we need to create a set of functions, callable from a **C** program that performs **FFT** and **inverse** **FFT** of such vectors, optimized for the **x86 AVX2** architecture.

Detailed requirements

The Complex numbers are defined as following:

typedef struct {

int16_t re;

int16_t im;

} Complex;

The twiddle factors needed should be initialized at run-time.

The function prototypes may look like:

void init_fft(); // Initialize FFT twiddle factors

void fft(Complex *out, Complex *in); // Perform out = FFT(in)

void init_ifft(); // Initialize inverse FFT twiddle factors

void ifft(Complex *out, Complex *in); // Perform out = inverse FFT(in)

Each function should also print the CPU time and the CPU cycles used.

**NOTE: **Customer expects the Library to work on a single core as a pure library. Solutions that spawn additional worker-threads, are not valid and will be rejected.

**Target OS: **Linux with kernel v4