Generate random int with specified upper-bound (0

问题:

roommate went to an interview and got this one:

Rules:

permitted to use rand();

RAND_MAX = 32 767;

no use of division or modulo;

TODO: Write a function that takes one int parameter and returns int in range 0 - parameter.

Head hurts, can't sleep. Any help appreciated. Thanks

回答1:

In my public domain randlib, I do it with no floating point, no division, no multiplication, just bitmasking and rejection sampling, like this:

int ojr_rand(ojr_generator *g, int limit) {
    int v, m = limit - 1;

    m |= m >> 1;
    m |= m >> 2;
    m |= m >> 4;
    m |= m >> 8; // m is smallest ((power of 2) - 1) > limit

    do {
            v = m & NEXT16(g);  // 16-bit random number
    } while (v >= limit);
    return v;
}

In the worst case (limit is power of two plus one), this can reject close to 50% of the generated numbers, but it's still faster than division or floating math with most fast RNGs, and in the general case it's much faster. Also, unlike the floating point math or mod, it is exact, meaning if you ask for a limit of 3, you get values 0, 1, and 2 with exactly equal probability, not just approximately equal.

回答2:

Few possibilities:

• the range transposition approach: int r = rand() * 0.00003051855095 * n;

• the "shuffle sort" approach: int r; do { r = random(); } while (r >= n);

• the BSD approach: uint32_t r = arc4random_uniform(n);

Etc., etc., etc.

回答3:

If c++11 is allowed there is a random header provided that makes this trivial:

#include <random>
#include <iostream>

int Roll(int Max)
{
    if(Max>32767)
        Max=32767;
    std::random_device generator;
    std::uniform_int_distribution<int> distribution(0,Max);
    return distribution(generator);   
}


int main()
{
    std::cout << Roll(10) << std::endl
              << Roll(10) << std::endl
              << Roll(999999) << std::endl;
}

More details at: http://en.cppreference.com/w/cpp/numeric/random

This presumes that RAND_MAX is provided by your problem and not by the C standard of course you could use the provided constant, for details see: http://en.cppreference.com/w/cpp/numeric/random/RAND_MAX

回答4:

do { r = random();} while (r >= max_rand);

At first I thought multiplying by a fraction would work but that could be considered cheating from a mathematical standpoint.

回答5:

int getRand(int max)
{
    int val = rand();

    while (val > max)
    {
        val -= max + 1;
    }

    return val;
}

This will obviously be off slightly by counting values <= RAND_MAX % max once more than everything else but rand() % max has the same problem so I assume this error to be acceptable (for values of max << MAX_RAND the error is insignificant).