Path: csiph.com!news.mixmin.net!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.programming Subject: Re: Another little puzzle Date: Sun, 25 Dec 2022 18:35:18 -0800 Organization: A noiseless patient Spider Lines: 41 Message-ID: <86bknqyjrt.fsf@linuxsc.com> References: <86pmcczcak.fsf@linuxsc.com> <87wn6krsc5.fsf@bsb.me.uk> <868riwzxu3.fsf@linuxsc.com> <87y1qwpb5p.fsf@bsb.me.uk> <86mt7byhtp.fsf@linuxsc.com> <87zgbbnopo.fsf@bsb.me.uk> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader01.eternal-september.org; posting-host="b017513bf0c3c2565b748ac271e0e545"; logging-data="3191608"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/JTYhiRNa18VAMEarAv7WdV8Z52nz0XBs=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:1gLwvm2RCg3YZb/a0ZSK8PwN/CY= sha1:Ib+uLzKYQVdUvs7wMkJo4NzyCQk= Xref: csiph.com comp.programming:16159 Ben Bacarisse writes: > 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. Right. > 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. My best so far is only O( n * log n ). Probably that isn't optimal. I don't see how to make it linear though. Do you have any ideas?