Можно ли вычислить минимум трех чисел, используя одновременно два сравнения?

Question

Я пытался придумать, каким образом я мог бы сделать два сравнения одновременно, чтобы найти наибольшее/меньшее из трех чисел. В этом случае арифметические операции над ними считаются «свободными».

То есть классический способ нахождения большего из двух, а затем сравнение его с третьим числом недействителен в этом случае, потому что одно сравнение зависит от результата другого.

Можно ли использовать два сравнения, где это не так? Я думал, может быть, сравнивать различия чисел как-то или их продуктов или что-то в этом роде, но ничего не придумал.

Для того, чтобы еще раз подчеркнуть, до сих пор выполняются два сравнения, только ни одно сравнение не зависит от результата другого сравнения.

Больших ответов до сих пор, спасибо, ребята

Answer 1

Я думаю, что это возможно (следующее за мин, в зависимости от исходной формы вопроса):

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

, а затем вы их объединяете (я должен написать его последовательно, но это скорее 3-позиционный переключатель):

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 

Вы можете утверждать, что abs() подразумевает сравнение, но это зависит от оборудования. Для целых чисел существует a trick to do it without comparison. Для плавающей точки IEEE 754 это всего лишь вопрос заставлять бит знака равняться нулю.

Относительно (A + B - abs(A - B))/2: это (A + B)/2 - abs(A - B)/2, то есть минимум A и B составляет половину расстояния между A и B вниз от их средней точки. Это можно применить снова, чтобы получить min (A, B, C), но тогда вы потеряете личность минимум, то есть знаете только значение минимум, но не там, где оно исходит.

В какой-то день мы можем обнаружить, что параллелизация 2 сравнений дает лучшее время обработки или даже пропускную способность в некоторой ситуации. Кто знает, может быть, для некоторой векторизации, или для некоторого MapReduce, или для чего-то, о чем мы еще не знаем.

Answer 2

Игнорирования возможности равных значений («связь»), есть 3! : = 6 возможных порядков из трех элементов. Если сравнение дает ровно один бит, то два сравнения могут кодировать только 2 * 2: = 4 возможных конфигураций. и 4 < 6. IOW: вы не можете выбрать порядок из трех предметов, используя 2 фиксированных сравнения.

---

Используя таблицу истинности:

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) <<--- (*) 

Как вы можете видеть, вы не можете различить два случая, отмеченные (*), при использовании только a<b и a<c сравнения. (выбор другого набора из двух сравнений, конечно, потерпит неудачу аналогично (по симметрии)).

Но жаль: мы не кодировать три возможных результатов, используя только два бита. (Да, мы могли бы, но мы должны были бы третье сравнение, или выбрать второе сравнение на основе результатов первого)

Answer 3

От Bit Twiddling Hacks

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

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

два сравнения!

Answer 4

Как об этом, чтобы найти минимум:

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

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

Return a; 

Answer 5

Если вы только говорить целые числа, я думаю, что вы можете сделать это с нуля, используя сравнения математикой и немного скрипку. Учитывая три ИНТ значений а, Ь, с:

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) 

с Abs (х) реализован в виде

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

Не тщательно протестированы, так что я, возможно, что-то пропустил.Кредит на Abs битного Twiddle идет к этим источникам

How to compute the integer absolute value

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

Answer 6

Вы можете сделать это с нулевым сравнением в теории, предполагая представление номера дополнения 2 (и чтобы правое смещение знакового числа сохраняло свой знак).

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

, а затем

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

Это работает, потому что если предположить a >> bit_depth дает 0 для положительных чисел и -1 для отрицательных чисел, то 2*(a>>bit_depth)+1 дает 1 для положительных чисел и -1 для отрицательных чисел. Это дает функцию signum, и мы получаем abs(a) = signum(a) * a.

Тогда это всего лишь вопрос формулы min (a, b). Это можно продемонстрировать, пройдя две возможности:

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 

Таким образом, формула для min (a, b) работает.

Предположения, приведенные выше, применяются только к функции abs(), если вы можете получить функцию 0-сравнения abs() для вашего типа данных, тогда вы хорошо пойдете.

Например, данные с плавающей точкой IEEE754 имеют бит знака как верхний бит, поэтому абсолютное значение просто означает очистку этого бита. Это означает, что вы также можете использовать числа с плавающей запятой.

И тогда вы можете продлить это до min из N номеров в 0 сравнениях.

На практике, однако, трудно представить, что этот метод будет бить что-либо, что не преднамеренно медленнее.Это всего лишь использование менее 3 независимых сравнений, а не создание чего-то более быстрого, чем простое внедрение на практике.

Answer 7

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