Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #16112

Re: Another little puzzle

Show all headers | View raw

On 21/12/2022 21:54, Dmitry A. Kazakov wrote:
> On 2022-12-21 20:55, Mike Terry wrote:
> 
>> The OP was probably deliberately rather vague on this point!  The easiest definition for "average" 
>> literally doesn't make sense in a modulo context:  we can ADD the modular values, but in general 
>> dividing in such a mathematical setting doesn't make much sense, so
>>
>>      Average ([i=1,2,..n] x_i)  =[def]=  Sum ([i=1,2,..n] x_i) /n
>>
>> would be inappropriate due to the /n operation.
> 
> Unless you calculate everything as reals or integers and then take the remainder of 24. Which is 
> kind of most natural definition, at least to me.

That is unambiguous, but to my mind not at all what is wanted - an artificial cut-point has been 
introduced to the continuous mod-24 "loop", converting all the points into non-modular lengths (say 
real numbers), and then those are averaged.  That produces "silly" conclusions as people have 
listed.  I get that people want to read the original question in a literal fashion, because at least 
that would make it clear - but to me that is very much not what was intended or actually said.

(Well, I agree very little was actually /said/ but near the end of the post I give a couple of [what 
I consider] minimal requirements for what a modulo average should achieve, and I bet the OP would 
agree with those!)

> 
>> HOWEVER, there's another characterisation for the average of a set, which looks more promising in 
>> a modular (or other more general) setting:  the average is the value of V which MINIMISES THE 
>> "ERROR" calculated by
>>
>>      error = Sum ([i=1,2,..n] (V - x_i)^2)
>>
>> that is, minimises the sum of squares of differences from V.
> 
> This has exactly same problem as above, because subtraction and multiplication (power of two) have 
> different semantics in modular arithmetic.

Hmm, I don't agree - we've moved from a "calculate this formula for averaging numbers in R" 
perspective, which DOESN'T WORK IN THE MODULO SYSTEM [due to the division] to a "choose V which 
minimises such-and-such error function" which DOES work, provided we have a way of making the error 
function clear.

Note that in the error =  formula above, the "(V - x_i)^2" terms are the squares of the distance 
between V and X_i.  I agree V-x_i would be ambiguous in the modulo system, but that formula is the 
formula for REAL number averages (the "mean" as you point out below).  In the modulo system we need 
a replacement for "distance" that is well defined and appropriate.

So provided we can propose a sensible metric on the modular system, the error function approach 
makes perfect sense.  That's not at all like the "convert modulo number to real number and then take 
arithmetic mean, and then reduce that modulo whatever" definition, which will give different results 
depending on where you make the required "cut" in the modulo loop.

So to be clearer perhaps I should have written:

       error = Sum ([i=1,2,..n] Distance(V,x_i)^2)

ALSO NOTE:  this error calculation ISN'T A MODULO CALCULATION!  It's a calculation in the real 
numbers R.  So Distance is a real number, and squaring is being done in the real numbers, and the 
error function is a function mapping to real numbers that is being minimised as a value in R (by a 
choice of V in the modulo system).  [That all relates to your remark about different semantics in 
modular arithmetic.]

> 
>> [Incidentally, if we minimise the sum of absolute differeces from V, that characterises the mode 
>> (aka "midpoint") of the sample, but I think the median is more what is wanted here...]
> 
> Actually it is the same beast. Median is the least C-norm defined as |x-y|.
> 
> Mean is the least Euclidean norm (squares), the thing you proposed.
> 
> Mean and average are same for real numbers.

Yeah, I agree - Thanks, I'd totally muddled the definitions for those terms!!  Well, I'll say it's 
been a while :)  I should have said "mean".  A quick check shows "mode" is actually "the most common 
value" which is not of much interest here.

> 
> You are right that median (and C-norm) can be unambiguously defined in modular numbers. But nobody 
> would ever qualify this as a puzzle! (:-))
> 
> [...]
> 
>> Now, as to how to CALCULATE the V above???
> 
> As I said, in real numbers V is the mean, i.e.
> 
>     V = Sum (Xi) =def= mean({Xi | i=1..n})
>        i=1..n

But that doesn't work sensibly for a modulo system where arithmetic wraps.  That's the whole point 
of this thread, it seems to me.

Hmmm, ok clearly for a modulo system, if we translate all the x_i by a fixed amount, THE "AVERAGE" 
SHOULD ALSO TRANSLATE BY THE SAME FIXED AMOUNT.  Otherwise it is simply not a sensible definition of 
average with that modulo system.  Your definition does not have the translation property while my 
one does - that's why I propose it for this problem.

I'd agree that there's plenty of room for discussing what is the right "distance" function or 
precisely how that feeds into the "error" function (squares vs. abs values or whatever).  But also I 
think my suggestion for those is good enough...

> 
> Any numeric method is in the end mapping Xi to some normal number, calculating a classic mean, 
> mapping back. The problem is with the forward mapping being ambiguous. One method to disambiguate is 
> staying within the same day. Another could be taking a median and considering 12 hours before and 12 
> hours after it. And there are many more.

Maybe so - I'd just say here that you are discussing an /algorithm/ to compute a result, rather than 
the definition of what is to be considered the correct answer, which was the focus in my post.  I 
agree any algorithm could well incorporate calculating the mean of certain real numbers, but 
/correctness/ is judged by whether the algorithm produces the V with minimum error function. 
[Otherwise people just make an arbitrary coding decision, and say by definition their code is 
correct because it correctly codes what they want it to :) ]

Going a bit further than my last post, I'd say that the average as I've defined it would probably 
turn out to be the real-number average, if only we could make the cut in the modulo loop 12 hours 
away from the point V.  Of course the point V is the value to be determined, which isn't known up 
front, so /defining/ V like this would be circular!  It does seem that the effect of moving V in all 
the calculations would be more easily evaluated, if the times x_i were SORTED, so we could quickly 
find how many x_i are in different intervals.  Just thinking...

> 
> P.S. There are differences between the average and mean. OP referred the average, which may mean 
> something completely counterintuitive (no pun intended (:-))
> 

I think the OP didn't think too deeply about the mathematics - but I think any solution without 
these two properties would be an automatic fail for OP:

-   if all x_i are within 5 minutes of each other [ALLOWING FOR WRAPPING
     AROUND THE END OF THE MODULO LOOP] then the "average" will be within
     those same 5 minutes.   NOT e.g. 12 hours or 4 hours or whatever away.

-   if all x_i are translated by a fixed offset like 1 hour, the average
     will translate by the same offset, i.e. it maintains the same "modulo"
     relation with the translated x_i.

Regards,
Mike.

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

Thread

Re: Another little puzzle Richard Heathfield <rjh@cpax.org.uk> - 2022-12-21 13:09 +0000
  Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-21 17:05 +0000
    Re: Another little puzzle Richard Heathfield <rjh@cpax.org.uk> - 2022-12-21 17:21 +0000
    Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-12-21 18:55 +0100
      Re: Another little puzzle Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-12-21 19:55 +0000
        Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-12-21 22:54 +0100
          Re: Another little puzzle Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-12-22 00:01 +0000
            Re: Another little puzzle Julio Di Egidio <julio@diegidio.name> - 2022-12-21 16:05 -0800
              Re: Another little puzzle David Brown <david.brown@hesbynett.no> - 2022-12-22 16:50 +0100
                Re: Another little puzzle Julio Di Egidio <julio@diegidio.name> - 2022-12-22 08:30 -0800
                Re: Another little puzzle David Brown <david.brown@hesbynett.no> - 2022-12-22 22:06 +0100
                Re: Another little puzzle Richard Heathfield <rjh@cpax.org.uk> - 2022-12-22 21:30 +0000
                Re: Another little puzzle David Brown <david.brown@hesbynett.no> - 2022-12-23 13:46 +0100
                Re: Another little puzzle Y A <angel0000000001000000000000@mail.ee> - 2023-01-09 21:26 -0800
                Re: Another little puzzle Julio Di Egidio <julio@diegidio.name> - 2022-12-22 14:15 -0800
                Re: Another little puzzle David Brown <david.brown@hesbynett.no> - 2022-12-23 13:47 +0100
                Re: Another little puzzle Julio Di Egidio <julio@diegidio.name> - 2022-12-23 08:33 -0800
                Re: Another little puzzle Julio Di Egidio <julio@diegidio.name> - 2022-12-25 15:52 -0800
                Re: Another little puzzle Julio Di Egidio <julio@diegidio.name> - 2022-12-26 06:32 -0800
                Re: Another little puzzle Julio Di Egidio <julio@diegidio.name> - 2022-12-26 06:34 -0800
              Re: Another little puzzle Julio Di Egidio <julio@diegidio.name> - 2022-12-23 08:35 -0800
            Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-12-22 09:10 +0100
          Re: Another little puzzle Ǝ <angel00000100000@mail.ee> - 2022-12-30 18:18 -0800
        Re: Another little puzzle Julio Di Egidio <julio@diegidio.name> - 2022-12-21 14:47 -0800
          Re: Another little puzzle Julio Di Egidio <julio@diegidio.name> - 2022-12-23 08:35 -0800
          Re: Another little puzzle Julio Di Egidio <julio@diegidio.name> - 2022-12-25 15:52 -0800
            Re: Another little puzzle Julio Di Egidio <julio@diegidio.name> - 2022-12-26 06:32 -0800
          Re: Another little puzzle Julio Di Egidio <julio@diegidio.name> - 2022-12-26 06:33 -0800
          Re: Another little puzzle Y A <angel0000000001000000000000@mail.ee> - 2023-01-09 21:26 -0800

csiph-web