How to find minimum of two numbers.

P

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).
 
T

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
 
T

Trent Buck

Up spake (e-mail address removed):
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).
Click to expand...

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

David W. Cantrell

Travis Willse said:
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).
Click to expand...

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
 
B

Ben Pfaff

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).
Click to expand...

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

Richard Bos

David W. Cantrell said:
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))
Click to expand...

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
 
S

Skybuck Flying

Travis Willse said:
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).
Click to expand...

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

Bye,
Skybuck.
 
S

Skybuck Flying

Ben Pfaff said:
a * (a < b) + b * (a >= b)
Click to expand...

a < b

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

Bye,
Skybuck.
 
L

Lawrence Kirby

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

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
 
L

Lawrence Kirby

a < b

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

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
 
G

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).
 
M

Michael Mair

gerard46 said:
| 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.
Click to expand...

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
 
G

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.
 
K

kevin.bagust

| 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)
Click to expand...
| This always evaluates to zero.
Click to expand...
No, it doesn't. However, for the values
Click to expand...
11 -44
Click to expand...
the function returns -11 ______________________________Gerard S.
Click to expand...

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.
 
D

David W. Cantrell

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.
Click to expand...

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.
Click to expand...

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,
Click to expand...

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
 
K

Kristofer Pettijohn

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

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
 
K

Kristofer Pettijohn

Oh yes it does, in C. (Sorry could not resist)
> 1/2 is equal to 0 using integer maths. So:
Click to expand...

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

Keith Thompson

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

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

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Minimum Total Difficulty 0
C program to find minimum solution to reach a number N using only two opration. 6
Sum of two arrays 3
Minimising chi square to fit two parameters 1
Program to find the largest integer element of an array. 1
How to find and deal with maximum and minimum numbers? 8
Pyautogui, cv2 and cannot find image 0
Logic Problem with BigInteger Method 2

Members online

No members online now.
Total: 22 (members: 0, guests: 22)
Robots: 613

Forum statistics

Threads
473,769
Messages
2,569,581
Members
45,057
Latest member
KetoBeezACVGummies

Latest Threads

Top