ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexandr A. Redchuck                 2:5020/400     29 Dec 2002  01:40:53
 To : Sergey Andrianov
 Subject : Re: Ускорение поиска максимума...
 -------------------------------------------------------------------------------- 
 

 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() без сравнений? Hа поразрядной
 SA> логике что ли? :)
 
 Именно на ней.
 Для представления целых знаковых чисел с дополнением до 2:
     ; выяснение условия val<0
   <вспомогательный регистр> := <расширение знака рабочего регистра>
     ; "услованая инверсия"
   <рабочий регистр> := <рабочий регистр> XOR <вспомогательный регистр>
     ; "условный инкремент"
   <рабочий регистр> := <рабочий регистр> - <вспомогательный регистр>
 
 Правда, при этом abs(INT_MIN) возвращает все тот же INT_MIN,
 но это в точности то же самое, что сделает
   if (val<0) val=-val;
 
 wbr,
 Кстати, если уж говорить о "неветвящихся" способах, то
 получение максимума можно сделать в виде
  <рег. максимума> := <рег. максимума> - <новое значение>
  <вспом. регистр> := <расширение знака рег. максимума>
  <вспом. регистр> := <инверсия вспом. регистра> ; не нужно при Min
  <рег. максимума> := <рег. максимума> AND <вспом. регистр>
  <рег. максимума> := <рег. максимума> + <новое значение>
 
 Hо этот алгоритм  не к паскалю и не к С. Хотя современные могли бы
 реализовать такую функцию 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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: Ускорение поиска максимума...   Alexandr A. Redchuck   29 Dec 2002 01:40:53   Re: Ускорение поиска максимума...   Sergey Andrianov   30 Dec 2002 23:59:32