Any Good Learning resource for FFT

joney_000 · November 7, 2016, 12:29am

Some Good Tutorial and Implementation will helpful to understand Fast Fourier Transform .

srd091 · November 7, 2016, 12:58am

You can refer to this link. It contains different variations of -FFT along with the code snippets.

This link also contains the description of FFT in a very helpful manner.

miike · November 7, 2016, 12:28pm

you can try this video tutorial-: https://www.youtube.com/watch?v=qrGBpexbT-c
you can also learn from e-maxx http://e-maxx.ru/algo/fft_multiply
(translate it with google translate)

neilit1992 · November 7, 2016, 1:33pm

Check This Link, It might be helpful

chilling · November 7, 2016, 7:18pm

github.com

IpankajI/programming/blob/master/FFTPolyMult.cpp

#include <bits/stdc++.h>
#define cpx complex<double>
#define pi 3.14159265359
using namespace std;
vector<cpx> FFT(vector<int> vc){
	int n=vc.size();
	if(n==1){
		vector<cpx> tmp;
		tmp.push_back(cpx(1.0*vc[0],0.0));
		return tmp;
	}
	int half=n/2;
	vector<int> v0,v1;
	for(int i=0;i<half;i++){
		v0.push_back(vc[i<<1]);
		v1.push_back(vc[i<<1^1]);
	}
	vector<cpx> Y0=FFT(v0),Y1=FFT(v1),foo(n);
	cpx w(1,0),wn(cos(2*pi/n),sin(2*pi/n));
	for(int i=0;i<half;i++){

This file has been truncated. show original

avm · June 28, 2018, 4:23am

Introduction

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein “Introduction to Algorithms, 3rd Edition”, Chapter 30 - Polynomials and the FFT

Advanced

Jörg Arndt “Matters Computational”

https://www.jjj.de/fxt/