On Tue, 17 Jan 2006, Ed Kelly wrote:
Thanks again. The reason I am looking at this is because I'm doing a lot of work with autocorrelation functions and would really like to find ways of speeding them up. I'm using nested for loops, but maybe some form of matrix math is more appropriate. I've never studied maths in so much depth, but if anyone can point me to a way of making fast realtime versions of ACFs I would be extremely grateful! (and we will have a new external).
You need to use some kind of FFT in order to benefit from the fantastic speed increase possible with the Convolution Theorem.
the trick is: fourier(x convol y) = fourier(x) * fourier(y)
and then this formula wouldn't get things any faster if it weren't for the FFT. a Fourier Transform itself is a kind of convolution so naïvely it takes n*n multiplications but it's very special because it's optimisable and so the Fast (FFT) version takes only n*log2(n) multiplications.
_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801 - http://artengine.ca/matju | Freelance Digital Arts Engineer, Montréal QC Canada