Re: [boost] Interest in algorithm for arithmetic mean of integers

Subject: Re: [boost] Interest in algorithm for arithmetic mean of integers
From: Matt Calabrese (rivorus_at_[hidden])
Date: 2015-09-06 14:21:31

On Sun, Sep 6, 2015 at 4:46 AM, Bjorn Reese <breese_at_[hidden]>
wrote:
>
> I still do not understand how you calculate these state values

If it's not already clear enough based on the descriptions, you'll have to
wait until I release the code.

 On Sun, Sep 6, 2015 at 4:46 AM, Bjorn Reese <breese_at_[hidden]>
 wrote:

> looking at them it becomes clear that the average M[i] at iteration i
> is given by (assuming W[i] is the first entry in the state tuple at
> iteration i)
>
  M[i] = W[i] + (N[i] / D[i])
>

Logically that is the value that is represented, yes. The mixed number
state is { W, N, D } where W is the whole number part, and N/D is the
fractional part, where N an integer is in the range [0, D)

 On Sun, Sep 6, 2015 at 4:46 AM, Bjorn Reese <breese_at_[hidden]>
 wrote:
>
> I am wondering if you can also calculate the running sum from the
> state variables by?
>
>   S[i] = W[i] * D[i] + N[i]

If this were just pure mathematics or if we were talking about infinite
precision types, then yes, you could do that, but in practice we are
dealing with built-in integer types or other user-define integer types that
can only represent one of a certain closed set of integer values. Even with
a range that only has two values in it you can potentially overflow when
calculating the sum, which is why the mean algorithm that is that is
presented never directly represents the sum. In this way, the algorithm is
able to produce an exact mean for a range of any size, where each element
of the range can hold any integer value that the value type of the range
can hold. There are no additional preconditions for the function and it
should always produce a valid result.

 On Sun, Sep 6, 2015 at 4:46 AM, Bjorn Reese <breese_at_[hidden]>
 wrote:

> If they are to be added to Boost.Algorithm, then you need to get the
> interest of the maintainer. He will decide what level of review is
> needed, if any.

Yeah, I CC'd Marshall and Eric in earlier replies, so I imagine they will
eventually respond.

-- 
-Matt Calabrese