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

Groups > comp.programming > #16074 > unrolled thread

Re: Another little puzzle

Back to article view | Back to comp.programming

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-12-14 14:06 +0100
    Re: Another little puzzle Richard Heathfield <rjh@cpax.org.uk> - 2022-12-14 13:10 +0000
      Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-12-14 14:35 +0100
        Re: Another little puzzle Richard Heathfield <rjh@cpax.org.uk> - 2022-12-14 14:10 +0000
          Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-12-14 15:58 +0100
            Re: Another little puzzle Richard Heathfield <rjh@cpax.org.uk> - 2022-12-14 15:18 +0000
              Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-12-14 16:41 +0100
                Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-12-14 16:43 +0100
                  Re: Another little puzzle Y A <angel00000100000@mail.ee> - 2023-01-09 16:33 -0800
                Re: Another little puzzle Richard Heathfield <rjh@cpax.org.uk> - 2022-12-14 16:13 +0000
          Re: Another little puzzle V <angleeeeeeee@mail.ee> - 2023-05-10 11:16 -0700
      Re: Another little puzzle Ǝ <angel0000000001000000000000@mail.ee> - 2022-12-30 05:59 -0800

#16074 — Re: Another little puzzle

On 2022-12-14 13:24, Stefan Ram wrote:
>    Given n times of the 24-hour day, print their average.
> 
>    For example, the average of "eight o'clock" and
>    "ten o'clock" (n=2) would be "nine o'clock".

You probably missed to require the interesting part: doing all that in 
the modular type (modulo 24) arithmetic:

    20 + 5 = 1 (mod 24)

>    (You can choose any representation, for example "HH:MM"
>    or "seconds since midnight".)

That is not representation. Averaging hours, minutes, seconds are three 
different problems, though the algorithm would be same.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [next] | [standalone]

#16075

On 14/12/2022 1:06 pm, Dmitry A. Kazakov wrote:
> On 2022-12-14 13:24, Stefan Ram wrote:
>>    Given n times of the 24-hour day, print their average.
>>
>>    For example, the average of "eight o'clock" and
>>    "ten o'clock" (n=2) would be "nine o'clock".
> 
> You probably missed to require the interesting part: doing all 
> that in the modular type (modulo 24) arithmetic:
> 
>     20 + 5 = 1 (mod 24)

...which will give you the wrong answer. Chase that goose!

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#16077

On 2022-12-14 14:10, Richard Heathfield wrote:
> On 14/12/2022 1:06 pm, Dmitry A. Kazakov wrote:
>> On 2022-12-14 13:24, Stefan Ram wrote:
>>>    Given n times of the 24-hour day, print their average.
>>>
>>>    For example, the average of "eight o'clock" and
>>>    "ten o'clock" (n=2) would be "nine o'clock".
>>
>> You probably missed to require the interesting part: doing all that in 
>> the modular type (modulo 24) arithmetic:
>>
>>     20 + 5 = 1 (mod 24)
> 
> ...which will give you the wrong answer. Chase that goose!

Right, you must count the wrap-ups. E.g.

for I in Times'Range loop
    New_Sum := Old_Sum + Times (I);
    if Old_Sum > New_Sum then -- Wrapped
       Count := Count + 1;
       if Count = n then -- Each n wrap-ups can be discarded
          Count := 0;
       end if;
    end if;
    Old_Sum := New_Sum;
end loop;

In the end you have to evaluate

    (Old_Sum + Count * 24) / n  (mod 24)

where Count < n is the wrap-ups count.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#16080

On 14/12/2022 1:35 pm, Dmitry A. Kazakov wrote:
> On 2022-12-14 14:10, Richard Heathfield wrote:
>> On 14/12/2022 1:06 pm, Dmitry A. Kazakov wrote:
>>> On 2022-12-14 13:24, Stefan Ram wrote:
>>>>    Given n times of the 24-hour day, print their average.
>>>>
>>>>    For example, the average of "eight o'clock" and
>>>>    "ten o'clock" (n=2) would be "nine o'clock".
>>>
>>> You probably missed to require the interesting part: doing all 
>>> that in the modular type (modulo 24) arithmetic:
>>>
>>>     20 + 5 = 1 (mod 24)
>>
>> ...which will give you the wrong answer. Chase that goose!
> 
> Right, you must count the wrap-ups.

No, you don't. You're given n times of the 24-hour day, so all 
values are already in the hour range [0-24). Convert to seconds 
from midnight, add all values, divide by n to give a number t 
guaranteed (assuming no leap seconds) to be in the range 
[0-86400), and convert to the representation of your choice. (And 
even if there is a leap second, it doesn't matter more than half 
a sixpence.)

e.g.

int h, m, s;

h = t / 3600;
m = (t - h*3600) / 60;
s = (t - h*3600 - m * 60);

So why do you need mod?

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#16081

On 2022-12-14 15:10, Richard Heathfield wrote:
> On 14/12/2022 1:35 pm, Dmitry A. Kazakov wrote:
>> On 2022-12-14 14:10, Richard Heathfield wrote:
>>> On 14/12/2022 1:06 pm, Dmitry A. Kazakov wrote:
>>>> On 2022-12-14 13:24, Stefan Ram wrote:
>>>>>    Given n times of the 24-hour day, print their average.
>>>>>
>>>>>    For example, the average of "eight o'clock" and
>>>>>    "ten o'clock" (n=2) would be "nine o'clock".
>>>>
>>>> You probably missed to require the interesting part: doing all that 
>>>> in the modular type (modulo 24) arithmetic:
>>>>
>>>>     20 + 5 = 1 (mod 24)
>>>
>>> ...which will give you the wrong answer. Chase that goose!
>>
>> Right, you must count the wrap-ups.

[...]

> So why do you need mod?

As I said, the challenge is only interesting in modulo arithmetic (24 or 
24*60 or 24*60*60). E.g. let

    type Hour is mod 24;

Average a series of Hour without conversion to another integer type.

(Otherwise it is trivial: convert to a wider type, average, convert back)

P.S. This problem may actually arise in programming a microcontroller 
when you have some large series and narrow 16-bit types. Close cases are 
computations with color channels and grayscale levels when conversions 
to wider types are too expensive etc.

The general case is some f(X1,X2,..,Xn) such that max{Xi} >= f() >= 
min{Xi}, but intermediates are not. As it is in the case with averaging Xi.

BTW, averaging floats is a nasty problem too. A naive implementation 
quickly loses precision.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#16082

On 14/12/2022 2:58 pm, Dmitry A. Kazakov wrote:
> On 2022-12-14 15:10, Richard Heathfield wrote:
>> On 14/12/2022 1:35 pm, Dmitry A. Kazakov wrote:
>>> On 2022-12-14 14:10, Richard Heathfield wrote:
>>>> On 14/12/2022 1:06 pm, Dmitry A. Kazakov wrote:
>>>>> On 2022-12-14 13:24, Stefan Ram wrote:
>>>>>>    Given n times of the 24-hour day, print their average.
>>>>>>
>>>>>>    For example, the average of "eight o'clock" and
>>>>>>    "ten o'clock" (n=2) would be "nine o'clock".
>>>>>
>>>>> You probably missed to require the interesting part: doing 
>>>>> all that in the modular type (modulo 24) arithmetic:
>>>>>
>>>>>     20 + 5 = 1 (mod 24)
>>>>
>>>> ...which will give you the wrong answer. Chase that goose!
>>>
>>> Right, you must count the wrap-ups.
> 
> [...]
> 
>> So why do you need mod?
> 
> As I said, the challenge is only interesting in modulo arithmetic

So the challenge is only interesting if you add something you 
don't need. Let's throw in some elephants. Does that make it more 
interesting?

> BTW, averaging floats is a nasty problem too. A naive 
> implementation quickly loses precision.

We're dealing with 'o'clock' and "HH:MM", and nowadays we have 
64-bit integer types and there are even 128-bit integers mooching 
around looking for a reason to exist. You'd have to average a 
hell of a lot of times even to /need/ floats, let alone lose 
significant precision.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#16083

On 2022-12-14 16:18, Richard Heathfield wrote:

>> BTW, averaging floats is a nasty problem too. A naive implementation 
>> quickly loses precision.
> 
> We're dealing with 'o'clock' and "HH:MM", and nowadays we have 64-bit 
> integer types and there are even 128-bit integers mooching around 
> looking for a reason to exist. You'd have to average a hell of a lot of 
> times even to /need/ floats, let alone lose significant precision.

I never suggested float for averaging time stamps, I pointed out that 
averaging is not a simple problem. E.g. try this one:

    function Average (X : Float; N : Positive) return Float is
       Sum : Float := 0.0;
    begin
       for Index in 1..N loop
          Sum := Sum + X;
       end loop;
       return Sum / Float (N);
    end Average;

The function does naive averaging. For simplicity it just sums up the 
same number X N times and divides by N.

    Average (1.0, 17_000_000)  = 0.986895
    Average (1.0, 100_000_000) = 0.167772
    Average (1.0, 200_000_000) = 0.838861

The issue is catastrophic precision loss of addition Sum + X when Sum >> X.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#16084

On 2022-12-14 16:41, Dmitry A. Kazakov wrote:
> On 2022-12-14 16:18, Richard Heathfield wrote:
> 
>>> BTW, averaging floats is a nasty problem too. A naive implementation 
>>> quickly loses precision.
>>
>> We're dealing with 'o'clock' and "HH:MM", and nowadays we have 64-bit 
>> integer types and there are even 128-bit integers mooching around 
>> looking for a reason to exist. You'd have to average a hell of a lot 
>> of times even to /need/ floats, let alone lose significant precision.
> 
> I never suggested float for averaging time stamps, I pointed out that 
> averaging is not a simple problem. E.g. try this one:
> 
>     function Average (X : Float; N : Positive) return Float is
>        Sum : Float := 0.0;
>     begin
>        for Index in 1..N loop
>           Sum := Sum + X;
>        end loop;
>        return Sum / Float (N);
>     end Average;
> 
> The function does naive averaging. For simplicity it just sums up the 
> same number X N times and divides by N.
> 
>     Average (1.0, 17_000_000)  = 0.986895
>     Average (1.0, 100_000_000) = 0.167772
>     Average (1.0, 200_000_000) = 0.838861
                                    0.0838861

The error is obviously systematic.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#16280

Look this
↓
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀🌞⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀ ⠀ ⠀ ⠀ ⠀ ⠀ ⠀ ⠀ ⠀ 🛩
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀🌧️🌧️🌧️⠀⠀🌧️🌧️⠀⠀⠀⠀⠀⠀🌧️🌧️🌧️⠀⠀🌧️🌧️🌧️🌧️⠀⠀🌧️🌧️⠀⠀⠀🌧️🌧️🌧️⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀🕊️ ⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀🌴⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀🍄 ⠀⠀⠀⠀ 🌼⠀⠀⠀⠀ 🌻
🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫🟫

How do You rate this on 1....10 scale ?


On Wednesday, December 14, 2022 at 5:43:18 PM UTC+2, Dmitry A. Kazakov wrote:
> On 2022-12-14 16:41, Dmitry A. Kazakov wrote: 
> > On 2022-12-14 16:18, Richard Heathfield wrote: 
> > 
> >>> BTW, averaging floats is a nasty problem too. A naive implementation 
> >>> quickly loses precision. 
> >> 
> >> We're dealing with 'o'clock' and "HH:MM", and nowadays we have 64-bit 
> >> integer types and there are even 128-bit integers mooching around 
> >> looking for a reason to exist. You'd have to average a hell of a lot 
> >> of times even to /need/ floats, let alone lose significant precision. 
> > 
> > I never suggested float for averaging time stamps, I pointed out that 
> > averaging is not a simple problem. E.g. try this one: 
> > 
> >    function Average (X : Float; N : Positive) return Float is 
> >       Sum : Float := 0.0; 
> >    begin 
> >       for Index in 1..N loop 
> >          Sum := Sum + X; 
> >       end loop; 
> >       return Sum / Float (N); 
> >    end Average; 
> > 
> > The function does naive averaging. For simplicity it just sums up the 
> > same number X N times and divides by N. 
> > 
> >    Average (1.0, 17_000_000)  = 0.986895 
> >    Average (1.0, 100_000_000) = 0.167772 
> >    Average (1.0, 200_000_000) = 0.838861
> 0.0838861 
> 
> The error is obviously systematic.
> -- 
> Regards, 
> Dmitry A. Kazakov 
> http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#16086

On 14/12/2022 3:41 pm, Dmitry A. Kazakov wrote:
> On 2022-12-14 16:18, Richard Heathfield wrote:
> 
>>> BTW, averaging floats is a nasty problem too. A naive 
>>> implementation quickly loses precision.
>>
>> We're dealing with 'o'clock' and "HH:MM", and nowadays we have 
>> 64-bit integer types and there are even 128-bit integers 
>> mooching around looking for a reason to exist. You'd have to 
>> average a hell of a lot of times even to /need/ floats, let 
>> alone lose significant precision.
> 
> I never suggested float for averaging time stamps,

Yes, you did.

> I pointed out 
> that averaging is not a simple problem.

Yes, it is.

> E.g. try this one:
> 
>     function Average (X : Float; N : Positive) return Float is
>        Sum : Float := 0.0;
>     begin
>        for Index in 1..N loop
>           Sum := Sum + X;
>        end loop;
>        return Sum / Float (N);
>     end Average;
> 
> The function does naive averaging. For simplicity it just sums up 
> the same number X N times and divides by N.

You're not being naïve /enough/. The average of N instances of X 
is X, so just return X.

Yes, if you try hard enough, you can screw anything up. So what?

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#16486

Hey !

↓

☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️
☀️⠀anglezzzzzzzzzzz.000webhostapp.com⠀☀️
☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️

[toc] | [prev] | [next] | [standalone]

#16193

Wahtsup nǝgro ?



🌞


Richard Heathfield kirjutas Kolmapäev, 14. detsember 2022 kl 15:10:58 UTC+2:
> On 14/12/2022 1:06 pm, Dmitry A. Kazakov wrote: 
> > On 2022-12-14 13:24, Stefan Ram wrote: 
> >>    Given n times of the 24-hour day, print their average. 
> >> 
> >>    For example, the average of "eight o'clock" and 
> >>    "ten o'clock" (n=2) would be "nine o'clock". 
> > 
> > You probably missed to require the interesting part: doing all 
> > that in the modular type (modulo 24) arithmetic: 
> > 
> >    20 + 5 = 1 (mod 24)
> ...which will give you the wrong answer. Chase that goose!
> -- 
> Richard Heathfield 
> Email: rjh at cpax dot org dot uk 
> "Usenet is a strange place" - dmr 29 July 1999 
> Sig line 4 vacant - apply within

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web