4 ms·

Python is too slow for FFT. There is no reason to understand how FFT could be implemented in python, if at the end of the day, C or Fortran will be used [1]. [

• sampo 13y ago
  The title of the post if just "Understanding the FFT Algorithm", and his goal is to explain the algorithm. He just uses Python instead of pseudocode, to explain things. The HN title has misled you, in this respect.
• Wilya 13y ago
  Read the article. Quote for you: > "Though the pure-Python functions are probably not useful in practice, I hope they've provided a bit of an intuition into what's going on in the background of FFT-based data analysis." There's very little to be gained by reading pure Fortran code, especially if you don't know the mathematical tricks/optimisations used beforehand. The Python code, on the other hand, stays (relatively) readable. It's not extremely fast (though it stays decent, thanks to Numpy), but it's not the point.
  • af3 13y ago
    > There's very little to be gained by reading pure Fortran code, especially if you don't know the mathematical tricks/optimisations used beforehand. The Python code, on the other hand, stays (relatively) readable. Don't agree. Why trying to understand implementation in the language that will never be used in the production? And, there is a lot to gain by reading Fortran code.
    • Wilya 13y ago
      Because a good part of the optimizations are language-independent. And you need to understand these optimizations before going further. The computations which are redundant and can be done once and stored afterwards don't change depending on whether you're coding in Python of Fortran. The symmetries that you can exploit to compute less stuff don't either. The math behind is always the same. Once you have done that (and gained two or three order of magnitude in computation time), and you're still not fast enough, then okay, it's time to drop to C/Fortran and start playing bookkeeper with your memory allocations. But not before.
      • af3 13y ago
        > Once you have done that (and gained two or three order of magnitude in computation time), and you're still not fast enough, then okay, You are talking about the language (or better implementation) that is compiled to bytecode. The speed increase that you gain by optimization is of the order of magnitude smaller than by just using language that compiles to machine code. Once you understood how it's done in python, then you need to port it to fortran/c, what is the point? Fortran is not much different from python in syntax.
        • darkarmani 13y ago
          > Once you understood how it's done in python, then you need to port it to fortran/c, what is the point? At that point, why would you port it to fortran/c instead of using FFTW? The whole point of the exercise was to learn about and optimize the algorithm. If you can learn the easiest using python, why wouldn't you do your exploration in python, since going from python to your language of choice should be the easiest part of the exercise if you choose to do that.
    • dbaupp 13y ago
      > Why trying to understand implementation in the language that will never be used in the production? It's the underlying mathematics that's most interesting: that's how one goes from O(n^2) to O(n log n). And the mathematics is language independent, so it might as well be demonstrated in a reasonably accessible way.
    • coldtea 13y ago
      >Why trying to understand implementation in the language that will never be used in the production? Because the end goal is understanding the algorithm, NOT writing production code. Those reading the article will never even write a FFT function anyway, since you can use ready made highly optimized versions. So knowing what the production code looks like is totally moot to them. It's like you're arguing why ever use pseudo-code. Because it's readable, makes the process easy to follow, and doesn't contain all the boilerplate junk you'd need to get performance in a production implementation. Python serves this role very well, with the added benefit that it's not even pseudo. Plus, ever heard of prototyping?
  • sampo 13y ago
    "There's very little to be gained by reading pure Fortran code, especially if you don't know the mathematical tricks/optimisations used beforehand. The Python code, on the other hand, stays (relatively) readable." Depends. His first Python code was: x = np.asarray(x, dtype=float) N = x.shape[0] n = np.arange(N) k = n.reshape((N, 1)) M = np.exp(-2j * np.pi * k * n / N) return np.dot(M, x) I can write more or less the same in Fortran: n = reshape([(i, i=0,len-1)], shape=[1,len]) k = transpose(n) M = exp(-2 * j * pi * matmul(k,n) / len) res = matmul(M, x) But of course Fortran is a typed language, so I need to explicitly write the types for everything, so my whole function gets longer pure function dft_slow(x, len) result(res) complex, intent(in) :: x(len) integer, intent(in) :: len complex :: n(1,len), k(len,1), M(len, len), res(len) integer :: i n = reshape([(i, i=0,len-1)], shape=[1,len]) k = transpose(n) M = exp(-2 * j * pi * matmul(k,n) / len) res = matmul(M, x) end function dft_slow and so yes, maybe less readable. P.S. One must also define somewhere global constants complex, parameter :: j = (0,1) ! imaginary unit real, parameter :: pi = acos(-1.) for the above function to work. Also everything is by default in single precision here.
    • vonmoltke 13y ago
      I have a sudden urge to find an excuse to write Fortran again.
• weland 13y ago
  The usual approach is to use the foreign function interface and work with FFTW or some other high-performance library.
  • af3 13y ago
    that's correct. AFAIK the point of the OP was to understand how that "high-performance library" works.