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 17649 days, 5 hours, 45 minutes ago.