Re: Another little puzzle

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.programming
Subject	Re: Another little puzzle
Date	2022-12-25 21:44 +0000
Organization	A noiseless patient Spider
Message-ID	<87zgbbnopo.fsf@bsb.me.uk> (permalink)
References	(2 earlier) <86pmcczcak.fsf@linuxsc.com> <87wn6krsc5.fsf@bsb.me.uk> <868riwzxu3.fsf@linuxsc.com> <87y1qwpb5p.fsf@bsb.me.uk> <86mt7byhtp.fsf@linuxsc.com>

Show all headers | View raw

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> 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.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-21 13:17 -0800
  Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-22 04:10 +0000
    Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-24 06:21 -0800
      Re: Another little puzzle Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-12-24 16:53 +0000
        Re: Another little puzzle Richard Heathfield <rjh@cpax.org.uk> - 2022-12-24 17:14 +0000
        Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-24 22:30 +0000
          Re: Another little puzzle Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-12-25 00:02 +0000
            Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 01:30 +0000
            Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 01:55 +0000
        Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 00:37 -0800
      Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 00:41 +0000
        Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 01:05 -0800
          Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 09:30 -0800
          Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 21:44 +0000
            Re: Another little puzzle Richard Damon <Richard@Damon-Family.org> - 2022-12-25 17:59 -0500
              Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 18:39 -0800
              Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-26 03:18 +0000
            Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 18:35 -0800
              Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-26 03:49 +0000

csiph-web