lambdaspeech :: lispology

1 | list | login |load

| |

_h3 [[DFT]] | JS_FFT | [[LT_FFT|?view=lispology4]]

_h2 the Fast Fourier Transform {sup (Javascript)}

_img https://www.ritchievink.com/img/post-5-fft/fig_2.png

{center {h1 {code X(N) = Σ{sub n=0}{sup N-1} 1/n.sin(2Πn/N)}}}

_p See [[rosettacode.org/wiki/Fast_Fourier_transform|http://rosettacode.org/wiki/Fast_Fourier_transform#C.2B.2B]]

{script ;;

function Cnew(x, y) { return {re:x, im:(y || 0)} }
function isC(x) { return (x instanceof Object)? true : false }
function Cadd(x,y) { return {re:x.re+y.re, im:x.im+y.im} }  
function Csub(x,y) { return {re:x.re-y.re, im:x.im-y.im} }
function Cmul(x,y) {
  return {re:x.re * y.re - x.im * y.im, im:x.re * y.im + x.im * y.re} 
}
function Cexp(x) {
  var xx = Math.exp(x.re);
  return {re:xx * Math.cos(x.im), im:xx * Math.sin(x.im)}
}

function square_sample(n) {
  var a = [];
  for (var i=0; i < n; i++)
    a.push( 1 );
  for (var i=0; i < n; i++)
    a.push( 0 );
  return a
}

function sample_array2complex_array(x) {
  for (var cx=[], i=0; i < x.length; i++)
    cx[i] = Cnew(x[i],0);
  return cx
}

setTimeout( display,1 )
}

{pre  {@ style="box-shadow:0 0 8px #000; padding:10px;"} °°
1) the FFT function
 
function fft(x) {
  if (x.length <= 1) return x; 
  var N  = x.length, 
      hN = N/2,
      a  = -2*Math.PI,  
      even = [], 
      odd  = [];
  for(var i = 0; i < x.length/2; i++) {
    even[i] = x[i*2];
    odd[i]  = x[i*2+1];
  }
  even = fft(even);
  odd  = fft(odd);  
  for(var k = 0; k < hN; k++) {
    var phi = Cmul(odd[k], Cexp( Cnew( 0, a*k/N )));
    x[k]    = Cadd( even[k], phi )
    x[k+hN] = Csub( even[k], phi )
  }
  return x 
}
°°}

{pre °°

2) Cnumbers functions

3) testing

function square_sample(n) {
  var a = [];
  for (var i=0; i < n; i++) a.push( 1 );
  for (var i=0; i < n; i++) a.push( 0 );
  return a
}

function sample_array2complex_array(x) {
  for (var cx=[], i=0; i < x.length; i++)
    cx[i] = Cnew(x[i],0);
  return cx
}

setTimeout( display,1 )
°°}

_h2 display

{prewrap {div {@ id="output"}...}}

_p We have found the first sines {code [1 1/1] [1 1/3] [1 1/5] [1 1/7] [1 1/9] [1 1/11] [1 1/13] [1 1/15] [1 1/17] ...} according to 
{center {code X(N) = Σ{sub n=0}{sup N-1} 1/n.sin(-2Πin/N)}}

_p Next step: translate from JS to '{lambda talk}.