From: ben.usenet@bsb.me.uk   
      
   Tim Rentsch  writes:   
      
   > Ben Bacarisse  writes:   
      
   >> I'm sorry to be obtuse, but what is the "conventional average"?  The   
   >> name makes it sound trivial, but the quadratic time makes me certain   
   >> that is isn't.   
   >   
   > Sorry, I meant to refer to your formulation of average   
   >   
   >     A that minimizes { Sum_{i=1,n} difference(A, t(i))^2 }   
   >   
   > where 'difference' means the shorter arc length.  This formula   
   > matches the result for 'mean' on real numbers.   
   >   
   >> My "conventional average" algorithm (which is not well thought out) was   
   >> to (a) rotate the data set to avoid the 23/0 boundary (not always   
   >> possible), (b) take the arithmetic mean, and then (c) rotate the result   
   >> back.  E.g. [23,0,1] -> [0,1,2] by adding one, and the average is   
   >> mean[0,1,2] - 1 = 0.   
   >   
   > Yes, if you know where to split the cycle then the answer can be   
   > found in O(n) time.  But how can we figure out where to split the   
   > cycle?   
      
   Well I handily stopped considering this at the stage where I assumed   
   there must be a simple way to spot the optimal rotation, so I never   
   thought it might have to be quadratic.  Presumably your algorithm tries   
   all the offsets and minimises the result.   
      
   Looking at it a bit more I can't see a better way (but that might be the   
   Ratafia de Champagne).  It feels as if there /should/ be one.  In fact   
   it feels as if it should be linear.   
      
   --   
   Ben.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)