• 10
• 9
• 12
• 14
• 14

# Make this small algorithm branchless ?

This topic is 599 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello,

I need to move an object position by an X amount (floating point value) step by step, by maximum 1 pixel increments. For example if X=3.2, i need to move by 1, 1, 1 then 0.2.

X can be negative so -2.4 would do -1,-1 then -0.4.

I made the following algo :

#define sign(x) ((x > 0) - (x < 0)) // returns 1 if x positive, -1 if x negative

double X = 3.2;

for (int i = 0; i < ceil(fabs(X)); i++){

if (fabs(X)-i >= 1) // increments by 1 or -1
position += sign(X);
else // finally add the floating part of X
position += X-i*sign(X);

}

It works well, but is there any way to optimize it ? I'd like to do it without branches in a single line, but i can't find the right way to proceed.

Any help is welcome :)

Edited by isbinil

##### Share on other sites

What about using the loop with the floored value, then always doing the else part after the loop? I would worry more about calling functions more often than needed than the branch though..?

##### Share on other sites

In fact i have some other code in the loop that needs the new position value, so i can't put something outside. But you're probably right, i won't really matters performance-wise. I was just searching for a more "elegant" solution

##### Share on other sites
#define sign(x) ((x > 0) - (x < 0)) // returns 1 if x positive, -1 if x negative

double X = 3.2;
double oX = fabs(X);
int signage = sign(X);
while (oX > 1.0)
{
oX = oX - 1.0;
}
oX = (double)signage * oX;

Edited by Alpheus

##### Share on other sites

Meta-approach: run a profiler on it. I'm a bit dubious this is worth optimizing unless you're doing it millions of times per frame, but if that's actually a concern you should be profiling and testing to see the actual effects in conjunction with the compiler optimizations.

For the algorithm itself:

while (position < position + X) {
position += std::clamp(X, -1.0, 1.0);
}


or min(max(X, 1.0), -1.0).

##### Share on other sites

#define sign(x) ((x > 0) - (x < 0)) // returns 1 if x positive, -1 if x negative

double X = 3.2;

for (int i = 0; i < ceil(fabs(X)); i++){
/*
if (fabs(X)-i >= 1) // increments by 1 or -1
position += sign(X);
else // finally add the floating part of X
position += X-i*sign(X);

*/

position  +=    (sign(fabs(X)-i -1)+1)*0.5 * (sign(X))  +   (sign(fabs(X)-i -1)-1)*-0.5 * (X-i*sign(X));

}

Your sign macro should return 1 for zero, zero is considered a positive number, it will return 0 for zero.

Edited by JohnnyCode

##### Share on other sites
Your sign macro should return 1 for zero, zero is considered a positive number, it will return 0 for zero.

That completely depends on which definition is most useful for your purpose. Zero is not considered a positive number; in fact, mathematicians commonly use non-negative to talk about all positive numbers and zero. Mathematically you can use whatever convention fits your use case for sign(0). Float/double even has +0 and -0!

##### Share on other sites

Zero is not considered a positive number; in fact, mathematicians commonly use non-negative to talk about all positive numbers and zero. Mathematically you can use whatever convention fits your use case for sign(0). Float/double even has +0 and -0!

Though it depends on mechanics of yours which one to pick realy, floating point format +0/-0 is purely technical and has no algebraic pattern.

Since you cannot pick negative for zero, it makes sanse to pick positive in 1 bit informational space, what "a sign" should be (there are only two signs).

##### Share on other sites

Since you cannot pick negative for zero, it makes sanse to pick positive in 1 bit informational space, what "a sign" should be (there are only two signs).

sign(0) = 1 makes as much sense as sign(0) = -1. The most common choice, sign(0) = 0, is very useful for cases where you want logic to branch on positive or negative numbers, but not on 0. sign(0) is undefined in a mathematical sense, so the sign of 0 is 100% up to preference -- mathematicians choose 0 most of the time.

@OP: Notice that your else condition is run exactly once: in the last iteration of your loop. You can move the condition fabs(X) >= 1 into the loop condition and move the else part out of your loop. It probably won't make any difference as the branch is extremely predictable anyways.

##### Share on other sites
sign(0) = 1 makes as much sense as sign(0) = -1

Zero is not considered a positive number; in fact, mathematicians commonly use non-negative to talk about all positive

Do not confuse mathematical syntax culture in math analysis, such as limits +0,-0 as for aproach of direction. Again, from algebraic point of view,

zero can be subtracted

-0=+0 would break math if they were a different number .

thus yes, you cannot determine a sign of zero (3 bit system), but in a two bit system (one of the signs) - it has to be positive. Negative literaly means lowering, a neutral/ positive means the postive result then negative (persevarence as well advance).

We went off topic.

Since you cannot pick negative for zero, it makes sanse to pick positive in 1 bit informational space, what "a sign" should be (there are only two signs).

That has been my point that would have healed the issue of OP (not escaping to instruction stack, on cost of two multiplications in registers )

Edited by JohnnyCode