How to find minimum of two numbers.

[pradt]

This might be a silly question. I'm searching for a trick to
prgramatically find minimum of two positive integers without
using a conditional statement/operator('if', '?', etc).

[Travis Willse]

pradt,

How about the following?

min(a,b)=(1/2)*abs(a+b)-(1/2)*abs(a-b)

Note that from a CS standpoint, this really just buries the conditional
inside the definition of the operator abs (which is predefined in most
languages, anyway).

Cheers,
Travis

pr***@yahoo.com wrote:

This might be a silly question. I'm searching for a trick to
prgramatically find minimum of two positive integers without
using a conditional statement/operator('if', '?', etc).

[Trent Buck]

Up spake pr***@yahoo.com:

This might be a silly question. I'm searching for a trick to
prgramatically find minimum of two positive integers without
using a conditional statement/operator('if', '?', etc).

I'm curious; why can't you use a conditional?

--
-trent
Join the hundreds of people on the Internet!
-- installing OS/2

[David W. Cantrell]

Travis Willse <tw*****@gladstone.uoregon.edu> wrote:

pradt,

How about the following?

min(a,b)=(1/2)*abs(a+b)-(1/2)*abs(a-b)

Note that from a CS standpoint, this really just buries the conditional
inside the definition of the operator abs (which is predefined in most
languages, anyway).
Or better: min(a,b) = (1/2)*(a + b - abs(a-b))

FWIW, an alternative to using abs would be

min(a,b) = (1/2)*(a + b - Sqrt((a-b)^2))

David
pr***@yahoo.com wrote:

This might be a silly question. I'm searching for a trick to
prgramatically find minimum of two positive integers without
using a conditional statement/operator('if', '?', etc).

[Ben Pfaff]

pr***@yahoo.com writes:

This might be a silly question. I'm searching for a trick to
prgramatically find minimum of two positive integers without
using a conditional statement/operator('if', '?', etc).

a * (a < b) + b * (a >= b)
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Richard Bos]

David W. Cantrell <DW********@sigmaxi.org> wrote:

Travis Willse <tw*****@gladstone.uoregon.edu> wrote:

pradt,

How about the following?

min(a,b)=(1/2)*abs(a+b)-(1/2)*abs(a-b)

Note that from a CS standpoint, this really just buries the conditional
inside the definition of the operator abs (which is predefined in most
languages, anyway).

Or better: min(a,b) = (1/2)*(a + b - abs(a-b))

FWIW, an alternative to using abs would be

min(a,b) = (1/2)*(a + b - Sqrt((a-b)^2))

Charming. Of course, this requires the #inclusion of <math.h>, (and the
first one requires <stdlib.h>, but you're more likely to have that
already), are probably massively less efficient than a straight
comparison, and can cause overflow that a simple comparison cannot. Oh,
and it's spelled sqrt(), not Sqrt(), and the ^ operator does not do what
you think it does.
Ben's solution is much better, since it avoids all these problems, but
it's still a decent example of why the cross-post is not one of the most
useful. Recreational maths has a set of standards which differs rather
from those of programming. (AAMOF, I'd say that programming can be
useful in RM, but even then you'd want the programming to be done to
non-recreational standards, lest you do recreational things to your
computer.)

Richard

[Skybuck Flying]

"Travis Willse" <tw*****@gladstone.uoregon.edu> wrote in message
news:H4********************@comcast.com...

pradt,

How about the following?

min(a,b)=(1/2)*abs(a+b)-(1/2)*abs(a-b)

Note that from a CS standpoint, this really just buries the conditional
inside the definition of the operator abs (which is predefined in most
languages, anyway).

How about getting rid of the abs by simply setting the "sign" bit to be
always positive ?

Bye,
Skybuck.

[Skybuck Flying]

"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
news:87************@benpfaff.org...

pr***@yahoo.com writes:

This might be a silly question. I'm searching for a trick to
prgramatically find minimum of two positive integers without
using a conditional statement/operator('if', '?', etc).

a * (a < b) + b * (a >= b)

a < b

Isn't that simply a compare ? In other words an "if" statement at the
assembler level ? ;)

Bye,
Skybuck.

[Fred L. Kleinschmidt]

Travis Willse wrote:

pradt,

How about the following?

min(a,b)=(1/2)*abs(a+b)-(1/2)*abs(a-b)
This always evaluates to zero.

Note that from a CS standpoint, this really just buries the conditional
inside the definition of the operator abs (which is predefined in most
languages, anyway).

Cheers,
Travis

pr***@yahoo.com wrote:

This might be a silly question. I'm searching for a trick to
prgramatically find minimum of two positive integers without
using a conditional statement/operator('if', '?', etc).

--
Fred L. Kleinschmidt
Boeing Associate Technical Fellow
Technical Architect, Common User Interface Services
M/S 2R-94 [phone]

[Lawrence Kirby]

On Fri, 10 Dec 2004 16:09:39 +0100, Skybuck Flying wrote:

"Travis Willse" <tw*****@gladstone.uoregon.edu> wrote in message
news:H4********************@comcast.com...

pradt,

How about the following?

min(a,b)=(1/2)*abs(a+b)-(1/2)*abs(a-b)

Note that from a CS standpoint, this really just buries the conditional
inside the definition of the operator abs (which is predefined in most
languages, anyway).

How about getting rid of the abs by simply setting the "sign" bit to be
always positive ?

That assumes that signed integers are represented in a sign-magnitude
form. That isn't guaranteed by C, indeed it is rare. Try this:

#include <limits.h>
#include <stdio.h>

int main(void)
{
int x = -42;
int maskedx = x & INT_MAX; /* Clear the sign bit */

printf("x=%d maskedx=%d\n", x, maskedx);
return 0;
}

Lawrence

[Lawrence Kirby]

On Fri, 10 Dec 2004 16:12:23 +0100, Skybuck Flying wrote:

"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
news:87************@benpfaff.org...

pr***@yahoo.com writes:

> This might be a silly question. I'm searching for a trick to
> prgramatically find minimum of two positive integers without
> using a conditional statement/operator('if', '?', etc).

a * (a < b) + b * (a >= b)

a < b

Isn't that simply a compare ? In other words an "if" statement at the
assembler level ? ;)

If you are thinking of if (a < b) then the if () and the a < b are
different things. The a < b provides the test, the if () provides the
selection behaviour based on the result. So if () and a<b are not the same
thing at all. Many processors have instructions that can compare values
and produce a numeric result, conditional branching isn't implied even
conceptually. E.g. given

int compare(int a, int b)
{
return a < b;
}

gcc can produce the following code for x86:
compare:
movl 8(%esp), %eax
cmpl %eax, 4(%esp)
setl %al
movzbl %al, %eax
ret
Lawrence

[gerard46]

| Fred L. Kleinschmidt wrote:
|> Travis Willse wrote:
|> pradt,
|>
|> How about the following?
|>
|> min(a,b)=(1/2)*abs(a+b)-(1/2)*abs(a-b)

| This always evaluates to zero.

No, it doesn't. However, for the values

11 -44

the function returns -11 ______________________________Gerard S.
|> Note that from a CS standpoint, this really just buries the conditional
|> inside the definition of the operator abs (which is predefined in most
|> languages, anyway).

[Michael Mair]

gerard46 wrote:

| Fred L. Kleinschmidt wrote:
|> Travis Willse wrote:
|> pradt,
|>
|> How about the following?
|>
|> min(a,b)=(1/2)*abs(a+b)-(1/2)*abs(a-b)

| This always evaluates to zero.

No, it doesn't. However, for the values

11 -44

the function returns -11 ______________________________Gerard S.

No, it evaluates to zero.
Hint: We are talking about 1/2 == 0 (whereas 1/2.0 or 1.0/2
is a completely different matter ;-))
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[gerard46]

| Michael Mair wrote:
|> gerard46 wrote:
|>| Fred L. Kleinschmidt wrote:
|>|> Travis Willse wrote:
|>|> pradt,
|>|>
|>|> How about the following?
|>|>
|>|> min(a,b)=(1/2)*abs(a+b)-(1/2)*abs(a-b)

|>| This always evaluates to zero.

|> No, it doesn't. However, for the values
|>
|> 11 -44
|>
|> the function returns -11 ______________________________Gerard S.

| No, it evaluates to zero.
| Hint: We are talking about 1/2 == 0 (whereas 1/2.0 or 1.0/2
| is a completely different matter ;-))

Ah, I see your problem. You're assumming that I'm using a language
that evaluates 1/2 to 0.
Well, mine doesn't. 1/2 = 0.5 _________________________Gerard S.

[kevin.bagust]

In article <xm****************@news7.onvoy.net>,
gerard46 <ge******@rtt.net> wrote:

| Fred L. Kleinschmidt wrote:
|> Travis Willse wrote:
|> pradt,
|>
|> How about the following?
|>
|> min(a,b)=(1/2)*abs(a+b)-(1/2)*abs(a-b) | This always evaluates to zero. No, it doesn't. However, for the values 11 -44 the function returns -11 ______________________________Gerard S.

Oh yes it does, in C. (Sorry could not resist)

1/2 is equal to 0 using integer maths. So:
(1/2)*abs(a+b)-(1/2)*abs(a-b) == 0*abs(a+b)-0*abs(a-b) == 0

You would need to use floating point maths to get it to work. So it would
be:
(int)( 0.5 *abs(a+b)- 0.5 *abs(a-b)

Kevin.

[David W. Cantrell]

rl*@hoekstra-uitgeverij.nl (Richard Bos) wrote:

David W. Cantrell <DW********@sigmaxi.org> wrote:

Travis Willse <tw*****@gladstone.uoregon.edu> wrote:

pradt,

How about the following?

min(a,b)=(1/2)*abs(a+b)-(1/2)*abs(a-b)

Note that from a CS standpoint, this really just buries the
conditional inside the definition of the operator abs (which is
predefined in most languages, anyway).
Or better: min(a,b) = (1/2)*(a + b - abs(a-b))

FWIW, an alternative to using abs would be

min(a,b) = (1/2)*(a + b - Sqrt((a-b)^2))

Charming. Of course, this requires the #inclusion of <math.h>, (and the
first one requires <stdlib.h>, but you're more likely to have that
already), are probably massively less efficient than a straight
comparison, and can cause overflow that a simple comparison cannot.

Hmm. I had the impression that avoidance of any explicit
comparison/decision structure was the OP's _objective_.

From a mathematical standpoint, both expressions I'd given are correct, and
satisfy the OP's objective (assuming that I understood it correctly).
Oh, and it's spelled sqrt(), not Sqrt(), and the ^ operator does not do
what you think it does.
I never said I was writing anything in any computer language. Surely
if what I wrote did not make sense in a given language, one might
reasonably have assumed that it was not intended to be construed in that
language!

As I suppose you know, by writing (a-b)^2, I was indicating that (a-b) be
squared. And I intended to write Sqrt, rather than sqrt. In doing so, I was
following the convention according to which the principal value of a
multivalued relation is distinguished by capitalisation. For example,
according to that convention, asin(0) has an infinite number of values,
while Asin(0) has the single value 0.
Ben's solution is much better,

I too am a proponent of Iverson bracket notation. However, such a solution
does not meet the OP's objective, at least as I understood it.

David

[Kristofer Pettijohn]

>>min(a,b)=(1/2)*abs(a+b)-(1/2)*abs(a-b)

This always evaluates to zero.

You may be thinking of the last part being abs(b-a)..

Start simple, a=-1, b=1..

= (1/2)*abs(-1+1) - (1/2)*abs(-1-1)
= (1/2)*0 - (1/2)*2
= -1

Kristofer

[Kristofer Pettijohn]

> Oh yes it does, in C. (Sorry could not resist)

1/2 is equal to 0 using integer maths. So:

Heh, I missed that one when I was writing it out on paper. Damn me.

[Keith Thompson]

[...]

Ah, I see your problem. You're assumming that I'm using a language
that evaluates 1/2 to 0.

Not an unreasonable assumption, since a lot of us are reading this in
comp.lang.c.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Travis Willse]

David,

Your formula is right, of course; I was being sloppy. My definition
(needlessly) assumes too much about a and b (and generally fails when
a<0 or b<0, for example).

Regards,
Travis

David W. Cantrell wrote:

Travis Willse <tw*****@gladstone.uoregon.edu> wrote:

pradt,

How about the following?

min(a,b)=(1/2)*abs(a+b)-(1/2)*abs(a-b)

Note that from a CS standpoint, this really just buries the conditional
inside the definition of the operator abs (which is predefined in most
languages, anyway).

Or better: min(a,b) = (1/2)*(a + b - abs(a-b))

FWIW, an alternative to using abs would be

min(a,b) = (1/2)*(a + b - Sqrt((a-b)^2))

David

pr***@yahoo.com wrote:

This might be a silly question. I'm searching for a trick to
prgramatically find minimum of two positive integers without
using a conditional statement/operator('if', '?', etc).

[Ben Pfaff]

"Skybuck Flying" <no****@hotmail.com> writes:

"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
news:87************@benpfaff.org...

pr***@yahoo.com writes:

> This might be a silly question. I'm searching for a trick to
> prgramatically find minimum of two positive integers without
> using a conditional statement/operator('if', '?', etc).

a * (a < b) + b * (a >= b)

a < b

Isn't that simply a compare ? In other words an "if" statement at the
assembler level ? ;)

It's not a conditional statement and it's not the conditional
operator (?:), thus it fits the OP's criteria.
--
Just another C hacker.

[Mark McIntyre]

On Fri, 10 Dec 2004 18:14:30 GMT, in comp.lang.c , "gerard46"
<ge******@rtt.net> wrote:

| No, it evaluates to zero.
| Hint: We are talking about 1/2 == 0 (whereas 1/2.0 or 1.0/2
| is a completely different matter ;-))

Ah, I see your problem.
actually its /your/ problem... :-)
You're assumming that I'm using a language that evaluates 1/2 to 0.
In C, this is a perfect assumption.
Well, mine doesn't. 1/2 = 0.5

You might want consider stopping crossposting to comp.lang.c then, where
integer division cannot result in floating point results.

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>

[Skybuck Flying]

"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
news:87************@benpfaff.org...

"Skybuck Flying" <no****@hotmail.com> writes:

"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
news:87************@benpfaff.org...

pr***@yahoo.com writes:

> This might be a silly question. I'm searching for a trick to
> prgramatically find minimum of two positive integers without
> using a conditional statement/operator('if', '?', etc).

a * (a < b) + b * (a >= b)

a < b

Isn't that simply a compare ? In other words an "if" statement at the
assembler level ? ;)

It's not a conditional statement and it's not the conditional
operator (?:), thus it fits the OP's criteria.

Well hey says etc... ;) so maybe this aint good as well.

It depends on what this code does at the asm level.

Is it a conditional at the asm level that's what's interesting to me ;)

Probably for the cpu as well... if it's not conditional it might be faster
;)

A conditional at asm level is probably something like

cmp
jmp,jne,jz, etc

Bye,
Skybuck.

[Bob Harris]

Mark McIntyre wrote:

You might want consider stopping crossposting to comp.lang.c then, where
integer division cannot result in floating point results.

(chuckle) Well, Mark, then you certainly should stop crossposting to
alt.math.recreational, where unless otherwise stated division is expected to
behave as it does in mathematics.

Bob H

[Bob Harris]

Travis Willse wrote:

min(a,b)=(1/2)*abs(a+b)-(1/2)*abs(a-b)

If abs() is allowed, and if overflow can be ignored, this should always
work:

min(a,b) = (a+b-abs(b-a))/2

If abs() is considered cheating, then |n| can easily be accomplished without
a compare if we know where the sign bit is in n. For 32-bit signed integers
|n| is n*(2*(n>>31)+1). I believe that will work for sign-magnitude as well
as the usual (these days) twos-complement. This of course has overflow
holes in it (e.g. if fails when n is -0x80000000 on a two's complement
machine). And it assumes that >> propagates sign. One could just as easily
use a mask to pick out the sign bit s, then compute u*s+v, where u and s are
chosen so that the two possible results are +1 and -1, then multiply that by
n.

Nearly all the overflow issues can be avoided if you first compute variables
to hold the signs of a and b (based on above technique) and then use these
to create a sum in which all subtotals are zero (because they are multiplied
by something that is zero) except the correct answer.

Bob H

P.S. Note that |n| is intended to mean 'absolute value of n'.

[Oppie]

Well, why not just take max(a,b) and then choose the other one!

Bob Harris wrote:

Travis Willse wrote:

min(a,b)=(1/2)*abs(a+b)-(1/2)*abs(a-b)

If abs() is allowed, and if overflow can be ignored, this should always
work:

min(a,b) = (a+b-abs(b-a))/2

If abs() is considered cheating, then |n| can easily be accomplished without
a compare if we know where the sign bit is in n. For 32-bit signed integers
|n| is n*(2*(n>>31)+1). I believe that will work for sign-magnitude as well
as the usual (these days) twos-complement. This of course has overflow
holes in it (e.g. if fails when n is -0x80000000 on a two's complement
machine). And it assumes that >> propagates sign. One could just as easily
use a mask to pick out the sign bit s, then compute u*s+v, where u and s are
chosen so that the two possible results are +1 and -1, then multiply that by
n.

Nearly all the overflow issues can be avoided if you first compute variables
to hold the signs of a and b (based on above technique) and then use these
to create a sum in which all subtotals are zero (because they are multiplied
by something that is zero) except the correct answer.

Bob H

P.S. Note that |n| is intended to mean 'absolute value of n'.

--
Oppie the Bear
aka TOJ (The Other John)

'Remove' MYWORRIES to email me!

In the beginning, there was nothing.
And God said, 'Let there be Light.'
And there was still nothing,
but you could see a bit better.

[Mark McIntyre]

On Sat, 11 Dec 2004 20:04:50 GMT, in comp.lang.c , Bob Harris
<pl************@wrappermindspring.com> wrote:

Mark McIntyre wrote:

You might want consider stopping crossposting to comp.lang.c then, where
integer division cannot result in floating point results.
(chuckle) Well, Mark, then you certainly should stop crossposting to
alt.math.recreational,

Well, yes. But if I'd done that, you would not have seen my reply. The
point is, your answers were Just Plain Wrong (tm) in CLC so x-posting to
CLC was bound to raise heckles.
where unless otherwise stated division is expected to
behave as it does in mathematics.

Mayhap, tho personally I fundamentally disagree that integer maths should
EVER yield floating point results, and if you in AMR don't agree, you're
slightly strange mathematicians.

But then I didn't start the cross post so....

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>

[Bob Harris]

Mark McIntyre wrote:

On Sat, 11 Dec 2004 20:04:50 GMT, in comp.lang.c , Bob Harris
<pl************@wrappermindspring.com> wrote:

Mark McIntyre wrote:

You might want consider stopping crossposting to comp.lang.c then, where
integer division cannot result in floating point results.

(chuckle) Well, Mark, then you certainly should stop crossposting to
alt.math.recreational,

Well, yes. But if I'd done that, you would not have seen my reply. The
point is, your answers were Just Plain Wrong (tm) in CLC so x-posting to
CLC was bound to raise heckles.

*My* answers? I didn't provide any answers prior to my post above.

where unless otherwise stated division is expected to
behave as it does in mathematics.

Mayhap, tho personally I fundamentally disagree that integer maths should
EVER yield floating point results, and if you in AMR don't agree, you're
slightly strange mathematicians.

But then I didn't start the cross post so....

[Albert van der Horst]

In article <cp**********@news4.zwoll1.ov.home.nl>,
Skybuck Flying <no****@hotmail.com> wrote:

"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
news:87************@benpfaff.org...

pr***@yahoo.com writes:

> This might be a silly question. I'm searching for a trick to
> prgramatically find minimum of two positive integers without
> using a conditional statement/operator('if', '?', etc).
a * (a < b) + b * (a >= b)

a < b

Isn't that simply a compare ? In other words an "if" statement at the
assembler level ? ;)

Not on some modern architectures, like DEC Alpha and IA64.
This translates to a single instruction, setting a register
with a value derived from the values from two other registers.
Because jumps are avoided, pipe lines don't stall, and this may be
substantially faster. I speculate that this is the OP's intent
(if it is not a homework assignment.)

Back to the c-language. A compiler for such architecture will
probably recognize the idiomatic ( a<b ? a : b )
and compile it into a sequence without control instructions and
optimal speed.

Bye,
Skybuck.

--
--
Albert van der Horst,Oranjestr 8,3511 RA UTRECHT,THE NETHERLANDS
One man-hour to invent,
One man-week to implement,
One lawyer-year to patent.

[Frank J. Lhota]

"Bob Harris" <pl************@wrappermindspring.com> wrote in message
news:BDE0BC99.453E7%pl************@wrappermindspri ng.com...

Mark McIntyre wrote:

You might want consider stopping crossposting to comp.lang.c then, where
integer division cannot result in floating point results.

(chuckle) Well, Mark, then you certainly should stop crossposting to
alt.math.recreational, where unless otherwise stated division is expected
to
behave as it does in mathematics.

And don't those Mathematicians realize that for unsigned integers, -1 > 0?