+ JavaScript の質問用スレッド vol.102 +

>>106
xrに配列、xiに同じ長さの配列（0を入れとく）、mに2の何乗ぶん変換するかを入れてね〜

function fft(xr,xi,m){
var a,b,g,h,i,j,k,l,m,n,o,p,q;
var stank,ctank,xd;
n=1<<m;stank=new Array(n/2);ctank=new Array(n/2);a=0;b=Math.PI*2/n;
for(i=0;i<n/2;i++){stank[i]=Math.sin(a);ctank[i]=Math.cos(a);a=a+b};
l=n;h=1;for(g=0;g<m;g++){l/=2;k=0;
for(q=0;q<h;q++){p=0;
for(i=k;i<l+k;i++){j=i+l;
a=xr[i]-xr[j];b=xi[i]-xi[j];
xr[i]+=xr[j];xi[i]+=xi[j];
if(p==0){xr[j]=a;xi[j]=b;}else{xr[j]=a*ctank[p]+b*stank[p];xi[j]=b*ctank[p]-a*stank[p];};
p+=h;};k+=l+l;};h+=h;};j=n/2;
for(i=1;i<n-1;i++){
if(j<i){xd=xr[i];xr[i]=xr[j];xr[j]=xd;xd=xi[i];xi[i]=xi[j];xi[j]=xd;};k=n/2;
for(;;){if(j<k)break;j-=k;k/=2;};j+=k;};};