[mike0613]

Looking for a simple algorithm/expression to find min of two numbers using only four basic arithmetic operators (add, subtract, multiply, divide).

Alternatively, find how to make '1' if a<b and '0' otherwise (again, using only the 4 arithmetic operators). Knowing how to do this I can answer the original question.

Another route is to be able to get an absolute value of a - b using the 4 operators above. Knowing this will also enable me to answer the original question.

Thanks,
Mike

This post has been edited by mike0613: 15 September 2009 - 10:39 PM

[Ter13]

mike0613, on 15 Sep, 2009 - 09:31 PM, said:

Looking for a simple algorithm/expression to find min of two numbers using only four basic arithmetic operators (add, subtract, multiply, divide).

Alternatively, find how to make '1' if a<b and '0' otherwise (again, using only the 4 arithmetic operators). Knowing how to do this I can answer the original question.

Another route is to be able to get an abs(a, using the 4 operators above. Knowing this will also enable me to answer the original question.

Thanks,
Mike

Can't use the min( a , b ) function? Sounds like a highschool programming assignment if you can't...

This post has been edited by Ter13: 15 September 2009 - 10:40 PM

[OliveOyl3471]

[rules][/rules]

BUT, without giving too much code...

You only need the minimum of TWO numbers? That's easy. You don't need + - * /.
Just if's.

 if(x<y){
//then x is minimum number
}
else{
//then y is minimum number
}

edit--or did you mean that you're not allowed to use the <> signs?
You could make them both ints and check if a/b==0.

int a, b;
if(a/b == 0){
	   cout<<a<<" is lowest.";
}
	   else{
			cout<<b<<" is lowest.";
	   }

Quote

Alternatively, find how to make '1'

How to make what '1'?

This post has been edited by OliveOyl3471: 15 September 2009 - 11:00 PM

[yoni162]

Another way, if you have to use only +/- operators, is to look at the difference between 2 numbers. For example, the numbers 3 and 5. 3-5 is less than 0, therefore 3<5. so your functions return value will be 1.
For any 2 numbers a and b, just check the difference a-b.

[baavgai]

These sort of questions kind of annoy me. Not your fault, it just means you instructor is either math person and really doesn't get computers or is just being overly cute.

Without a conditional, you're stuck with a pure functional kind of deal. Even less, actually. This would be easy enough, but your ability to do real math has been crippled by a limited operation set. To expand the operation set you need some conditional logic.

You really need an abs function. You could actually fake this with square root. You could write your own square root, but now you need a conditional again. Your only option left is to give up on real math and see if you can exploit the limitations of the computer language you're working in.

Here's one exploit: floating point.

e.g.

f(n) = 1/n
f(-3) = -0.333333
f(-2) = -0.5
f(-1) = -1
f(0) = oops
f(1) = 1
f(2) = 0.5
f(3) = 0.333333

We could be able to do something with this. We need to allow for zero.

Long story short:

f(n) = 1.0-(0.01/(n+0.1))
f(-3) = 1.00345
f(-2) = 1.00526
f(-1) = 1.01111
f(1) = 0.990909
f(2) = 0.995238
f(3) = 0.996774

Cast that puppy as an int and you have to building block for the answer.

int isNeg(int n) { return 1.0-(0.01/(n+0.1)); }

You're using the built in behavior of the language to toss the float and essentially do a floor. But you're not calling for, you're just using C as it behaves normally. If it feels like a hack, it is.

It's pretty simple to roll your own abs from there.

Hope this helps. Please smack you instructor for me.

[hawkysu]

This is the forumula for calculating 1

(x+y)/0+1

[NickDMax]

I am pretty sure that division by zero is unlikely to work...

[NickDMax]

mike0613, on 16 Sep, 2009 - 12:31 AM, said:

Alternatively, find how to make '1' if a<b and '0' otherwise (again, using only the 4 arithmetic operators). Knowing how to do this I can answer the original question.

HINT:

Lets take a look at a-b

if a == b then a-b = 0
if a > b then a-b > 0
if a < b then a-b < 0

Now lets take a look at that last one -- computers use the two's complement to represent negative numbers. One result of that is that all negative numbers as the MSB set -- so given a 32 bit number all negatives are of the form:
1xxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx -- So if we want to see if a number is negative we only have to check that one bit!

So if we want 0 for a == b and a > b but 1 for a < b all we have to do is shift that bit down to the LSB spot -- turns out that left sift is the same as division by a power of 2. Once we do our sift, had the value been > 0 then of course the result would be 0 (since we are only looking at the MSB of the 32 bits, so if it was 0 to begin with, then our result is 0).

So... what if we don't know how many bits the compiler is using? We can't use sizeof() since that is an operator and we are only allowed the 4 arithmatic operators! Well C has a header file limits.h or climits in C++ which has a value of use to us. UINT_MAX is the largest value an unsigned (hint hint) value can have, so our required shift value is:

const unsigned int SHIFT_VALUE = UINT_MAX/2+1;

[mike0613]

Thanks for all the answers but unfortunately they all miss the point of the question. I guess it's my fault - it really belongs in a math section - I just couldn't find one on this forum.

No conditional statements are allowed, no floating point, no min( a,b ), and of course, no division by zero... You can only use the two given numbers ( a and b ), and the four basic arithmetic operators - as per original question. So no MAX_UINT32 or any other constants either - unless you are able to produce them from a and b with + , - , * and /.

<To make '1' or '0'> means exactly that - the result of the operation should be '1' or '0' depending on whether a>b or b>a.

If you just want to make '1' (unconditionally) a/a will do, and to make '0', you do a-a of course.

It is not homework, it is more of a brainteaser or a riddle, but it is still a well defined programming question, to which there definitely is a valid answer (solution). The programming language really doesn't matter, I just put it here because I know C best.

Any more ideas?

This post has been edited by mike0613: 17 September 2009 - 02:53 AM

[carltech]

How about this ans = ~((a-b )>>255).

This post has been edited by carltech: 17 September 2009 - 05:19 PM

[mike0613]

carltech, on 17 Sep, 2009 - 04:16 PM, said:

How about this ans = ~(( a-b )>>255).

How do you do inverse (~), shift (>>) and constant (255) when all you have is the two input nmbers ( a and b ), and the four arithmetic operators?

[pareidolia]

I tried doing gymathtics with the absolute value problem and no matter what I did a negative product or quotient had to be involved. I don't know if this is right but wouldnt:

1 = a/a
0 = a/a - a/a

[NickDMax]

Well you DID ask the question in a C/C++ programming forum and so we assumed that it was a programming question.

So the question is: using only the 4 basic arithmetic operations can you construct a map of the form:

F: Z x Z --> Z

where F will give the minimum of its two arguments.

You claim that if we can come up with:

F: Z x Z --> {0, 1}

Where F( a, b ) = 0 if a == b or a < b, and 1 if a > b.

Well lets say c = a - b, we can map this to {-1, 0, 1} if we have the absolute value using d = c / | c | -- however the absolute value really requires the Square root function.

d = c / √( c * c )

<edit>Actually the absolute value would only work if a is not equal b i.e. c is not zero</edit>

I could be wrong, but I really don't think that you CAN express
F: Z x Z --> Z where F(x, y) is min(x, y) in terms of the 4 basic arithmetic functions.

In C its actually kind of easy though.

[NickDMax]

Actually in C you would need at least 1 constant (even if its value was 1) -- see you said that you need to make any constants out of a and b, no problem BUT you have no way to tell if a or b is zero -- so you have a problem because you need a value that would have to be formed though mathematical operations, but if a and b are zero the 4 math operations will only give you 0.

I really would love to see what your teacher says the answer is. I would put money down that you have the rules of the problem wrong.

however I still may be wrong.

[OliveOyl3471]

I think you are right, Nick.

Except for one thing...if a and b are both zero, then you'd get zero for three of the math operations, and you can't do division at all.

How could you figure out which is the larger and which is the smaller without using any conditional statements? How can you make the result of the operation on the two numbers always turn out to be 1 if a is larger and always turn out to be 0 otherwise, without a conditional statement to determine which is larger or smaller? That just does not make sense!

This post has been edited by OliveOyl3471: 18 September 2009 - 12:02 AM