Clip random integer to a range of values without using division/modulo

Question

This can done this way:

int clamp(int rnd, int min, int max)
{
    return min + rnd % (max - min + 1);
}

Can this be done without using division? Returned value doesn't necessarily have to match, however, uniform distribution has to be preserved.

rnd, min, and max are arbitrary integers. rnd in my case is a random integer.

One possible solution is to convert to double in range of [0...1) using std::ldexp and then multiply, but I'd like to know if there is a simpler solution that doesn't involve floats and/or division.

Are you trying to a uniform int distribution with some given min and max? If yes, then see https://stackoverflow.com/a/19728404/3033441 — lakshayg, Jul 21 '18 at 03:21
If you can ensure that (max-min+1) is a perfect power of 2 then you can use `return min + rnd & (max - min)` because `n % pow(2, k) = n & (pow(2, k)-1)` — lakshayg, Jul 21 '18 at 03:25
@LakshayGarg I updated the question. `min` and `max` are arbitrary, and I specified that uniformity has to be preserved, eg I cannot simply select some range of bits. — Pavel P, Jul 21 '18 at 03:49
What about range of rnd? If that one is a power of 2 (say it's a full range of int), you can use shift instead of division — isp-zax, Jul 21 '18 at 03:50
@LakshayGarg Seems like `uniform_int_distribution` "asks" rnd generator for a number in range of `[0... max - min + 1]` (at least that's what MS stdc++ lib does) — Pavel P, Jul 21 '18 at 03:54
@isp-zax yes, rnd is full range 32 bits. How would shifting help? Shifting would work if the `[min... max]` range was `(X^2) -1` — Pavel P, Jul 21 '18 at 03:56
Well, int is 16 bit and signed, not 32, but if your int is long, you can use (long long) cast instead of long, shift by 32 and scale like this min + (((long)max-(long)min) * (long)rnd)>>16 which effectively scales rnd to 0..1 and the value to min..max — isp-zax, Jul 21 '18 at 04:00
@isp-zax int is 32 bits. I don't care what standard requires/guarantees, I care what's on practice. I updated my question with possible solution, I think what you mentioned should be similar but with fixed points and most likely should work. — Pavel P, Jul 21 '18 at 04:03

score 2 · Accepted Answer · edited Jul 21 '18 at 04:10

If as per comment you have a 32 bit int and rnd input uniformly distributed between -2^31 and 2^31 you can calculate your output as min + ((((long long)max-(long long)min) * (unsigned long)rnd))>>32 which effectively scales rnd to 0..1 and the value to min..max. Since you wrote you don't care about standards, I wasn't to particular about signed/unsigned conversion practices and warnings. Just gave a general idea - first multiply then shift instead of division.

int clamp(uint32_t rnd, int min, int max)
{
    return min + (1ull*rnd*(max - min + 1)) >> 32;
}

Clip random integer to a range of values without using division/modulo

1 Answers1