5 ms·

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 o

by gp7 8y ago

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-Practice https://cnx.org/contents/ulXtQbN7@15/Implementing-FFTs-in-Pr...

martyalain 8y ago
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 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 8y ago
"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 http://lambdaway.free.fr/lambdaspeech/?view=lispology.
- gp7 8y ago
  You copy rather than use strided accesses. It's the same algorithm.
  - martyalain 8y ago
    " 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 8y ago
      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?

by gp7 8y ago

martyalain 8y ago

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 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 8y ago

"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 http://lambdaway.free.fr/lambdaspeech/?view=lispology.

gp7 8y ago
You copy rather than use strided accesses. It's the same algorithm.
- martyalain 8y ago
  " 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 8y ago
    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?