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

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