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

Question

Какой самый быстрый способ реализовать операцию, которая возвращает абсолютное значение числа?

x=root(x²)

или

if !isPositive(x):
    x=x*(-1)

На самом деле этот вопрос можно перевести как, как быстро if (и почему, пожалуйста).

Мои профессора по программированию в колледже всегда говорили мне избегать if s, потому что они чрезвычайно медленные, но я всегда забывал спросить, как медленно и почему. Кто-нибудь здесь знает?

Answer 1

Есть отличный способ вычислить абсолютное значение целого числа с дополнением 2s без использования оператора 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, приведенному выше, это действительно имеет значение для глубоких конвейеров, где чем больше веток в вашем коде, тем выше вероятность того, что ваш предиктор ветвления ошибется и придется выполнить откат и т. Д. возможно, в вашем ядре все будет двигаться полным ходом:).

Answer 2

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

Правила большого пальца из моих дней сборки:

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

Answer 3

Тьфу, твои учителя на самом деле сказали тебе это? Правило, которому следует большинство людей, - сначала сделать ваш код читабельным, а затем подправить любые проблемы с производительностью после того, как они действительно окажутся проблемами. использовал слишком много операторов if. Кнут сказал, что лучше , «преждевременная оптимизация - корень всего зла».

Answer 4

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

(x >= 0) ? x : -x

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

Answer 5

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

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

Answer 6

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

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

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

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

Answer 7

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

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

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

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

Answer 8

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

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

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

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

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

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

Answer 9

Вы используете сборку 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

(вопиюще украдено )

Answer 10

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

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