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