Instantly share code, notes, and snippets.

# wrayal/LICENSE.txt forked from 140bytes/LICENSE.txt Created May 27, 2011

Fast Fourier Transform in 139b

# 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.

 //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,[]))
 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)}
 DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE Version 2, December 2004 Copyright (C) 2011 YOUR_NAME_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.
 { "name": "FFT", "description": "Calculate the (forward) DFT...FAST", "keywords": [ "FFT", "cooley-tukey", "140b" ] }
Owner Author

### wrayal commented May 28, 2011

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

### jed commented Jul 11, 2011

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

### wrayal commented Jul 11, 2011

 @jed no problems, done!