8

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

Milo Hou
  • 239
  • 2
  • 17
  • Related: http://stackoverflow.com/questions/9576557/most-efficient-way-to-find-smallest-of-3-numbers-java – megawac Nov 06 '13 at 20:44
  • @user2864740 what conditions would need to be put on the 3 numbers then? I don't think it'd make comparison sort constant time, since the same amount of comparisons are still used, the only difference is a matter of sequence – Milo Hou Nov 06 '13 at 20:51
  • 1
    regarding your edit: isn't elseif a comparison that depends on the result of the first comparison "if boolA"? just trying to clarify the rules of the game here – Tom Swifty Nov 06 '13 at 21:29
  • @TomSwifty hm good point, my thought process was that the else if used a boolean that was already calculated simultaneously with boolA – Milo Hou Nov 06 '13 at 21:55
  • 1
    your "what about" does not work. `A=100, B=101, C=102`, or `A=1, B=2, C=-3` – Walter Tross Nov 06 '13 at 22:09
  • @WalterTross why doesn't it? 9 > 5, so max = 3 – Milo Hou Nov 06 '13 at 22:15
  • my second triple ended with a `-3` - and then there is the first... – Walter Tross Nov 06 '13 at 22:17

7 Answers7

5

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)

wildplasser
  • 43,142
  • 8
  • 66
  • 109
  • hm seems like it makes sense, what would be the analogous bits for the sequential comparisons then? – Milo Hou Nov 06 '13 at 21:06
  • 4
    Good point. On second thought, if you only care what is the minimum value, there are just three possibilities, not six. –  Nov 06 '13 at 21:06
  • 1
    @MiloHou the sequential comparisons take advantage of the triangle inequality. If A < B and B < C and you already know the results of the A < C comparison. – Adam Nov 06 '13 at 21:07
  • I thought some cleverness may have been possible if infinite arithmetic was allowed, is this not the case? what if i compared A^2+B^2 vs C^2 along with A and B? then I could know if C was the max and also the greater of A and B – Milo Hou Nov 06 '13 at 21:15
  • @MiloHou - 5^2 + 10^2 < 11^2, yet 11 > 10 > 5. – mbeckish Nov 06 '13 at 21:36
  • @jdv-JandeVaan: good point. But the enumeration is on the input (six possible configurations) not on the result (three possible outcomes) – wildplasser Nov 06 '13 at 21:41
  • @wildplasser- I was thinking about making an argument like this but there's a bit of a gap I'm stuck on. Although there are six permutations, multiple permutations can result in the same answer. With four possible outcomes, you could conceivably design the comparisons so that two distinct permutations with the same maximum value do indeed end up producing the same answer. Can you explain why that would be impossible? – templatetypedef Nov 06 '13 at 21:43
  • @mbeckish that's my point exactly. you can find if C is the max with only one comparison, and use the other comparison to find the max of A and B – Milo Hou Nov 06 '13 at 21:49
  • 3
    The question is about finding minimum, which has 3 possible outcomes, not ordering the numbers. Therefore 2 comparison is enough. The problem is in making them independent. – Michael Nov 06 '13 at 21:50
3

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.

Walter Tross
  • 12,237
  • 2
  • 40
  • 64
1

If you were only talking integers, I think you can do it with zero comparisons using some math and a bit fiddle. Given three int values a, b, and c:

int d = ((a + b) - Abs(a - b)) / 2; // find d = min(a,b)
int e = ((d + c) - Abs(d - c)) / 2; // find min(d,c)

with Abs(x) implemented as

int Abs(int x) {
    int mask = x >> 31;
    return (x + mask) ^ mask;
}

Not extensively tested, so I may have missed something. Credit for the Abs bit twiddle goes to these sources

How to compute the integer absolute value

http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs

Community
  • 1
  • 1
hatchet - done with SOverflow
  • 15,919
  • 5
  • 47
  • 57
0

From Bit Twiddling Hacks

r = y ^ ((x ^ y) & -(x < y)); // min(x, y)

min = r ^ ((z ^ r) & -(z < r)); // min(z, r)

Two comparisons!

Doug Currie
  • 40,708
  • 1
  • 95
  • 119
  • 2
    There are two comparisons done here - one between `x` and `y` and one between `z` and `r`. The comparison on `r` is a dependent comparison. – templatetypedef Nov 06 '13 at 21:43
0

How about this to find the minimum:

If (b < a)
   Swap(a, b)

If (c < a)
   Swap(a, c)

Return a;
  • 2
    Does this technically count as a dependent comparison, since the value being compared in the second step depends on the outcome of the first comparison? – templatetypedef Nov 06 '13 at 21:44
  • I'm not sure what you mean. Was dependent compare not allowed by the OP? –  Nov 06 '13 at 21:46
  • yes dependent compare isn't allowed because you'd have to do one after the other – Milo Hou Nov 06 '13 at 21:48
0

You can do this with zero comparisons in theory, assuming 2's complement number representation (and that right shifting a signed number preserves its sign).

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

and then

    min(a,b,c) = min(min(a,b),c)

This works because assuming a >> bit_depth gives 0 for positive numbers and -1 for negative numbers then 2*(a>>bit_depth)+1 gives 1 for positive numbers and -1 for negative numbers. This gives the signum function and we get abs(a) = signum(a) * a.

Then it's just a matter of the min(a,b) formula. This can be demonstrated by going through the two possibilities:

    case min(a,b) = a:
    min(a,b) = (a+b - -(a-b))/2
    min(a,b) = (a+b+a-b)/2
    min(a,b) = a

    case min(a,b) = b:
    min(a,b) = (a+b-(a-b))/2
    min(a,b) = (a+b-a+b)/2
    min(a,b) = b

So the formula for min(a,b) works.

The assumptions above only apply to the abs() function, if you can get a 0-comparison abs() function for your data type then you're good to go.

For example, IEEE754 floating point data has a sign bit as the top bit so the absolute value simply means clearing that bit. This means you can also use floating point numbers.

And then you can extend this to min of N numbers in 0 comparisons.

In practice though, it's hard to imagine this method will beat anything not intentionally slower. This is all about using less than 3 independent comparisons, not about making something faster than the straightforward implementation in practice.

SirGuy
  • 10,660
  • 2
  • 36
  • 66
0
if cos(1.5*atan2(sqrt(3)*(B-C), 2*A-B-C))>0 then 
  A is the max
else
  if cos(1.5*atan2(sqrt(3)*(C-A), 2*B-C-A))>0  then 
    B is the max
  else                   
    C is the max
Egor Skriptunoff
  • 23,359
  • 2
  • 34
  • 64