0

I have a couple of situations where I need to clamp a floating-point number to the upper or lower end of an arbitrary[1] range. Thus far, I have been using floor and ceil functions with pre- and post-scaling, as follows:

y*floor(x/y) - x + y

y*ceil(x/y) - x - y

Where y specifies the size of the range that we're snapping to. That works, but it feels inelegant, and these calculations happen often enough to be an actual performance bottleneck. Now, it turns out that x mod y = x - y*floor(x/y), which means with a little algebra that first expression can be simplified to y - (x mod y), which is only two operations rather than five, and eliminates a multiply.

I am, however, having considerably more difficulty figuring out how to replace ceil without using branching (which would not do any good for performance). So, is there any way to re-write y*Math.ceil(x/y) that would give me opportunities for algebraic simplification, or am I just stuck with this?

[1] In case it helps, y is always an integer power of two, and the exponent is cached and available for use.

Logan R. Kearsley
  • 682
  • 1
  • 5
  • 19
  • (a) ceil(*x*) = −floor(− *x*), so any floor implementation can be made into a ceil implementation with two bit flips. (b) You mean `x - (x mod y)` rather than `y - (x mod y)` as a floor implementation. (c) Since *y* is a power of two and you have information about it cached, you could cache *r* = 1 / *y*. Then `floor` for nonnegative *x* is `truncate(x*r)*y`. That is two multiplies and a truncation to an integer, which may be faster than a division/remainder. – Eric Postpischil Apr 14 '19 at 22:32
  • @EricPostpischil re (b), I definitely mean `y`. Subbing `x - x mod y` into `y*floor(x/y) - x + y` for `y*floor(x/y)`, we get `(x - x mod y) - x + y`, which then simplifies to `y - x mod y`. But the rest of that is good info. I think using the `ceil(x) = -floor(-x)` identity, I can get down to one modulus and 3 subtractions, which is better than a division, multiply, ceil, and 2 subtractions. Thanks! – Logan R. Kearsley Apr 14 '19 at 23:07
  • 1
    You should explain what you mean by clamping to a range. For `x`=34 and `y`=10, `y*floor(x/y) - x + y` is `10*floor(34/10) - 34 + 10` = `30 - 34 + 10` = `6`, which does not seem to be the endpoint of anything defined by `x` or `y`. – Eric Postpischil Apr 14 '19 at 23:15
  • @EricPostpischil The clamping part is just the leading `y*floor(x/y)` or `y*ceil(x/y)`--it snaps the value to a multiple of `y`--i.e., to the endpoints of a range of arbitrary size--rather than to a multiple of 1. The other additions and subtracts give you the distance from the value of `x` to the next snapping point, either up or down, and are included for context as they may cancel with other terms, which may change the suitability of certain possible substitutions compared to what the optimal substitutions would be in isolation. – Logan R. Kearsley Apr 15 '19 at 00:10
  • This is not clamping, which clamps a value to the range's limits when it's outside that range, A.K.A saturated math. There are various functions in C++ for that like [`std::clamp()`](https://en.cppreference.com/w/cpp/algorithm/clamp). [Most efficient/elegant way to clip a number?](https://stackoverflow.com/q/9323903/995714). You just want to map x to 2 values between -y and y instead of setting x to -y if x < -y and y if x > y – phuclv Apr 15 '19 at 00:42
  • 1
    Your first expression is the amount to add to `x` to increase it to the next higher multiple of `y`, and your second expression is the amount to add to decrease `x` to the next lower multiple of `y`. As you note, the first is `y - x mod y`, where “mod” is the value in [0, y) that is congruent to x modulo y (assuming positive `y`). Then the second would be `-x mod y - y`. In general, no more reduction is available, as “remainder” is a pretty elementary operation. However, given that `y` is a power of two, some improvement might be possible, as I noted with the reciprocal and truncation. – Eric Postpischil Apr 15 '19 at 01:44

0 Answers0