Autocorrelation functions, was Re: [PD-dev] using SIMD instructions in externals

[Mathieu Bouchard]

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