Re: Ускорение поиска максимума...

From

Alexandr A. Redchuck ()

To

Sergey Andrianov

Date

2002-12-29T00:40:53Z

Area

RU.ALGORITHMS

From: "Alexandr A. Redchuck" <real@real.kiev.ua>

26-Dec-02 23:13 Sergey Andrianov wrote to Alexander Chelmodeev:

AC>>    max:= (max+ar[n] + Abs(max-ar[n])) div 2 ;
AC>>    min:= (min+ar[n] - Abs(min-ar[n])) div 2 ;
AC>>  end;

SA>     А как ты собираешься реализовать Abs() без сравнений? На поразрядной
SA> логике что ли? :)
Именно на ней.
Для представления целых знаковых чисел с дополнением до 2:
    ; выяснение условия val<0
  <вспомогательный регистр> := <расширение знака рабочего регистра>
    ; "услованая инверсия"
  <рабочий регистр> := <рабочий регистр> XOR <вспомогательный регистр>
    ; "условный инкремент"
  <рабочий регистр> := <рабочий регистр> - <вспомогательный регистр>

Правда, при этом abs(INT_MIN) возвращает все тот же INT_MIN,
но это в точности то же самое, что сделает
  if (val<0) val=-val;

wbr,
Кстати, если уж говорить о "неветвящихся" способах, то
получение максимума можно сделать в виде
 <рег. максимума> := <рег. максимума> - <новое значение>
 <вспом. регистр> := <расширение знака рег. максимума>
 <вспом. регистр> := <инверсия вспом. регистра> ; не нужно при Min
 <рег. максимума> := <рег. максимума> AND <вспом. регистр>
 <рег. максимума> := <рег. максимума> + <новое значение>

Но этот алгоритм  не к паскалю и не к С. Хотя современные могли бы
реализовать такую функцию Max(a,b), ведь Abs()-то они таки делают без
условных переходов, по кр. мере еще BC3.1 генерит
;      return  abs(a);
  mov     ax,word ptr [bp+4]
  cwd
  xor     ax,dx
  sub     ax,dx

--
/* Alexandr Redchuck, Kyiv, Ukraine */
/* real на real тчк kiev тчк ua     */

--- ifmail v.2.15dev5
 * Origin: ReAl at home (2:5020/400)