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

[Mathieu Bouchard]

On Fri, 20 Jan 2006, Ed Kelly wrote:

> > If I guess correctly it's supposed to take the average distance
> > between each possible pair of two distinct points? Then I have a O(n
> > log n) algorithm for that, which has nothing to do with FFT.

> Yes, that's the idea. I would be very grateful to have a look at that.

Just sort your floats. Then every number will be greater than each of the
values that precede it. Then you need not fabs(). Then because fabs() is
gone, summing in[i]-in[k] for 0<=i<l and 0<=k<i is optimisable from O(n*n) 
to O(n):

float pred=0.0;
float total=0.0;
for (int i=1; i<l; i++) {
  total += pred - in[i]*i;
  pred += in[i];
}

Is that right?

However I don't know how that interacts with your "start" and "end" bounds
that you use for variable j in your code...

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