Skip to content

Instantly share code, notes, and snippets.

@wrayal
Forked from 140bytes/LICENSE.txt
Created May 27, 2011 16:03
Show Gist options
  • Save wrayal/995571 to your computer and use it in GitHub Desktop.
Save wrayal/995571 to your computer and use it in GitHub Desktop.
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 <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.
{
"name": "FFT",
"description": "Calculate the (forward) DFT...FAST",
"keywords": [
"FFT",
"cooley-tukey",
"140b"
]
}
@wrayal
Copy link
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
Copy link

jed commented Jul 11, 2011

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

@wrayal
Copy link
Author

wrayal commented Jul 11, 2011

@jed no problems, done!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment