Is there a branchless way to move number towards another number without exceeding it?

Question

I want to implement a function conforming to the following interface and contract:

void move_towards(float& value, float target, float step) 
    // Moves `value` towards `target` by `step`. 
    // `value` will never go beyond `target`, but can match it.
    // If `step == 0.0f`, `value` is unchanged.
    // If `step > 0.0f`, `std::abs(target - value)` decreases.
    // If `step < 0.0f`, the behavior is undefined.

The idea is to use this function to gradually move an existing floating point value towards another, without ever exceeding the target. This is useful - for example - to perform linear transitions between values as part of the execution of a game loop.

Here's an example test case:

float value = 5.0f;
move_towards(value,  10.f,  1.f); assert(value ==  6.0f);
move_towards(value,  10.f,  1.f); assert(value ==  7.0f);
move_towards(value, -5.f,   5.f); assert(value ==  2.0f);
move_towards(value, -5.f,   5.f); assert(value == -3.0f);
move_towards(value, -5.f,   5.f); assert(value == -5.0f);
move_towards(value, -5.f,   5.f); assert(value == -5.0f);
move_towards(value,  0.f,  15.f); assert(value ==  0.0f);

I tried a few branchless ideas using a combination of std::copysign and std::clamp, but they always failed in some edge cases. In the end, I resorted to using a branchy version:

void move_towards(float& value, float target, float step) 
{
    if (value < target)
    {
        value += step;
        if (value > target)
        {
            value = target;
        }
    }
    else if (value > target)
    {
        value -= step;
        if (value < target)
        {
            value = target;
        }
    }
}

live on godbolt.org

• Is it possible to implement move_towards in order to produce branchless instructions?
• If not, is it possible to at least minimize the number of branches?
• Regardless, what version provides the best run-time performance?

Answer 1

I think this is the approach that Francois Andrieux was hinting at. Have you tried this? It's just one branch.

void move_towards(float& value, float target, float step) {
    value = target < value 
        ? std::max(value - step, target)
        : std::min(value + step, target);
}

https://godbolt.org/z/jxKP6oT1h

Answer 2

You can do this completely branch-free, if you have a reasonably modern processor target (with branch-free selection from two floating-point values).

The approach would be to formulate the problem as follows:

Compute a "signed step" value that is either +step or -step, depending on whether target > value or target < value. Find the median of target, value and value + signed step. Finding the median can be done by sorting, but for three elements you can also just combine the elements with an invertible operation and apply the inverted operation on the combination with the maximum and minimum of the three values. For float, invertible operations are a bit of a problem, because addition/subtraction are not associative. However, in your comments you said that you do not care about the case where the target and value have extremely different magnitudes, so addition and subtraction work decently well. A better solution would bitwise convert to an unsigned integer type of the same width, then use xor as the invertible operation, then convert the median bit pattern back to float.

Here's the solution on godbolt, and in the answer:

void move_towards(float& value, float target, float step) {
    auto sstep = (target > value ? step : -step);
    auto nval = value + sstep;
    value = value + target + nval -
        std::min(std::min(value, target), nval) -
        std::max(std::max(value, target), nval);
}

Answer 3

any branchless version?

Use the sign of target - value to select a function by index.

float move_towards(float value, float target, float step) {
  static float (*f[2])(float a, float b) = {fminf, fmaxf};
  float diff = target - value;
  bool index = signbit(diff);
  step = copysignf(step, 0 - index);
  return f[index](target, value + step);
}

Code is a C solution. Leave it to OP to translate to C++ as needed.

Answer 4

The desired result is the median of value - step, value + step, and target, so this works:

void move_towards(float &value, float target, float step) 
{
    value = std::max(value - step, std::min(value + step, target));
}

To see this, consider the cases where target lies below, between, or above value - step and value + step:

• If target ≤ value - step < value + step, then value can take a full step down toward target, so we want value - step.
• If value - step < target < value + step, then value cannot take a full step toward target (which might be in either direction), so we want target.
• If value - step < value + step ≤ target, then value can take a full step up toward target, so we want value + step.

In each case, we want the middle value.

Testing shows GCC generates two instructions fewer if we swap the std::max operands, likely just because it works better with where the operands happen to be in registers:

void move_towards(float &value, float target, float step) 
{
    value = std::max(std::min(value + step, target), value - step);
}