Fast Fourier Transform in 139b

README.md

FFT - CT

An implementation of the Cooley-Tukey FFT algorithm in 139bytes of javascript.

The implementation uses recursion for space reasons - probably not so suitable for 10^6 modes+...

There are two slightly immoral things here: two rotations (one complex, one array, neither "suspicious") are included that are not existing libraries (but should be). Also, concat() is turned into c(). Again, more humane.

Note that exact output is a convention. E.g. Mathematica disagrees with Wikipedia; I give exactly that given by CT.

annotated.js

//JS really should be taught to handle complex numbers, and operator overloading <3
function C(real,imaginary){
	this.x=real;
	this.y=imaginary;
}
C.prototype.m=function(b){ //Complex multiplication
	return new C(this.x*b.x-this.y*b.y,this.x*b.y+this.y*b.x);
}
C.prototype.toString=function(){
	return this.x+"+i"+this.y
}
C.e=function(a) { //Complex exponentiation
	return new C(Math.exp(a.x)*Math.cos(a.y),Math.exp(a.x)*Math.sin(a.y));
}
C.prototype.a=function(b) { //Complex Addition
	this.x=this.x+b.x;
	this.y=this.y+b.y;
	return;
}
s=function(a,b) { //Complex subtraction
	return new C(a.x-b.x,a.y-b.y);
}
r=function(d,l) { //discrete rotation on el't [i]
	return C.e(new C(0,-3.14159265358979323846264*d)).m(l)
}
Array.prototype.r = function(){this.unshift(this.pop()); return this.pop()}; //rotate and pop. Neat but too long
Array.prototype.c = Array.prototype.concat; //to save space; unavoidable



myFn=function e(
	X,		//The sample values passe
	N,		//The number of samples (=no. of modes)
	Z,		//The spare array, to hold interleaved samples etc
	i		//Looping variable
	){
		Z=[]; 			//Initialise Z
		if(N>1){		//In the final "N=1" case we just want to return X
			for(		
				i=N/=2;	//Halve the modes at each step
				i;	//Loop while i is non-zero
				Z[--i]=X.r()	//we rotate and pop
			);
			for(
				X=e(X,N),Z=e(Z,i=N);	//Cooley-Tukey recursion
				i--;					//looping
				X[i].a(t))Z[i]=s(X[i],t=r(i/N,Z[i])	//Re-combining with complex rotation
			)
		}
	return X.c(Z)	//and return
}



//Try this to test:
alert(myFn([new C(18,-13),new C(0,1),new C(1,-1),new C(5,3)],4,[]))

index.js

function e(X,N,Z,i){Z=[];if(N>1){for(i=N/=2;i;Z[--i]=X.r());for(X=e(X,N),Z=e(Z,i=N);i--;X[i].a(t))Z[i]=s(X[i],t=r(i/N,Z[i]))}return X.c(Z)}

LICENSE.txt

            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
                    Version 2, December 2004

 Copyright (C) 2011 YOUR_NAME_HERE <YOUR_URL_HERE>

 Everyone is permitted to copy and distribute verbatim or modified
 copies of this license document, and changing it is allowed as long
 as the name is changed.

            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

  0. You just DO WHAT THE FUCK YOU WANT TO.

package.json

{
  "name": "FFT",

  "description": "Calculate the (forward) DFT...FAST",

  "keywords": [
    "FFT",
    "cooley-tukey",
    "140b" 
  ]
}

With another 4 bytes, c() could become concat() again. But there's nothing to be done about the rotations I believe

hey @wrayal, would you mind taking the comments out of your package.json?

@jed no problems, done!