Is it possible to compute the minimum of three numbers by using two comparisons at the same time?

Question

I've been trying to think up of some way that I could do two comparisons at the same time to find the greatest/least of three numbers. Arithmetic operations on them are considered "free" in this case.

That is to say, the classical way of finding the greater of two, and then comparing it to the third number isn't valid in this case because one comparison depends on the result of the other.

Is it possible to use two comparisons where this isn't the case? I was thinking maybe comparing the differences of the numbers somehow or their products or something, but came up with nothing.

Just to reemphasize, two comparisons are still done, just that neither comparison relies on the result of the other comparison.

Great answers so far, thanks guys

Answer 1

Ignoring the possibility of equal values ("ties"), there are 3! := 6 possible orderings of three items. If a comparison yields exactly one bit, then two comparisons can only encode 2*2 := 4 possible configurations. and 4 < 6. IOW: you cannot decide the order of three items using two fixed comparisons.

---

Using a truth table:

a b c|min|a<b a<c b<c| condition needed using only a<b and a<c
-+-+-+---+---+---+---+------------------
1 2 3| a | 1   1   1 | (ab==1 && ac==1)
1 3 2| a | 1   1   0 |  ...
2 1 3| b | 0   1   1 | (ab==0 && ac==1)
3 1 2| b | 0   0   1 | (ab==0 && ac==0) <<--- (*)
2 3 1| c | 1   0   0 | (ab==1 && ac==0)
3 2 1| c | 0   0   0 | (ab==0 && ac==0) <<--- (*)

As you can see, you cannot distinguish the two cases marked by (*), when using only the a<b and a<c comparisons. (choosing another set of two comparisons will of course fail similarly, (by symmetry)).

But it is a pity: we fail to encode the three possible outcomes using only two bits. (yes, we could, but we'd need a third comparison, or choose the second comparison based on the outcome of the first)

Answer 2

I think it's possible (the following is for the min, according to the original form of the question):

B_lt_A = B < A
C_lt_min_A_B = C < (A + B - abs(A - B)) / 2

and then you combine these (I have to write it sequentially, but this is rather a 3-way switch):

if (C_lt_min_A_B) then C is the min
else if (B_lt_A)  then B is the min
else                   A is the min

You might argue that the abs() implies a comparison, but that depends on the hardware. There is a trick to do it without comparison for integers. For IEEE 754 floating point it's just a matter of forcing the sign bit to zero.

Regarding (A + B - abs(A - B)) / 2: this is (A + B) / 2 - abs(A - B) / 2, i.e., the minimum of A and B is half the distance between A and B down from their midpoint. This can be applied again to yield min(A,B,C), but then you lose the identity of the minimum, i.e., you only know the value of the minimum, but not where it comes from.

One day we may find that parallelizing the 2 comparisons gives a better turnaround time, or even throughput, in some situation. Who knows, maybe for some vectorization, or for some MapReduce, or for something we don't know about yet.