TAking the minimum of three values

[Alf P. Steinbach]

Re: TAking the minimum of three values

On Wed, 10 Sep 2003 04:34:29 +1000, Sona <sona.gardner@n ospam.com> wrote:
[color=blue]
>I need to find a minimum of three float values.. what would be the most
>efficient way of doing this? Can someone please share a #define macro or
>something with me for doing this? Thanks[/color]

First off, DO NOT, I repeat for your convenience, DO NOT, crosspost
general questions to both [comp.lang.c] and [comp.lang.c++].

Those are different languages.

Now _the_ (one and only) answer to your question is simple: the _most
efficient_ way of finding the minimum of three 'double' values is to
leverage contextual information and language- and implementation- quirks.
That depends very much on the problem to be solved, your current code,
the language you're using, and even the compiler. Post this information,
except the compiler, and you may receive more specific answers.

[Carsten Hansen]

Re: TAking the minimum of three values


"Jirka Klaue" <jklaue@ee.tu-berlin.de> wrote in message
news:bjm108$cvg $1@mamenchi.zrz .TU-Berlin.DE...[color=blue]
> Carsten Hansen wrote:[color=green]
> >"Jirka Klaue" wrote:[color=darkred]
> >>Carsten Hansen wrote:
> >>>"Sona" wrote:
> >>>
> >>>>I need to find a minimum of three float values.. what would be the[/color][/color][/color]
most[color=blue][color=green][color=darkred]
> >>>>efficient way of doing this? Can someone please share a #define macro[/color][/color][/color]
or[color=blue][color=green][color=darkred]
> >>>>something with me for doing this? Thanks
> >>>
> >>>You want a macro. Here you go:
> >>>#define min3(x, y, z) \
> >>>((x) < (y)) ? (((y) < (z)) ? (y) : (((x) < (z)) ? (z) : (x))) : (((x) <[/color]
> >
> > (z))
> >[color=darkred]
> >>>? (x) : (((y) < (z)) ? (z) : (y)))
> >>>
> >>>You can't beat that for efficiency.
> >>
> >>It is not even correct.[/color]
> >
> > Give an example where it fails.[/color]
>
> #include <stdio.h>
>
> #define MIN3(x, y, z) \
> ((x) < (y)) ? (((y) < (z)) ? (y) : (((x) < (z)) ? (z) : (x))) : (((x) <[/color]
(z)) ? (x) : (((y) < (z)) ? (z) : (y)))[color=blue]
>
> int main(void)
> {
> float a = 1.6, b = 1.7, c = 1.8;
> printf("%f\n", MIN3(a, b, c));
>
> a = 1.9, b = 1.7, c = 1.8;
> printf("%f\n", MIN3(a, b, c));
>
> a = 1.6, b = 1.7, c = 1.5;
> printf("%f\n", MIN3(a, b, c));
>
> return 0;
> }
>
> 1.700000
> 1.800000
> 1.600000
>
> Now, give an example where it works.
> And even when you fix it, it probably is not the most efficient method.
>
> Jirka
>[/color]

Sorry. It is me being stupid. The macro I posted returns the median of the
three, not the minimum.
This one is much simpler.

#define min3(x, y, z) \
(((x) < (y)) ? (((z) < (x)) ? (z) : (x)) : (((z) < (y)) ? (z) : (y)))

Carsten Hansen

[Jirka Klaue]

Re: TAking the minimum of three values

Carsten Hansen wrote:
....[color=blue][color=green][color=darkred]
>>>>>#define min3(x, y, z) \
>>>>>((x) < (y)) ? (((y) < (z)) ? (y) : (((x) < (z)) ? (z) : (x))) : (((x) < (z)) ? (x) : (((y) < (z)) ? (z) : (y)))[/color][/color][/color]
....[color=blue]
> Sorry. It is me being stupid. The macro I posted returns the median of the
> three, not the minimum.
> This one is much simpler.
>
> #define min3(x, y, z) \
> (((x) < (y)) ? (((z) < (x)) ? (z) : (x)) : (((z) < (y)) ? (z) : (y)))[/color]

I see. Seems to be pretty efficient now, too. :-)

Jirka

[Peter Nilsson]

Re: TAking the minimum of three values

Martin Ambuhl <mambuhl@earthl ink.net> wrote in message news:<Sju7b.237 0$TC1.423@newsr ead2.news.atl.e arthlink.net>.. .[color=blue]
> Peter Nilsson wrote:[color=green]
> > "Howard" <alicebt@hotmai l.com> wrote in message
> > news:<bjl7cq$rl f@dispatch.conc entric.net>...[color=darkred]
> > >x = min( a, min( b, c ) );[/color]
> >
> >
> > Given a typical definition of min(), that will not produce an efficient
> > result.
> >
> > #define min3(a,b,c) \
> > ( (a) < (b) ? min(a,c) : min(b,c) )[/color]
>
> Have you counted the number of evaluations of a or b this involves? There
> is a good reason for preferring functions over defines.[/color]

Inline functions yes; but functions, in C, not always.

My problem was not realising that the OP cross posted. My Bad.

I was reading it in clc and concentrated on "Can someone please share
a #define macro or something..." in the OP's post.

[I really don't know why people using C++ also ask C groups for
solutions when the answers are highly likely to involve different
paradigms and/or language constructs.]

Anyway, my mistake...

FWIW, C99 has its own version of inline functions too.

--
Peter

[Ron Natalie]

Re: TAking the minimum of three values


"Peter Nilsson" <airia@acay.com .au> wrote in message news:63f490f7.0 309091622.3c76c f2f@posting.goo gle.com...
[color=blue][color=green]
> > x = min( a, min( b, c ) );[/color]
>
> Given a typical definition of min(), that will not produce an efficient result.
>
> #define min3(a,b,c) \
> ( (a) < (b) ? min(a,c) : min(b,c) )[/color]

The typical min is inlined to something like
a < b ? a : b

There's always two comparisons. Tests show no speed difference
between the two on my machine.

[Arthur J. O'Dwyer]

Re: TAking the minimum of three values


On Wed, 10 Sep 2003, Ron Natalie wrote:[color=blue]
>
> "Peter Nilsson" <airia@acay.com .au> wrote...[color=green]
> >[color=darkred]
> > > x = min( a, min( b, c ) );[/color]
> >
> > Given a typical definition of min(), that will not produce an
> > efficient result.
> >
> > #define min3(a,b,c) \
> > ( (a) < (b) ? min(a,c) : min(b,c) )[/color]
>
> The typical min is inlined to something like
> a < b ? a : b
>
> There's always two comparisons. Tests show no speed difference
> between the two on my machine.[/color]

Are you using functions, or macros? I'm sure that Peter
was referring to the use of macros, in C -- *not* C++, for
the benefit of those reading in c.l.c++.

So we have, without the usual parentheses since they'd just
clutter the example:

#define min(a,b) ((a < b)? a: b)

#define min3_inefficien t(a,b,c) min(a, min(b, c))

#define min3_better(a,b ,c) (a < b)? min(a, c): min(b, c)


min3_inefficien t(X, Y, Z) becomes

min(X, ((Y < Z)? Y: Z))

((X < ((Y < Z)? Y: Z))? X: ((Y < Z)? Y: Z)))


min3_better(X, Y, Z) becomes

((X < Y)? ((X < Z)? X: Z): (Y < Z)? Y: Z)


In this case, even though both expansions contain the same
number of < and ? characters, the "inefficien t" version has
poorer control flow -- three conditionals are evaluated
fully 2/3 of the time, whereas with the "better" version
only two conditionals are ever executed.

<C++ only>
With C++ template functions, of course, it doesn't matter
so much. But if you're interested in efficiency, why are
you using functions? ;-)
</C++>

-Arthur

[Ben Pfaff]

Re: TAking the minimum of three values

Irrwahn Grausewitz <irrwahn@freene t.de> writes:
[color=blue]
> "Jeff" <nothing@notexi st.com> wrote:[color=green]
> >Please do not post off-topic things here. It waste the bandwidth and time.[/color]
>
> Erm, (almost) the whole thread is cross-posted between c.l.c and c.l.c++[/color]

So any proposed solutions should work in both C and C++.
--
"...deficie nt support can be a virtue.
It keeps the amateurs off."
--Bjarne Stroustrup

[Irrwahn Grausewitz]

Re: TAking the minimum of three values

Ben Pfaff <blp@cs.stanfor d.edu> wrote:
[color=blue]
>Irrwahn Grausewitz <irrwahn@freene t.de> writes:
>[color=green]
>> "Jeff" <nothing@notexi st.com> wrote:[color=darkred]
>> >Please do not post off-topic things here. It waste the bandwidth and time.[/color]
>>
>> Erm, (almost) the whole thread is cross-posted between c.l.c and c.l.c++[/color]
>
>So any proposed solutions should work in both C and C++.[/color]

And one who is cross-posting complaints about off-topicality of
cross-posted replies to cross-posted questions should make clear
what the word "here" is referring to in this context.

--
What does this red button do?

[Ron Natalie]

Re: TAking the minimum of three values


"Arthur J. O'Dwyer" <ajo@andrew.cmu .edu> wrote in message news:Pine.LNX.4 .55L-[color=blue]
> Are you using functions, or macros? I'm sure that Peter
> was referring to the use of macros, in C -- *not* C++, for
> the benefit of those reading in c.l.c++.[/color]

I used inline functions. It's even worse if he used macros as
the expressions passed are possibly evaluated more than once.
[color=blue]
> In this case, even though both expansions contain the same
> number of < and ? characters, the "inefficien t" version has
> poorer control flow -- three conditionals are evaluated
> fully 2/3 of the time, whereas with the "better" version
> only two conditionals are ever executed.[/color]

It's beyond me what you mean by that. Both times execute
the comparison twice, as a result the select. You can make
up your own idea of the cost of the flow between the two, but
as I said, it;s negligable. Both functions on the Sun compiler
take the same amount of time.
[color=blue]
> <C++ only>
> With C++ template functions, of course, it doesn't matter
> so much. But if you're interested in efficiency, why are
> you using functions? ;-)
> </C++>[/color]

Templates have no bearing on this situation at all. You could
as easily code this as functions taking doubles without templates
and the answer would be the same.

[Glen Herrmannsfeldt]

Re: TAking the minimum of three values


"Arthur J. O'Dwyer" <ajo@andrew.cmu .edu> wrote in message
news:Pine.LNX.4 .55L-032.03091012130 40.11337@unix49 .andrew.cmu.edu ...

(snip)
[color=blue]
> Are you using functions, or macros? I'm sure that Peter
> was referring to the use of macros, in C -- *not* C++, for
> the benefit of those reading in c.l.c++.
>
> So we have, without the usual parentheses since they'd just
> clutter the example:
>
> #define min(a,b) ((a < b)? a: b)
>
> #define min3_inefficien t(a,b,c) min(a, min(b, c))
>
> #define min3_better(a,b ,c) (a < b)? min(a, c): min(b, c)
>
>
> min3_inefficien t(X, Y, Z) becomes
>
> min(X, ((Y < Z)? Y: Z))
>
> ((X < ((Y < Z)? Y: Z))? X: ((Y < Z)? Y: Z)))
>
>
> min3_better(X, Y, Z) becomes
>
> ((X < Y)? ((X < Z)? X: Z): (Y < Z)? Y: Z)
>
>
> In this case, even though both expansions contain the same
> number of < and ? characters, the "inefficien t" version has
> poorer control flow -- three conditionals are evaluated
> fully 2/3 of the time, whereas with the "better" version
> only two conditionals are ever executed.[/color]

Good compilers do common subexpression elimination, and hopefully will
notice that (Y<Z) occurs twice.

In any hand optimization problem, the question is always what will the
compiler find at want won't it find.

-- glen

[Arthur J. O'Dwyer]

Re: TAking the minimum of three values


On Wed, 10 Sep 2003, Ron Natalie wrote:[color=blue]
>
> "Arthur J. O'Dwyer" <ajo@andrew.cmu .edu> wrote...[color=green]
> > Are you using functions, or macros? I'm sure that Peter
> > was referring to the use of macros, in C -- *not* C++, for
> > the benefit of those reading in c.l.c++.[/color]
>
> I used inline functions. It's even worse if he used macros as
> the expressions passed are possibly evaluated more than once.[/color]

True; however, he did mention the *usual* definition of 'min',
which IME is more often than not as a macro.
[color=blue][color=green]
> > In this case, even though both expansions contain the same
> > number of < and ? characters, the "inefficien t" version has
> > poorer control flow -- three conditionals are evaluated
> > fully 2/3 of the time, whereas with the "better" version
> > only two conditionals are ever executed.[/color]
>
> It's beyond me what you mean by that. Both times execute
> the comparison twice, as a result the select.[/color]

Brain fart? :-)
Unsnipped from my previous post:

min3_inefficien t(X, Y, Z) becomes
min(X, ((Y < Z)? Y: Z))
((X < ((Y < Z)? Y: Z))? X: ((Y < Z)? Y: Z)))

min3_better(X, Y, Z) becomes
((X < Y)? ((X < Z)? X: Z): (Y < Z)? Y: Z)


Suppose X is the least of the three... then
min3_inefficien t compares Y to Z
then compares X to min(Y,Z)
min3_better compares X to Y
then compares X to Z

Suppose Y is the least of the three... then
min3_inefficien t compares Y to Z
then compares X to Y
then compares Y to Z
min3_better compares X to Y
then compares Y to Z

Suppose Z is the least of the three... then
min3_inefficien t compares Y to Z
then compares X to Z
then compares Y to Z
min3_better compares X to Y
then compares min(X,Y) to Z


See? min3_better makes exactly 2 comparisons in each case,
while min3_inefficien t makes 3 comparisons fully 2/3 of the
time, as I said. Thus min3_inefficien t *is* less efficient,
because it computes useless comparisons.

[color=blue]
> You can make
> up your own idea of the cost of the flow between the two, but
> as I said, it;s negligable. Both functions on the Sun compiler
> take the same amount of time.[/color]

Try running them more than once.

(But before doing that, take a look at the generated machine
code. I would not be surprised if the GCC folks have optimized
this particular computation, so the Sun folks might have too.)

[color=blue][color=green]
> > <C++ only>
> > With C++ template functions, of course, it doesn't matter
> > so much. But if you're interested in efficiency, why are
> > you using functions? ;-)
> > </C++>[/color]
>
> Templates have no bearing on this situation at all. You could
> as easily code this as functions taking doubles without templates
> and the answer would be the same.[/color]

....except in the case where you wanted to compare pointers.
Or C++ std::strings. Or 'long longs'. Or practically anything
that wasn't a double.

(Which, incidentally, is why the most common implementation of
'min' is as a macro -- because C macros can do things that C
functions can't.)

-Arthur

[Ron Natalie]

Re: TAking the minimum of three values


"Arthur J. O'Dwyer" <ajo@andrew.cmu .edu> wrote in message news:Pine.LNX.4 .55L-032.03091018095 40.8309@unix45. andrew.cmu.edu. ..[color=blue]
>
> On Wed, 10 Sep 2003, Ron Natalie wrote:[color=green]
> >
> > "Arthur J. O'Dwyer" <ajo@andrew.cmu .edu> wrote...[color=darkred]
> > > Are you using functions, or macros? I'm sure that Peter
> > > was referring to the use of macros, in C -- *not* C++, for
> > > the benefit of those reading in c.l.c++.[/color]
> >
> > I used inline functions. It's even worse if he used macros as
> > the expressions passed are possibly evaluated more than once.[/color]
>
> True; however, he did mention the *usual* definition of 'min',
> which IME is more often than not as a macro.[/color]

Maybe it is in C, but it certainly IS NOT in C++.

[color=blue]
>
> See? min3_better makes exactly 2 comparisons in each case,
> while min3_inefficien t makes 3 comparisons fully 2/3 of the
> time, as I said. Thus min3_inefficien t *is* less efficient,
> because it computes useless comparisons.[/color]

It is for the ugly macros, as I was saying, for inline functions it does
not need to generate a bogus third test.

[pete]

Re: TAking the minimum of three values

Ron Natalie wrote:[color=blue]
>
> "Arthur J. O'Dwyer" <ajo@andrew.cmu .edu> wrote in message news:Pine.LNX.4 .55L-032.03091018095 40.8309@unix45. andrew.cmu.edu. ..[color=green]
> >
> > On Wed, 10 Sep 2003, Ron Natalie wrote:[color=darkred]
> > >
> > > "Arthur J. O'Dwyer" <ajo@andrew.cmu .edu> wrote...
> > > > Are you using functions, or macros? I'm sure that Peter
> > > > was referring to the use of macros, in C -- *not* C++, for
> > > > the benefit of those reading in c.l.c++.
> > >
> > > I used inline functions. It's even worse if he used macros as
> > > the expressions passed are possibly evaluated more than once.[/color]
> >
> > True; however, he did mention the *usual* definition of 'min',
> > which IME is more often than not as a macro.[/color]
>
> Maybe it is in C, but it certainly IS NOT in C++.[/color]

The following macro is a paradigm in C:

#define max(a, b) ((a) > (b) ? (a) : (b))

--
pete

[pete]

Re: TAking the minimum of three values

Arthur J. O'Dwyer wrote:[color=blue]
>
> On Wed, 10 Sep 2003, Ron Natalie wrote:[color=green]
> >
> > "Peter Nilsson" <airia@acay.com .au> wrote...[color=darkred]
> > >
> > > > x = min( a, min( b, c ) );
> > >
> > > Given a typical definition of min(), that will not produce an
> > > efficient result.
> > >
> > > #define min3(a,b,c) \
> > > ( (a) < (b) ? min(a,c) : min(b,c) )[/color]
> >
> > The typical min is inlined to something like
> > a < b ? a : b
> >
> > There's always two comparisons. Tests show no speed difference
> > between the two on my machine.[/color]
>
> Are you using functions, or macros? I'm sure that Peter
> was referring to the use of macros, in C -- *not* C++, for
> the benefit of those reading in c.l.c++.
>
> So we have, without the usual parentheses since they'd just
> clutter the example:
>
> #define min(a,b) ((a < b)? a: b)[/color]

It's illogical to remove required parentheses
and then insert extra one's that you like.
Minimally but correctly parenthesized:

#define min(a, b) ((b) > (a) ? a : (b))

--
pete