correlation.frink

View or download correlation.frink in plain text format


/** This library calculates the correlation between items in lists. */

/** This calculates the autocorrelation of a single numeric list, that is, it
    identifies the periods at which sequences appear to repeat.  The result
    is a sorted list containing pairs of [offset, correlation] with the terms
    of strongest correlation being first in the list.

    If you just want a single most likely autcorrelation period, it is found at
       result@0@0
*/

autocorrelation[list] :=
{
   results = new array
   size = length[list]
   average = sum[list] / size

   // Scale the list around its average
   normalizedList = new array[size]
   for i = 0 to size-1
      normalizedList@i = list@i - average
   
   for offset=1 to size-1
   {
      sum = 0
      for j = 0 to size-offset-1
         sum = sum + normalizedList@j * normalizedList@(j+offset)

      results.push[[offset, sum]]
   }

   return sort[results, {|a,b| b@1 <=> a@1 }]
}


/**  Examples:

    Calculate the autocorrelation in a repeating list with sub-patterns.
    This should obtain an offset of 6 being the highest correlation. */

/*
list = [1,2,1,4,1,8,1,2,1,4,1,8,1,2,1,4,1,8]
println[autocorrelation[list]]
println[]

// The previous list with a bit of noise.  Hopefully the period will still be 6
println[autocorrelation[[1,2,1,4,1,8,1,2,3,4,1,8,1,2,1,5,1,8]]]
println[]

// The list made very noisy because each point is perturbed by Gaussian noise
// centered around the true value with standard deviation = 1
// (Note that results will vary between runs.)
// Hopefully the strongest period will still be detected at 6.
b = new array
for a = list
   b.push[randomGaussian[a, 1]]
println["Noisy list is $b"]
println["Results:"]
println[autocorrelation[b]]
println[]

// Find when the digits in a number repeat themselves.  The precision may have
// to be increased for larger denominators, as 1/n may repeat after as many as
// n-1 digits.
setPrecision[500]
b=127
println[autocorrelation[array[chars[toString[1./b]]]]]
println[]

// Calculate the autocorellation of a sinewave.  The period should be close
// to the number divided by in the "step" below.
setPrecision[15]
c = new array
for i = 0 to 10 pi step (2 pi / 17.1)
   c.push[sin[i]]

println[autocorrelation[c]]
*/


View or download correlation.frink in plain text format


This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 17591 days, 17 hours, 46 minutes ago.