Hacker News Reader

Comment by mdda | Hacker News Reader

Not explicitly stated in the article : The reason this is so fast is that you're only detecting a single frequency. If you wanted to detect a few (M, say), you'd have to keep updating M sets of Qs. While M<<N this is really efficient (and each one looks like a notch filter, or something).

But for larger M, it's better to do the FFT, since that gives you back O(N) frequencies in O(NlogN) time - because of the tricks it can do with N if it's a power of 2.

View on HN

> with N if it's a power of 2.

with N if it's highly composite. See, e.g. http://www.fftw.org/ which works fairly well even for non-powers of 2.

Very interesting : I was actually thinking about redoing the spectrometer music visualization for MythTV to be use 'piano keyboard' pitches (rather than the FFT that they're using at the moment). And I came to the conclusion that some kind of recurrence (short) resonant filter would do the trick (with 88 different copies) - but never got further than that, since I had limited imagination about what algorithms to search for. Unfortunately, I've got overwhelmed with other projects now...

If you only want to detect one frequency, can't you jut use the "slow" fourier transform?

Yes, the discrete Fourier transform (DFT) detects N frequencies in parallel, where N is the block size, and you can disregard the uninteresting frequencies. The fast Fourier transform (FFT) is an efficient algorithm that computes the DFT. For detecting M frequencies where M << N, the Goertzel algorithm requires less computation than the FFT. Also, the Goertzel algorithm allows targeting more exact frequencies regardless of the sampling rate (Fs), while the FFT's bins have a fixed spacing of ±Fs/N.

As with everything, there are trade-offs associated with these three options.

This looks like a row of a DFT, but using the history variables and the single cosine to avoid computing the coefficients from scratch.

Reply on news.ycombinator.com