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