[gp7]

The code is mostly equivalent to the recursive form found in the wikipedia article on the cooley-tukey algorithm. This is a good one to learn from, as its not only a simple formulation but it forms the basis of modern optimised FFTs such as FFTW (source[1], from the authors of FFTW).

As an aside, I also find the non-recursive, breadth-first, form easy to derive thru a process of code transformations of the depth-first form; explanations that start breadth-first are somewhat bewildering

[1] https://cnx.org/contents/ulXtQbN7@15/Implementing-FFTs-in-Pr...

[martyalain]

Actually my quest is to write the FFT code at the lambda-calculus level. Why? First for the fun and also because I consider that lambda-calculus is for the mind what assembly language is for the computer. See http://lambdaway.free.fr/lambdaspeech/?view=PLR. In this page I would like to replace the inefficient unary numeration by a more efficient decimal position numeration and I guess that FFT, the Katsuba or any divide & conquer algorithm could be useful. It should be pleasant for the mind and could overcome limits of the JS numbers implementation.

[martyalain]

"The code is mostly equivalent to the recursive form found in the wikipedia article on the cooley-tukey algorithm" I don't think so. A JS translation of the code shown in wikipedia can be seen in http://lambdaway.free.fr/lambdaspeech/?view=lispology.

[gp7]

You copy rather than use strided accesses. It's the same algorithm.

[martyalain]

" You copy rather than use strided accesses. " I don't understand "strided accesses". « Plagiarism is stealing, copying is create. » I just translated the code in the lambdatalk language and added missing examples, something that I consider mandatory.

[gp7]

Sorry, I'm not accusing you of anything. By strided accesses I mean when you access elements of an array sequentially using some step size. Think loops with `i += stride` instead of `i++`. In the wikipedia pseudocode this is done implicitly using the 's' parameter. Notice that, in the version you implemented, you split the input into even and odd parts explicitly; you can achieve the same end by accessing the input array in a certain order as you are performing the mathematical operations. This is what the wikipedia pseudocode does. If you've seen other versions of the FFT with a bit reversal step, this is also where that comes in.

Check this out (javascript):

  function permute1(x) { 
      if (x.length == 1) return x;
      let even = [];
      let odd = []; 
      for (let i = 0; i < x.length; i += 2) { 
           even[i / 2] = x[i];
           odd[i / 2] = x[i + 1];
      }
      return [].concat(permute1(even), permute1(odd));
  }

  function permute2(x, offset, stride) {
      if (!offset) offset = 0;
      if (!stride) stride = 1;
      if (stride >= x.length) return [x[offset]];
      return [].concat(permute2(x, offset, stride * 2), permute2(x, offset + stride, stride * 2));
  }
  
  function permute3(x) {
      let result = [];
      for (let i = 0; i < x.length; i++) {
          let k = i;
          // pretend 32-bit ints
          k = ((k >> 1) & 0x55555555) | ((k & 0x55555555) << 1);
          k = ((k >> 2) & 0x33333333) | ((k & 0x33333333) << 2);
          k = ((k >> 4) & 0x0F0F0F0F) | ((k & 0x0F0F0F0F) << 4);
          k = ((k >> 8) & 0x00FF00FF) | ((k & 0x00FF00FF) << 8);
          k = ( k >> 16             ) | ( k               << 16); 
          k = k >> (64 - Math.log2(x.length));
          if (k < 0) k += x.length; // fix up due to signed ints
          result[i] = x[k];
      }
      return result;
  }

For arrays with power of two sizes, these perform the same permutation (but fail differently for non power of two sizes). Note that, with permute1, we effectively iterate over the entire input log2(n) times, so this is an O(nlogn) algorithm!

edit: also, i think i may have misunderstood the relationship between your js version and your lambdatalk version. They seem to be the same to me?

[martyalain]

Thank you for your clever code. This morning I improved a little the JS code in http://lambdaway.free.fr/lambdaspeech/index.php?view=lispolo... and I plan to learn, understand and insert your code in the fft() function.

Yes there is a relationship between the JS version and its translation into lambdatalk. My project is to replace the array based version by a list based version so that I can replace in this page http://lambdaway.free.fr/lambdaspeech/?view=PLR the inefficient unary numeration based implementation of numbers (using standard Church numbers or just lists) by a decimal position numeration. Standard multiplication of words seen as polynoms being O(n^2) I need to go further and implement fast multiplication. So my interest in FFT.

As you could see in http://lambdaway.free.fr/lambdaspeech/meca/JS.js, the lambdatalk's interpreter is a regular expression window running on the code (not an AST) and replacing in situ expressions by their values. A kind of Turing machine. I like the idea of overcoming limits of JS numbers using nothing but words and simple substitutions on words.