0

Hi I'm working on a program to analyze sound files and I need to do a DFT on a 1 second array which often is 44100 samples.

So what I need is a 1D FFT algorithm working on arbitrary length, i.e. not a power of 2.

Any ideas?

Andreas Arvidsson
  • 25
  • 5
  • 3
    You can add zeros to make array length power of two (zero padding) – MBo Jan 07 '16 at 13:29
  • 2
    If you really need a 44100-length FFT, then you're probably doing something wrong. The most efficient algorithms for arbitrary-length DFTs internally use a larger power-of-two FFT, so even in the best case, a length 44100 FFT takes longer than a length 65536 FFT. – Matt Timmermans Jan 07 '16 at 13:58
  • As 44100=2²3²5²7², the total time will be very roughly proportional to `2x(2+3+5+7)`, to be compared to `16x2`. –  Jan 07 '16 at 14:47
  • without power of two dataset size you can not take full advantage of the recursion turning **FT** `O(n^2)` to **FFT** `O(n.log(n))` Instead you subdivide by `2` until you hit the wall and compute the rest normally slowing things down considerably not to mention added conditions messing up with cache ... The zero padding is usually faster (if coded right) even if the dataset is enlarged .... Also see [How to compute Discrete Fourier Transform?](http://stackoverflow.com/a/26355569/2521214) – Spektre Jan 07 '16 at 18:17
  • 2
    @Spektre Zero-padding will give you a fast implementation of that can obscure what you're looking for impossible because of "ringing". To see the issue draw an arbitrary smooth repeating curve over 44100 points that isn't 0 at 0, zero-pad it out to 65536 points and look at the graph. See the sudden cliffs at 44099 to 44100 and again at 65535 to 0? Most of the terms in the FFT will be spent trying to recreate those cliffs, completely swamping the shape of your curve. – btilly Jan 07 '16 at 20:45

1 Answers1

4

The https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm is USUALLY used for binary splits, but actually handles arbitrary factorizations. As long as your number factorizes completely into small numbers (yours is 2*2*3*3*5*5*7*7) this will give a fairly efficient FFT. (See the General Factorizations section.)

There are other FFT algorithms known that can handle arbitrary sizes, but they are much slower (though better than naive). See https://en.wikipedia.org/wiki/Chirp_Z-transform#Bluestein.27s_algorithm for one.

http://www.nayuki.io/page/free-small-fft-in-multiple-languages has implementations of the general Cooley-Tukey FFT algorithm in a number of languages, including JavaScript. It doesn't do an efficient implementation for arbitrary primes, but you don't have any large ones to deal with.

btilly
  • 43,296
  • 3
  • 59
  • 88