Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Which is the fastest way to get the absolute value of a number

Which is the fastest way to implement an operation that returns the absolute value of a number?

x=root(x²) 

or

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

Actually this question can be translated as, how fast is an if (and why please).

My college programing professors always told me to avoid ifs for they are extremely slow, but I always forgot to ask how slow and why. Does anybody here know?

like image 248
Diones Avatar asked Mar 20 '09 03:03

Diones


People also ask

What is the easiest way to find absolute value?

The absolute value of a number is the number's distance from zero, which will always be a positive value. To find the absolute value of a number, drop the negative sign if there is one to make the number positive. For example, negative 4 would become 4.

How do computers find absolute value?

To get the absolute value of a negative number, we have to toggle all bits and add 1 to the toggled number i.e, 0 0 0 0 0 0 0 1 + 1 will give the absolute value of 1 1 1 1 1 1 1 0.

How do you find the absolute value of a number in Java?

abs(int a) returns the absolute value of an int value. If the argument is not negative, the argument is returned. If the argument is negative, the negation of the argument is returned.


2 Answers

There is a great trick to calculate the absolute value of a 2s-complement integer without using an if statement. The theory goes, if the value is negative you want to toggle the bits and add one, otherwise you want to pass the bits through as is. A XOR 1 happens to toggle A and A XOR 0 happens to leave A intact. So you want do something like this:

  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 

In principle, you can do it in as few as three assembly instructions (without a branch). And you'd like to think that the abs() function that you get with math.h does it optimally.

No branches == better performance. Contrary to @paxdiablo's response above, this really matters in deep pipelines where the more branches you have in your code, the more likely you are to have your branch predictor get it wrong and have to roll-back, etc. If you avoid branching where possible, things will keep moving along at full throttle in your core :).

like image 88
vicatcu Avatar answered Sep 18 '22 02:09

vicatcu


Conditionals are slower than plain arithmetic operations, but much, much faster than something as silly as calculating the square root.

Rules of thumb from my assembly days:

  • Integer or bitwise op: 1 cycle
  • Floating-point add/sub/mul: 4 cycles
  • Floating-point div: ~30 cycles
  • Floating-point exponentiation: ~200 cycles
  • Floating-point sqrt: ~60 cycles depending on implementation
  • Conditional branch: avg. 10 cycles, better if well-predicted, much worse if mispredicted
like image 35
kquinn Avatar answered Sep 19 '22 02:09

kquinn