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

[Mathieu Bouchard]

On Thu, 19 Jan 2006, Mathieu Bouchard wrote:

> The radix-2 optimisations of FFT are generalizable to any radix. When it
> is said that FFT runs in O(n log n) time, what's really meant by log n is
> more like, the sum of all prime factors of n.

Actually, that's not exactly true... there's a newer FFT algorithm that
can do O(n log n) for prime sizes as well, but it's a slower O(n log n)
than the one that involves small prime factors. libfftw supports both 
algorithms. (Pd's builtin FFT supports only power-of-two AFAIK).

 _ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - tél:+1.514.383.3801 - http://artengine.ca/matju
| Freelance Digital Arts Engineer, Montréal QC Canada