Jump to content
  • Advertisement
Sign in to follow this  
isbinil

Make this small algorithm branchless ?

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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);
   // ...do your other computation
}

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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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

zero can be added

 

-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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!