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

Groups > comp.lang.c > #19099

Re: template metaprogramming in C?

Show all headers | View raw

On 03/28/2012 03:25 AM, Markus Wichmann wrote:
> On 27.03.2012 21:09, Philipp Klaus Krause wrote:
> 
>> Mean of HUGE_VAL, DBL_EPSILON * 4.0, 0.0 and -HUGE_VAL, assuming
>> HUGE_VAL is not infinity.
>>
> 
> If we sort the above list as:
> 
> -HUGE_VAL, 0.0, DBL_EPSILON * 4., HUGE_VAL
> 
> The sum would be
> 
> s1 = -HUGE_VAL
> s2 = -HUGE_VAL
> s3 = -HUGE_VAL (because DBL_EPSILON * 4 is most certainly shifted out
> completely by that addition)
> s4 = 0.0
> 
> so in the end the sum would be 0. If we order it a bit differently, though:
> 
> -HUGE_VAL, HUGE_VAL, 0.0, DBL_EPSILON * 4
> 
> the sum comes around to DBL_EPSILON * 4 (so the mean would be DBL_EPSILON)
> 
> There doesn't appear to be an always perfect sorting algorithm for this
> problem. At least none I can think of right now. We can't sort by
> descending magnitude, because then the effect of the added carry values
> might not appear.
> 
> Generally, we should try to sort in a way such that the magnitude of the
> list sum is maximized... shouldn't we? Damn, what's the real goal here?

The following is not my idea, but I don't know who the true originator was.

Roundoff error is dominated by the magnitude of the larger item being
added. Therefore, you want to arrange as much cancellation as possible,
to keep the magnitudes small. At each step in the sum, add the item not
previously included which will make the next partial sum have the
smallest magnitude. One way to implement this is to sort the list, and
then set two pointers to point at the smallest positive and negative
values in that list. Add either the positive or negative value,
whichever is opposite to the sign of the current sum, moving the
corresponding pointer away from the other one. When either end of the
list is used up, add in the remaining items from the other end of the
list in order of increasing magnitude.
-- 
James Kuyper

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

template metaprogramming in C? Rui Maciel <rui.maciel@gmail.com> - 2012-03-24 11:57 +0000
  Re: template metaprogramming in C? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-03-24 07:25 -0700
    Re: template metaprogramming in C? Markus Wichmann <nullplan@gmx.net> - 2012-03-26 11:46 +0200
      Re: template metaprogramming in C? Philipp Klaus Krause <pkk@spth.de> - 2012-03-27 21:09 +0200
        Re: template metaprogramming in C? Markus Wichmann <nullplan@gmx.net> - 2012-03-28 09:25 +0200
          Re: template metaprogramming in C? James Kuyper <jameskuyper@verizon.net> - 2012-03-28 06:59 -0400
      Re: template metaprogramming in C? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-03-28 12:13 -0700
      Re: template metaprogramming in C? James Dow Allen <jdallen2000@yahoo.com> - 2012-04-01 02:47 -0700
  Re: template metaprogramming in C? Jens Gustedt <jens.gustedt@loria.fr> - 2012-03-24 18:01 +0100
  Re: template metaprogramming in C? Nobody <nobody@nowhere.com> - 2012-03-24 22:57 +0000
    Re: template metaprogramming in C? William Ahern <william@wilbur.25thandClement.com> - 2012-03-24 18:29 -0700
      Re: template metaprogramming in C? Ian Collins <ian-news@hotmail.com> - 2012-03-25 15:03 +1300
      Re: template metaprogramming in C? nick_keighley_nospam@hotmail.com - 2012-03-25 05:32 -0700
  Re: template metaprogramming in C? BGB <cr88192@hotmail.com> - 2012-03-24 17:02 -0700
  Re: template metaprogramming in C? jacob navia <jacob@spamsink.net> - 2012-03-25 01:21 +0100
    Re: template metaprogramming in C? Philipp Klaus Krause <pkk@spth.de> - 2012-03-27 21:17 +0200
      Re: template metaprogramming in C? jacob navia <jacob@spamsink.net> - 2012-03-28 11:10 +0200
        Re: template metaprogramming in C? Nils M Holm <news2009@t3x.org> - 2012-03-28 10:05 +0000
          Re: template metaprogramming in C? Willem <willem@toad.stack.nl> - 2012-03-28 13:36 +0000
            Re: template metaprogramming in C? Nils M Holm <news2009@t3x.org> - 2012-03-28 14:40 +0000
        Re: template metaprogramming in C? Kaz Kylheku <kaz@kylheku.com> - 2012-03-28 18:32 +0000
          Re: template metaprogramming in C? jacob navia <jacob@spamsink.net> - 2012-03-28 22:27 +0200
            Re: template metaprogramming in C? Kaz Kylheku <kaz@kylheku.com> - 2012-03-28 21:02 +0000
        Re: template metaprogramming in C? Nobody <nobody@nowhere.com> - 2012-03-29 16:30 +0100
          Re: template metaprogramming in C? jacob navia <jacob@spamsink.net> - 2012-03-29 23:39 +0200
            Re: template metaprogramming in C? "BartC" <bc@freeuk.com> - 2012-03-29 23:36 +0100
              Re: template metaprogramming in C? Kaz Kylheku <kaz@kylheku.com> - 2012-03-30 00:55 +0000
            Re: template metaprogramming in C? Kaz Kylheku <kaz@kylheku.com> - 2012-03-30 00:32 +0000
              Re: template metaprogramming in C? "BartC" <bc@freeuk.com> - 2012-03-30 10:52 +0100
                Re: template metaprogramming in C? jacob navia <jacob@spamsink.net> - 2012-04-01 09:36 +0200
            Re: template metaprogramming in C? Ian Collins <ian-news@hotmail.com> - 2012-03-30 16:32 +1300
              Re: template metaprogramming in C? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-03-31 01:52 -0700
    Re: template metaprogramming in C? ImpalerCore <jadill33@gmail.com> - 2012-03-28 08:48 -0700
      Re: template metaprogramming in C? "io_x" <a@b.c.invalid> - 2012-04-05 12:18 +0200
        Re: template metaprogramming in C? "io_x" <a@b.c.invalid> - 2012-04-05 13:08 +0200
          Re: template metaprogramming in C? "io_x" <a@b.c.invalid> - 2012-04-05 13:36 +0200
            Re: template metaprogramming in C? pete <pfiland@mindspring.com> - 2012-04-06 18:43 -0400
              Re: template metaprogramming in C? pete <pfiland@mindspring.com> - 2012-04-06 19:20 -0400
      Re: template metaprogramming in C? "io_x" <a@b.c.invalid> - 2012-04-05 13:08 +0200
  Re: template metaprogramming in C? William Ahern <william@wilbur.25thandClement.com> - 2012-03-24 19:01 -0700
    Re: template metaprogramming in C? William Ahern <william@wilbur.25thandClement.com> - 2012-03-24 19:10 -0700
  Re: template metaprogramming in C? Ian Collins <ian-news@hotmail.com> - 2012-03-25 15:25 +1300
    Re: template metaprogramming in C? Rui Maciel <rui.maciel@gmail.com> - 2012-03-25 15:13 +0100
      Re: template metaprogramming in C? Ian Collins <ian-news@hotmail.com> - 2012-03-26 07:10 +1300
        Re: template metaprogramming in C? Rui Maciel <rui.maciel@gmail.com> - 2012-03-25 20:31 +0100
          Re: template metaprogramming in C? nick_keighley_nospam@hotmail.com - 2012-03-26 00:54 -0700

csiph-web