Wrap value into range [min,max] without division

Question

Is there any way in C# to wrap a given value x between x_min and x_max. The value should not be clamped as in Math.Min/Max but wrapped like a float modulus.

A way to implement this would be:

x = x - (x_max - x_min) * floor( x / (x_max - x_min));

However, I am wondering if there is an algorithm or C# method that implements the same functionality without divisions and without the likely float-limited-precision issues that may arise when the value lies far away from the desired range.

Answer 1

You can wrap it using two modulo operations, which is still equivalent to a division. I don't think there is a more efficient way of doing this without assuming something about x.

x = (((x - x_min) % (x_max - x_min)) + (x_max - x_min)) % (x_max - x_min) + x_min;

The additional sum and modulo in the formula are to handle those cases where x is actually less than x_min and the modulo might come up negative. Or you could do this with an if, and a single modular division:

if (x < x_min)
    x = x_max - (x_min - x) % (x_max - x_min);
else
    x = x_min + (x - x_min) % (x_max - x_min);

Unless x is not far from x_min and x_max, and is reachable with very few sums or subtractions (think also error propagation), I think the modulo is your only available method.

Without division

Keeping in mind that error propagation might become relevant, we can do this with a cycle:

d = x_max - x_min;
if (abs(d) < MINIMUM_PRECISION) {
    return x_min; // Actually a divide by zero error :-)
}
while (x < x_min) {
    x += d;
}
while (x > x_max) {
    x -= d;
}

Note on probabilities

The use of modular arithmetic has some statistical implications (floating point arithmetic also would have different ones).

For example say we wrap a random value between 0 and 5 included (e.g. a six-sided dice result) into a [0,1] range (i.e. a coin flip). Then

0 -> 0      1 -> 1
2 -> 0      3 -> 1
4 -> 0      5 -> 1

if the input has flat spectrum, i.e., every number (0-5) has 1/6 probability, the output will also be flat, and each item will have 3/6 = 50% probability.

But if we had a five-sided dice (0-4), or if we had a random number between 0 and 32767 and wanted to reduce it in the (0, 99) range to get a percentage, the output would not be flat, and some number would be slightly (or not so slightly) more likely than others. In the five-sided dice to coin-flip case, heads vs. tails would be 60%-40%. In the 32767-to-percent case, percentages below 67 would be CEIL(32767/100)/FLOOR(32767/100) = 0.3% more likely to come up than the others.

(To see this more clearly, consider the number to be from "00000" to "32767": once every 328 throws, the first three digits of the number will be "327". When this happens, the last two digits can only go from "00" to "67", they cannot be "68" to "99" because 32768 is out of range. So, digits from 00 to 67 are slightly more likely.

So, if one wanted a flat output, one would have to ensure that (max-min) was a divisor of the input range. In the case of 32767 and 100, the input range would have to be truncated at the nearest hundred (minus one), 32699, so that (0-32699) contained 32700 outcomes. Whenever the input was >= 32700, the input function would have to be called again to obtain a new value:

function reduced() {
#ifdef RECURSIVE
    int x = get_random();
    if (x > MAX_ALLOWED) {
        return reduced(); // Retry
    }
#else
    for (;;) {
        int x = get_random();
        int d = x_max - x_min;
        if (x > MAX_ALLOWED) {
            continue; // Retry
        }
    }
#endif
    return x_min + (
             (
               (x - x_min) % d
             ) + d
           ) % d;

When (INPUTRANGE%OUTPUTRANGE)/(INPUTRANGE) is significant, the overhead might be considerable (e.g. reducing 0-197 to 0-99 requires making roughly twice as many calls).

If the input range is less than the output range (e.g. we have a coin flipper and we want to make a dice tosser), multiply (do not add) using Horner's algorithm as many times as required to get an input range which is larger. Coin flip has a range of 2, CEIL(LN(OUTPUTRANGE)/LN(INPUTRANGE)) is 3, so we need three multiplications:

for (;;) {
    x = ( flip() * 2 + flip() ) * 2 + flip();
    if (x < 6) {
        break;
    }
}

or to get a number between 122 and 221 (range=100) out of a dice tosser:

for (;;) {
    // ROUNDS = 1 + FLOOR(LN(OUTPUTRANGE)/LN(INPUTRANGE)) and can be hardwired
    // INPUTRANGE is 6
    // x = 0; for (i = 0; i < ROUNDS; i++) { x = 6*x + dice();  }
    x = dice() + 6 * ( 
            dice() + 6 * ( 
                dice() /* + 6*... */
            )
        );
    if (x < 200) {
        break;
    }
}
// x is now 0..199, x/2 is 0..99
y = 122 + x/2;

Answer 2

Are min and max fixed values? If so, you could figure out their range and the inverse of that in advance:

const decimal x_min = 5.6m;
const decimal x_max = 8.9m;
const decimal x_range = x_max - x_min;
const decimal x_range_inv = 1 / x_range;

public static decimal WrapValue(decimal x)
{
    return x - x_range * floor(x * x_range_inv);
}

The multiplication should perform somewhat better than division.