Какой самый быстрый способ получить абсолютное значение числа

Условные выражения медленнее, чем простые арифметические операции, но намного, намного быстрее, чем такие глупые операции, как вычисление квадратного корня.

Эмпирические правила из моих сборочных дней:

• Целочисленная или побитовая операция: 1 цикл
• Добавление/подчинение/множение с плавающей запятой: 4 цикла
• div с плавающей запятой: ~ 30 циклов
• Возведение в степень с плавающей запятой: ~ 200 циклов
• sqrt с плавающей запятой: ~60 циклов в зависимости от реализации
• Условная ветвь: ср. 10 циклов, лучше, если они хорошо спрогнозированы, гораздо хуже, если спрогнозированы неверно

Существует отличный трюк для вычисления абсолютного значения целого числа с дополнением до 2 без использования оператора if. Теоретически, если значение отрицательное, вы хотите переключить биты и добавить один, в противном случае вы хотите передать биты как есть. XOR 1 переключает A, а XOR 0 оставляет A нетронутым. Итак, вы хотите сделать что-то вроде этого:

  uint32_t temp = value >> 31;     // make a mask of the sign bit
  value ^= temp;                   // toggle the bits if value is negative
  value += temp & 1;               // add one if value was negative

В принципе можно сделать всего за три инструкции по сборке (без ветки). И вы хотели бы думать, что функция abs(), которую вы получаете с math.h, делает это оптимально.

Нет ветвей == лучшая производительность. Вопреки ответу @paxdiablo выше, это действительно важно в глубоких конвейерах, где чем больше ветвей у вас есть в вашем коде, тем больше вероятность того, что ваш предсказатель ветвления ошибется и вам придется откатиться и т. д. Если вы избегаете ветвления, где возможно, в вашем ядре все будет продолжаться полным ходом :).

Вычисление квадратного корня, вероятно, одна из худших вещей, которые вы можете сделать, потому что это очень медленно. Обычно для этого есть библиотечная функция; что-то вроде Math.Abs(). Умножение на -1 также не нужно; просто верните -x. Поэтому хорошим решением будет следующее.

(x >= 0) ? x : -x

Компилятор, вероятно, оптимизирует это до одной инструкции. Условия могут быть довольно дорогими на современных процессорах из-за длинных конвейеров выполнения — вычисления должны быть выброшены, если ветвь была предсказана неправильно, и процессор начал выполнять инструкции с неправильного пути кода. Но из-за упомянутой оптимизации компилятора в этом случае вам все равно.

Для полноты вот способ сделать это для IEEE float в системах x86 на C++:

*(reinterpret_cast<uint32_t*>(&foo)) &= 0xffffffff >> 1;

Какой самый быстрый способ получить абсолютное значение числа

Я думаю, что «правильного» ответа здесь нет. Вероятно, самый быстрый способ получить абсолютное число — использовать Intel Intrinsic. См. https://software.intel.com/sites/landingpage/IntrinsicsGuide/ и ищите «vpabs» (или другую встроенную функцию, которая выполняет работу для вашего процессора). Я почти уверен, что это превзойдет все остальные решения здесь.

Если вам не нравятся встроенные функции (или вы не можете их использовать или ...), вы можете проверить, достаточно ли умен компилятор, чтобы выяснить, является ли вызов «собственного абсолютного значения» (std::abs в С++ или Math.Abs(x) в С#) автоматически изменится на встроенный - в основном это включает просмотр дизассемблированного (скомпилированного) кода. Если вы используете JIT, убедитесь, что оптимизация JIT не отключена.

Если это также не дает вам оптимизированных инструкций, вы можете использовать метод, описанный здесь: https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs .

Вариант if почти наверняка будет слепо быстрым по сравнению с извлечением квадратного корня, поскольку обычно он транслируется в инструкцию условного перехода на уровне машинного кода (после вычисления выражения, которое может быть сложным, но не в этом случае, так как это простая проверка меньше 0).

Извлечение квадратного корня из числа, вероятно, будет намного медленнее (метод Ньютона, например, будет использовать много-много операторов if на уровне машинного кода).

Вероятным источником путаницы является тот факт, что if неизменно приводит к непоследовательному изменению указателя инструкции. Это может замедлить работу процессоров, которые предварительно загружают инструкции в конвейер, поскольку им приходится повторно заполнять конвейер при неожиданном изменении адреса.

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

Операция по модулю используется для нахождения остатка, вы имеете в виду абсолютное значение. Я изменил вопрос, потому что должно быть так: если !pos(x), то x = x*-1. (не пропало)

Я бы не стал беспокоиться об эффективности оператора if. Вместо этого сосредоточьтесь на удобочитаемости вашего кода. Если вы обнаружите, что существует проблема с эффективностью, сосредоточьтесь на профилировании своего кода, чтобы найти реальные узкие места.

Если вы хотите следить за эффективностью во время написания кода, вам следует беспокоиться только о сложности ваших алгоритмов.

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

Умножение на -1 и проверка того, больше ли значение 0, можно свести к одной ассемблерной инструкции.

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

Время, необходимое для извлечения квадратного корня, намного больше, чем время, необходимое для извлечения условного выражения. Если вас учили избегать условных операторов, потому что они медленные, значит, вас дезинформировали. Они намного медленнее, чем тривиальные операции, такие как сложение или вычитание целых чисел или сдвиг битов, поэтому развертывание циклов может быть полезным, только если вы выполняете такие тривиальные операции. Но по большому счету условные предложения хороши и быстры, а не плохи и медленны. Делать что-то настолько сложное, как вызов функции или вычисление квадратного корня, чтобы избежать условного оператора, — это сумасшествие.

Кроме того, вместо (x = x * -1) почему бы не сделать (x = 0 - x)? Может быть, компилятор оптимизирует их одинаково, но не проще ли второй?

Вы используете сборку 8086? ;-)

                ; abs value of AX
   cwd          ; replicate the high bit into DX
   xor  ax, dx  ; take 1's complement if negative; no change if positive
   sub  ax, dx  ; AX is 2's complement if it was negative The standard
                : absolute value method works on any register but is much
                ; slower:

   or   bx, bx  ; see if number is negative
   jge  notneg  ; if it is negative...
   neg  bx      ; ...make it positive
notneg:         ; jump to here if positive

(явно украдено)

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

То, что быстрее, очень зависит от того, какой компилятор и на какой процессор вы ориентируетесь. На большинстве процессоров и всех компиляторах x = (x>=0)? х:-х; это самый быстрый способ получить абсолютное значение, но на самом деле часто стандартные функции уже предлагают это решение (например, fabs()). Он скомпилирован в сравнение, за которым следует инструкция условного присваивания (CMOV), а не в условный переход. Однако на некоторых платформах эта инструкция отсутствует. Хотя компилятор Intel (но не Microsoft или GCC) автоматически конвертировал бы if() в условное присваивание и даже пытался бы оптимизировать циклы (если это возможно).

Код ветвления в целом медленнее, чем условное присваивание, если ЦП использует статистическое прогнозирование. if() может быть в среднем медленнее, если операция повторяется несколько раз, а результат условия постоянно меняется. Процессоры, такие как Intel, начнут вычислять обе ветки и отбросят недопустимую, в случае больших тел if() или большого количества циклов, которые могут быть критическими.

sqr() и sqrt() на современных процессорах Intel являются одной встроенной инструкцией и не медленны, но они неточны, и загрузка регистров также потребует времени.

Связанный с этим вопрос: Почему инструкция перехода ЦП медленная?

Скорее всего, профессор хотел, чтобы студент провел исследование по этому вопросу, это полупровокационный вопрос\задание, которое пойдет только на пользу, если студент научится самостоятельно мыслить и искать дополнительные источники.

Я занимаюсь программированием ретро-графики на C для 8088/8086, и вызов abs() занимает много времени, поэтому я заменил его на:

/* assuming 'i' is int; this WILL NOT WORK on floating point */
if (i < 0) {
    i = ~i + 1;
}

Причина, по которой это быстрее, заключается в том, что он по сути меняет CALL в сборке на JNE. Вызов метода изменяет пару регистров, помещает еще несколько, помещает аргументы в стек и может очистить очередь предварительной выборки. Плюс эти действия нужно отменять в конце функции и все это очень дорого для процессора.

Для полноты, если вы имеете дело с числами с плавающей запятой, вы всегда можете сделать что-то вроде n * sign(n), где sign — это функция, которая возвращает +1, если число положительное, и -1, если отрицательное. В C это будет что-то вроде copysign(1.0, n) или (n > 0) - (n < 0).

В настоящее время большинство машин используют IEEE 754 в качестве формата с плавающей запятой, поэтому вы можете напрямую очистить бит знака:

float fabs(float x) {
    char *c = &x;
    c[0] &= 7;
    return *(float *)c;
}

Учитывая, что функция abs, вероятно, делает именно это, лучше всего использовать ее, когда она доступна. Если повезет, функция будет состоять из пары инструкций и будет встроена.

Интересно, если что-то не так с этим решением. Там есть

• нет ветвления
• нет смещения, зависящего от разрядности
• ни капли не вертится
• нет зависимости от архитектуры
• нет зависимости от компилятора
• необязательно: нет неопределенного поведения для INT_MIN

Может слишком много инструкций?

Мое решение

xabs = (x < 0)*(-x) + (x >=0)*x

• 2 целочисленных сравнения
• 2 умножения

Старое решение

xtest = (x < 0)*x;           // xtest = x if is negative, otherwise zero
xabs = (x - xtest) - xtest;  // Order of instructions taken into account

Неопределенное поведение при отрицании INT_MIN

Можно добавить проверку на неопределенное поведение (отрицание INT_MIN), если ваше значение не было ограничено в алгоритме где-то ранее. Но это немного усложняет задачу. Может быть, кто-то найдет более простую логику.

xabs =   (x < -INT_MAX)*INT_MAX            //  x < -INT_MAX < 0  --> xabs = INT_MAX
       + ((x >= -INT_MAX)&&(x < 0))*(-x)   // -INT_MAX =< x < 0  --> xabs = -x
       + (x >= 0)*x                        // 0 <= x             --> xabs = +x

• 5 целочисленных сравнений
• 3 целочисленных умножения

К сожалению, я никогда не сравнивал скорости. Так что я не знаю, действительно ли это быстрее, чем

if ( x < 0 )
{
  if ( x >= -INT_MAX )
  {
    x = -x;
  }
  else
  {
    x = INT_MAX;
  }
}
     

Для списка отрицательных чисел:

если у вас в памяти хранится ноль, просто используйте 0 - x, где x — отрицательное число.

Или, если у вас нет нуля в памяти:

x-x-x, где x — отрицательное число.

Или, со скобками для ясности:

(x) - (x) - (x) => (-n) - (-n) - (-n), где x = -n

т. е. вычесть отрицательное число из самого себя, чтобы получить ноль, а затем вычесть его из нуля.