4
\$\begingroup\$

I've looked for a good method to generate an integer inside a range of values. I think using modulo is not a good method because the values are not perfectly mapped in the range. So I mapped the pseudo random generated number in the range by using double variables types.

What do you think about this method? I know that performance is not better when using a modulo. How would you improve the method or the performance by keeping a perfect match?

quint32 randquint32(quint32 low, quint32 high)
{
    const quint32 uint_max = 0xffffffff;

    if (low == 0 && high == 0)
    {
        high = uint_max;
        if (RAND_MAX > high)
        {
            return (qrand() & high);
        }
    }
    else if (low > high)
    {
        qSwap(low, high);
    }

    const quint8 numberOfBits = bitCount(RAND_MAX);
    quint32 myRand = 0;
    int i = qCeil(((double)32) / ((double)numberOfBits));
    while (i--)
    {
        myRand += qrand();
        if (i)
        {
            myRand <<= numberOfBits;
        }
    }

    if (low == 0 && high == uint_max)
    {
        return myRand;
    }
    if (myRand == uint_max)
    {
        return high;
    }

    const double uint_max_double = (double)uint_max;

    double range = high - low + 1;
    double tmpRand = ((double)myRand) / uint_max_double * range;
    return qFloor(tmpRand);
}

quint8 bitCount(quint32 n)
{
    quint8 count = 0;
    while (n)
    {
        if (n & 1)
        {
            count++;
        }
        n >>= 1;
    }
    return count;
}

NEW VERSION:

// count setted bits at the right of a mask
quint8 bitCountRightMask(quint64 mask)
{
    quint8 bc = 0;
    while (mask & 1)
    {
        mask >>= 1;
        bc++;
    }
    return bc;
}

const quint64 uint64_max = 0xffffffffffffffff;
const int bitCountRandMax = bitCountRightMask(RAND_MAX);

// randomise an uint64 variable
quint64 rand64()
{
    quint64 myRand = qrand();

    if (uint64_max > RAND_MAX)
    {
        int i = qCeil(64 / (double)bitCountRandMax) - 1;
        do
        {
            myRand <<= bitCountRandMax;
            myRand += rand();
        } while (i--);
    }

    return myRand;
}

// randomize an uint64 variable between low and high (fast method (modulo))
quint64 rand64(quint64 low, quint64 high)
{
    if (low == 0 && high == 0)
    {
        high = uint64_max - 1;
    }
    else if (low > high)
    {
        qSwap(low, high);
    }

    return low + (rand64() % (high - low + 1));
}

// randomize an uint64 variable between low and high (precise method (double))
quint64 prand64(quint64 low, quint64 high)
{
    if (low == 0 && high == 0)
    {
        return rand64();
    }
    else if (low > high)
    {
        qSwap(low, high);
    }

    quint64 myRand = rand64();

    if (myRand == uint64_max)
    {
        return high;
    }

    static double uint64_max_double = static_cast<double>(uint64_max);

    return low + (myRand / uint64_max_double * (high - low + 1));
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I think the initialization with std::ceil() could be this: int i = std::ceil(static_cast<double>(32 / numberOfBits)); \$\endgroup\$ – Jamal Aug 26 '13 at 14:54
  • \$\begingroup\$ Related note for the std::ceil() - change int i to double i: stackoverflow.com/questions/1253670/… \$\endgroup\$ – Jamal Aug 27 '13 at 15:18
6
\$\begingroup\$

DONT DO THIS

while (i--)
{
    myRand += rand();
    if (i)
    {
        myRand <<= numberOfBits;
    }
}

It seems like you are trying to increase the range of random numbers.
What you are doing is screwing up the distribution of the random numbers and thus making them less random. Have you tried plotting a histogram to show the distribution.

Luckily for you your system probably only has 32 bit rands and thus this is not changing anything; as the loop is only done once.

ASSUMPTION HERE

static const unsigned long uint_max = 0xffffffff;  // assuming that long is 32 bits

// long has at least 32 bits but can be larger.

Is this not the whole point of all the work to avoid this:

    if (high < RAND_MAX)
    {
        return (rand() & high);  // basically this is the same as using 
    }                            // % high. You are folding at high
                                 // unless RAND_MAX is a multiple of high
                                 // then you have an uneven distribution.

There is plenty of documentation on the web of how to do this correctly please try and find rather than re-invent something like this. Random number generation is a non trivial task and exceedingly hard to get correct. Don't mess with it unless you have a PhD in probability.

Rand done properly: https://stackoverflow.com/a/10219422/14065

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ No, 3 iterations for uint32 because of RAND_MAX = 0x7fffffff (15 random bits). No, rand() & high is not equal to rand() % high because high is a mask here, not the high value. fail in variable name... Sorry I converted the variable types but that was a bad idea. I edited the first post with the current version I use. \$\endgroup\$ – Antoine Aug 27 '13 at 15:08
  • 1
    \$\begingroup\$ @AntoineLafarge: You miss the point (and I did not say equal). It is equivalent to a & because you are folding around the top 16 bit. Those you are causing an uneven distribution. Different method same result (uneven distribution). Also don't assume RAND_MAX is any particular value. \$\endgroup\$ – Martin York Aug 27 '13 at 15:37
  • \$\begingroup\$ Ok so you say that doing a modulo operation with superfluous bits is better than just folding this bits? For the mapping I am not agree with you. But I don't know for the pseudo-random generator. You must be right. If I keep the superfluous bits for integrating it in the next random generated number. Does it change anything? And you, how would you generate an unsigned integer of 64 bits? \$\endgroup\$ – Antoine Aug 28 '13 at 7:26
  • 1
    \$\begingroup\$ @AntoineLafarge: I am saying masking and modulo are just as bad. When you do % you are folding around a base 10 number when you do & you are folding around a base 2 number. The point is you get an uneven distribution unless your fold point is an exact divisor into RAND_MAX. The solution to this is well known and I provided a link. \$\endgroup\$ – Martin York Aug 28 '13 at 8:38
  • 1
    \$\begingroup\$ I would not try and get a 64 bit rand (I am not a probability professor). I would look for an already implemented 64 bit random number generator that has been tested by people that know what they are doing. Maybe boost::random has something you can use. \$\endgroup\$ – Martin York Aug 28 '13 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.