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

For the very specific case of range 0..1 this seems to work:

float wrap(float n) {
    if (n > 1.0) {
        return n - floor(n);
    }
    if (n < 0.0) {
        return n + ceil(abs(n));
    }
    return n;
}

Answer 3

If you're able to add the constraint of a min value of 0, simplifying LSerni's answer above is: x = ((x % x_max) + x_max) % x_max

The first x % x_max operation will always be negative when x is less than the 0 min value. This allows the second modulus operation of that simplification to be replaced with a less than 0 comparison.

float wrap0MinValue(float x, float x_max)
{
    int result = toWrap % maxValue;
    if (result < 0) // set negative result back into positive range
        result = maxValue + result;
    return result;
}

Answer 4

LinqPad SAMPLE CODE (Restricted to 3 decimal places)

void Main()
{ 
    Test(int.MinValue, 0, 1,0.1f, "value = int.MinValue");
    Test(int.MinValue, -2,- 1,0.1f, "value = int.MinValue");
    Test(int.MaxValue, 0, 1,0.1f, "value = int.MaxValue");
    Test(int.MaxValue, -2,- 1,0.1f, "value = int.MaxValue");
    Test(-2,-2,-1,0.1f, string.Empty);
    Test(0,0,1,0.1f, string.Empty);
    Test(1,1,2,0.1f, string.Empty);

    Test(int.MinValue, 0, 1, -0.1f, "value = int.MinValue");
    Test(int.MinValue, -2,- 1, -0.1f, "value = int.MinValue");
    Test(int.MaxValue, 0, 1, -0.1f, "value = int.MaxValue");
    Test(int.MaxValue, -2,- 1, -0.1f, "value = int.MaxValue");
    Test(-2,-2,-1, -0.1f, string.Empty);
    Test(0,0,1, -0.1f, string.Empty);
    Test(1,1,2, -0.1f, string.Empty);
}

private void Test(float value, float min ,float max, float direction, string comment)
{
    "".Dump("    " + min + " to " + max + " direction = " + direction + "   " + comment);
    for (int i = 0; i < 11; i++)
    {
        value = (float)Math.Round(min + ((value - min) % (max - min)), 3); 
        string.Format("    {1} -> value: {0}", value,  i).Dump(); 
        value = value + direction < min && direction < 0 ? max + direction : value + direction;
    }
} 

RESULTS

0 to 1 direction = 0.1   value = int.MinValue

0 -> value: 0
1 -> value: 0.1
2 -> value: 0.2
3 -> value: 0.3
4 -> value: 0.4
5 -> value: 0.5
6 -> value: 0.6
7 -> value: 0.7
8 -> value: 0.8
9 -> value: 0.9
10 -> value: 0

-2 to -1 direction = 0.1   value = int.MinValue

0 -> value: -2
1 -> value: -1.9
2 -> value: -1.8
3 -> value: -1.7
4 -> value: -1.6
5 -> value: -1.5
6 -> value: -1.4
7 -> value: -1.3
8 -> value: -1.2
9 -> value: -1.1
10 -> value: -2

0 to 1 direction = 0.1   value = int.MaxValue

0 -> value: 0
1 -> value: 0.1
2 -> value: 0.2
3 -> value: 0.3
4 -> value: 0.4
5 -> value: 0.5
6 -> value: 0.6
7 -> value: 0.7
8 -> value: 0.8
9 -> value: 0.9
10 -> value: 0

-2 to -1 direction = 0.1   value = int.MaxValue

0 -> value: -2
1 -> value: -1.9
2 -> value: -1.8
3 -> value: -1.7
4 -> value: -1.6
5 -> value: -1.5
6 -> value: -1.4
7 -> value: -1.3
8 -> value: -1.2
9 -> value: -1.1
10 -> value: -2

-2 to -1 direction = 0.1   

0 -> value: -2
1 -> value: -1.9
2 -> value: -1.8
3 -> value: -1.7
4 -> value: -1.6
5 -> value: -1.5
6 -> value: -1.4
7 -> value: -1.3
8 -> value: -1.2
9 -> value: -1.1
10 -> value: -2

0 to 1 direction = 0.1   

0 -> value: 0
1 -> value: 0.1
2 -> value: 0.2
3 -> value: 0.3
4 -> value: 0.4
5 -> value: 0.5
6 -> value: 0.6
7 -> value: 0.7
8 -> value: 0.8
9 -> value: 0.9
10 -> value: 0

1 to 2 direction = 0.1   

0 -> value: 1
1 -> value: 1.1
2 -> value: 1.2
3 -> value: 1.3
4 -> value: 1.4
5 -> value: 1.5
6 -> value: 1.6
7 -> value: 1.7
8 -> value: 1.8
9 -> value: 1.9
10 -> value: 1

0 to 1 direction = -0.1   value = int.MinValue

0 -> value: 0
1 -> value: 0.9
2 -> value: 0.8
3 -> value: 0.7
4 -> value: 0.6
5 -> value: 0.5
6 -> value: 0.4
7 -> value: 0.3
8 -> value: 0.2
9 -> value: 0.1
10 -> value: 0

-2 to -1 direction = -0.1   value = int.MinValue

0 -> value: -2
1 -> value: -1.1
2 -> value: -1.2
3 -> value: -1.3
4 -> value: -1.4
5 -> value: -1.5
6 -> value: -1.6
7 -> value: -1.7
8 -> value: -1.8
9 -> value: -1.9
10 -> value: -2

0 to 1 direction = -0.1   value = int.MaxValue

0 -> value: 0
1 -> value: 0.9
2 -> value: 0.8
3 -> value: 0.7
4 -> value: 0.6
5 -> value: 0.5
6 -> value: 0.4
7 -> value: 0.3
8 -> value: 0.2
9 -> value: 0.1
10 -> value: 0

-2 to -1 direction = -0.1   value = int.MaxValue

0 -> value: -2
1 -> value: -1.1
2 -> value: -1.2
3 -> value: -1.3
4 -> value: -1.4
5 -> value: -1.5
6 -> value: -1.6
7 -> value: -1.7
8 -> value: -1.8
9 -> value: -1.9
10 -> value: -2

-2 to -1 direction = -0.1   

0 -> value: -2
1 -> value: -1.1
2 -> value: -1.2
3 -> value: -1.3
4 -> value: -1.4
5 -> value: -1.5
6 -> value: -1.6
7 -> value: -1.7
8 -> value: -1.8
9 -> value: -1.9
10 -> value: -2

0 to 1 direction = -0.1   

0 -> value: 0
1 -> value: 0.9
2 -> value: 0.8
3 -> value: 0.7
4 -> value: 0.6
5 -> value: 0.5
6 -> value: 0.4
7 -> value: 0.3
8 -> value: 0.2
9 -> value: 0.1
10 -> value: 0

1 to 2 direction = -0.1   

0 -> value: 1
1 -> value: 1.9
2 -> value: 1.8
3 -> value: 1.7
4 -> value: 1.6
5 -> value: 1.5
6 -> value: 1.4
7 -> value: 1.3
8 -> value: 1.2
9 -> value: 1.1
10 -> value: 1

Answer 5

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.

Answer 6

use Wouter de Kort's answer but change

if (value.CompareTo(max) > 0) return max;

to

if (value.CompareTo(max) > 0) return min;

Answer 7

Modulo works fine on floating point, so how about:

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

It's still effectively a divide though, and you need to tweak it for values less < min...

You are worrying about accuracy when the number is far away from the range. However this is not related to the modulo operation, however it is performed, but is a property of floating point. If you take a number between 0 and 1, and you add a large constant to it, say to bring it into the range 100 to 101, it will lose some precision.

Answer 8

x = x<x_min?  x_min:
    x>x_max?  x_max:x;

Its a little convoluted, and you can definitely break it into a pair of if statements.. But I don't see the need for division to begin with.

Edit:

I seem to have missunderstood, le

x = x<x_min?  x_max - (x_min - x):
    x>x_max?  x_min + (x - x_max):x;

This would work if your value of x does not vary too much.. which might work depending on the use case. Else for a more robust version I expect you need divide or repeated (recursive?) subtraction atleast.

This should be a more robust version which keeps performing the above calculation until x is stable.

int x = ?, oldx = x+1; // random init value.

while(x != oldx){
    oldx = x;
    x = x<x_min?  x_max - (x_min - x):
        x>x_max?  x_min + (x - x_max):x;
}

Answer 9

How about using an extension method on IComparable.

public static class LimitExtension
{
    public static T Limit<T>(this T value, T min, T max)
         where T : IComparable
    {
        if (value.CompareTo(min) < 0) return min;
        if (value.CompareTo(max) > 0) return max;

        return value;
    }
}

And a unit test:

public class LimitTest
{
    [Fact]
    public void Test()
    {
        int number = 3;

        Assert.Equal(3, number.Limit(0, 4));
        Assert.Equal(4, number.Limit(4, 6));
        Assert.Equal(1, number.Limit(0, 1));

    }
}