I once made an algorithm that does frequency analysis without using the Fourier Transform or any variation of it. The complexity of this algorithm was 1 iteration per sample per frequency being monitored. I since lost the code, and I forgot how I did it, but I think it might have been like this, since it is one of the ideas I had at the time: It's possible to get the level of any particular freqency by convolving a signal with a sine wave of that frequency. In The Scientist and Engineer's Guide to Digital Signal Processing, Second Edition, I read that rotating a signal you're convolving for the purpose of finding the level of correlation has no effect on the result. So, instead of convolving the sine wave of the given frequency by the last N samples of the input signal each time a new sample comes in, I acted as if I'd rotated the input signal by one sample each time I received a new sample, then I only had to do an operation for that sample, plus subtracting the values incurred from the operations performed N samples ago, since the window of convolution had just slid past that sample. (I kept an array of these values, or maybe a deque or something.) I actually remember subtracting *fractions* of samples, but I don't remember why I thought I might have needed to do that. I do remember I wasn't sure whether it was necessary or even sensible. It's possible that the idea I implemented isn't even the one described here, or it's possible that I just can't think of why I'd need to do that now since I've forgotten all the details of convolution. I don't remember the details of how convolution works or how you get a signal level from it, but I guess I must have had to act as though the signal I'm convolving by (the sine wave of the given frequency) were rotating by 1 each time a sample came in too. I made a quick-and-dirty 2D graph of frequencies vs. time for an input signal, and it seemed to look realistic, though I had to divide the results by an arbitrary amount to get them within the proper range to display. I mean, I'm sure you can somehow calculate the theoretical amount one should divide by, but I didn't know what that value was, or I think I may have derived some value but it didn' work out, so I just employed trial and error. i think d:\py\convolve.py might be some code related to this experiment. here is the code: from __future__ import division import wave, math, struct import pygame import funcs nfreqs = 88 fpo = 12 refpt = 49 reffreq = 440 mult = 2**(1/fpo) freqs = [reffreq*mult**(x-(refpt-1)) for x in xrange(nfreqs)] pygame.init() s = pygame.display.set_mode((640,480)) wr = wave.open("d:\\windows\\media\\ringin.wav", "rb") wr = wave.open("c:\\windows\\media\\chimes.wav", "rb") nf = wr.getnframes() sw = wr.getsampwidth() nc = wr.getnchannels() fr = wr.getframerate() fs = wr.readframes(nf) ch1s = funcs.window(fs, sw, sw*nc) if sw == 2: ch1 = [struct.unpack_from("<h", x)[0] for x in ch1s] print ch1[:10] wavelets = [[math.sin(x/(fr/freq)*2*math.pi) for x in xrange(int(fr/freq))] for freq in freqs] maxs = [sum( for sn, s in enumerate(ch1): for wn, wavelet in enumerate(wavelets): if len(wavelet) <= sn: r = sum((ws*ch1[sn-wsn] for (wsn, ws) in enumerate(wavelet))) print sn, wn, r ---------------------------------------- OK, here's a bettetr description of my reasoning and what I did originally: 1. Correlation is convolving a signal by another waveform. Each element of the result is the degree to which the waveform is present in the signal. 2. I surmise that if you convolve a signal by a sine wave, you'll find out how much of that frequency is in that signal. Probably wrong. 3. I figure that the actual rotation/phase of the waveform is irrelevant, because even if you convolve correctly and start from the beginning of the waveform in each iteration, its phase will only actually line up with that frequency in the input signal's phase 1/freq times per second. This allows us to take a short cut. 4. We can convolve the last n input samples with the sine wave for each new input sample we receive by computing sum(i[n-j]*w[j] for each j from 0 to size(w)). 5. By acting as if we're rotating the sine wave by one sample each time we get a new input sample, we can compute that by simply having a running sum. We add the value of the last sample * the next sample in the sine wave, then subtract whatever value we added x iterations ago where x is size(sample). That's effectively the same as doing the whole sum given in #4 but rotating the sine wave by one each time. 6. Generate a bunch of sine waves at the initialization of the program, so that you have one for each frequency you want to compute for that's the right number of samples per degree of phase. 7. For each new incoming audio sample, perform the operation in #5 once for each stored sine described in #6. I still don't remember why or how I was subtracting partial samples. in http://nbviewer.jupyter.org/gist/rjw57/1fde826a1d77806b7f64bdd19a058586 (saved in d:\soundshop as jupyter notebook viewer) he detects frequencies (or sine waves anyway) by correlating a sound with the given sine waves