TinyChan

/*
Pastebin: gprej3S3
Resources:
	[GitHub] bellbind/index.html (archive.today:kRtUj)
	[GitHub] mbitsnbites/fft.js (archive.today:azlA0)
	[GitHub] neeraj1397/Fast-Fourier-Transform-in-C/C_Code.c (archive.today:hcZAX & gs3EC)
	[GitHub] corbanbrook/FFT.js (archive.today:BLuKt)
	[GitHub] rshuston/FFT-C (archive.today:ytgrF)
	[Department of Mathematics] fft.c (www․math․wustl․edu/~victor/mfmm/fourier/fft.c (periods replaced with "\u2024" because of link detection for new accounts), archive.today:j0t5A)
*/
let{cos,sin,PI,hypot,atan2,sqrt,pow,exp,log}=Math,TAU=PI*2,
	cexp=x=>({r:cos(x),i:sin(x)}),
	cabs=z=>sqrt(z.r**2+z.i**2); //hypot(z.r,z.i),
	carg=z=>atan2(z.i,z.r),
	cadd=(a,b)=>({r:a.r+b.r,i:a.i+b.i}),csub=(a,b)=>({r:a.r-b.r,i:a.i-b.i}),
	cmul=(a,b)=>({r:(a.r*b.r)-(a.i*b.i),i:(a.r*b.i)+(a.i*b.r)}),
//Verify like this on WolframAlpha: string.replace(/a\.r/g,"A").replace(/a\.i/g,"B").replace(/b\.r/g,"C").replace(/b\.i/g,"D").replace(/\*\*/g,"^").replace(/{r:(.+),i:(.+)}/g,"($1)+i($2)");
	cdiv=(a,b)=>({r:(a.r*b.r+a.i*b.i)/(b.r**2+b.i**2),i:(a.i*b.r-a.r*b.i)/(b.r**2+b.i**2)}),
	cpow=(a,b)=>({ //(A+iB)^(C+iD) = ((pow(A^2+B^2,C/2)*exp(-D*arg(A+iB))*cos(.5*D*log(A^2+B^2)+C*arg(A+iB)))+i(pow(A^2+B^2,C/2)*exp(-D*arg(A+iB))*sin(.5*D*log(A^2+B^2)+C*arg(A+iB))))
		r:pow(a.r**2+a.i**2,b.r/2)*exp(-b.i*carg(a))*cos(.5*b.i*log(a.r**2+a.i**2)+b.r*carg(a)),
		i:pow(a.r**2+a.i**2,b.r/2)*exp(-b.i*carg(a))*sin(.5*b.i*log(a.r**2+a.i**2)+b.r*carg(a))
	}),
	range=n=>[...Array(n).keys()],
	csum=a=>a.reduce((p,c)=>cadd(p,c),{r:0,i:0}),
	DFT=array=>{
		const N=array.length,t=-2*PI/N;
		return range(N).map(i=>csum(array.map((current,index)=>cmul(current,cexp(t*index*i)))));
	},
	IDFT=array=>{
		const N=array.length,t=TAU/N;
		/*return array.map((_,index)=>{
			let sum={r:0,i:0};
			for(let k=0;k<N;k++)
				sum=cadd(sum,cmul(array[k],cexp(TAU*(k/N)*index)));
			return cmul({r:1/N,i:0},sum);
		});*/
		return array.map((current,index)=>cmul({r:1/N,i:0},csum(range(N).map(k=>cmul(array[k],cexp(t*k*index))))));
	},
	FFT=array=>{ //TODO: This shouldn't be mutable? Also, add IFFT.
		let N=array.length/2,i,X=[],Y=[],a,b,c,s;
		for(i=0;i<N;++i){
			X[i]={r:array.r[2*i],i:array.i[2*i]};
			Y[i]={r:array.r[2*i+1],i:array.i[2*i+1]};
		}
		if(N>1){FFT(X);FFT(Y);}
		for(i=0;i<N;++i){
			a=-PI*i/N;
			c=cos(a);s=sin(a);
			a=c*Y.r[i]-s*Y.i[i];
			b=c*Y.i[i]+s*Y.r[i];
			array.r[i]=X.r[i]+a;
			array.i[i]=X.i[i]+b;
			array.r[i+N]=X.r[i]-a;
			array.i[i+N]=X.i[i]-b;
		}
	};