How Does Modulus and Rand() Work

How does modulus and rand() work?

If C++11 is an option then you should use the random header and uniform_int_distrubution. As James pointed out in the comments using rand and % has a lot of issues including a biased distribution:

#include <iostream>
#include <random>

int main()
{
    std::random_device rd;

    std::mt19937 e2(rd());

    std::uniform_int_distribution<int> dist(6, 12);

    for (int n = 0; n < 10; ++n) {
            std::cout << dist(e2) << ", " ;
    }
    std::cout << std::endl ;
}

if you have to use rand then this should do:

rand() % 7 + 6

Update

A better method using rand would be as follows:

6 + rand() / (RAND_MAX / (12 - 6 + 1) + 1)

I obtained this from the C FAQ and it is explained How can I get random integers in a certain range? question.

Update 2

Boost is also an option:

#include <iostream>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int_distribution.hpp>

int main()
{
  boost::random::mt19937 gen;
  boost::random::uniform_int_distribution<> dist(6, 12);

  for (int n = 0; n < 10; ++n) {
    std::cout << dist(gen) << ", ";
  }
  std::cout << std::endl ;
}

Why do people say there is modulo bias when using a random number generator?

So rand() is a pseudo-random number generator which chooses a natural number between 0 and RAND_MAX, which is a constant defined in cstdlib (see this article for a general overview on rand()).

Now what happens if you want to generate a random number between say 0 and 2? For the sake of explanation, let's say RAND_MAX is 10 and I decide to generate a random number between 0 and 2 by calling rand()%3. However, rand()%3 does not produce the numbers between 0 and 2 with equal probability!

When rand() returns 0, 3, 6, or 9, rand()%3 == 0. Therefore, P(0) = 4/11

When rand() returns 1, 4, 7, or 10, rand()%3 == 1. Therefore, P(1) = 4/11

When rand() returns 2, 5, or 8, rand()%3 == 2. Therefore, P(2) = 3/11

This does not generate the numbers between 0 and 2 with equal probability. Of course for small ranges this might not be the biggest issue but for a larger range this could skew the distribution, biasing the smaller numbers.

So when does rand()%n return a range of numbers from 0 to n-1 with equal probability? When RAND_MAX%n == n - 1. In this case, along with our earlier assumption rand() does return a number between 0 and RAND_MAX with equal probability, the modulo classes of n would also be equally distributed.

So how do we solve this problem? A crude way is to keep generating random numbers until you get a number in your desired range:

int x; 
do {
    x = rand();
} while (x >= n);

but that's inefficient for low values of n, since you only have a n/RAND_MAX chance of getting a value in your range, and so you'll need to perform RAND_MAX/n calls to rand() on average.

A more efficient formula approach would be to take some large range with a length divisible by n, like RAND_MAX - RAND_MAX % n, keep generating random numbers until you get one that lies in the range, and then take the modulus:

int x;

do {
    x = rand();
} while (x >= (RAND_MAX - RAND_MAX % n));

x %= n;

For small values of n, this will rarely require more than one call to rand().

---

Works cited and further reading:

• CPlusPlus Reference

• Eternally Confuzzled

---

rand() function in c++

The modulo (remainder) of division by n > 0 is always in the range [0, n); that's a basic property of modular arithmetic.

a + rand() % n does not return a number in the range [0, n) unless a=0; it returns an int in the range [a, n + a).

Note that this trick does not in general return uniformly distributed integers.

rand() not giving random numbers depending on modulo in xcode

I noticed the same behavior with the code shown in the question:

rand() % 7    // always shows 6
rand() % 14   // always shows 6 or 13
rand() % 21   // always shows 6, 13, or 20

The problem is peculiar and there seems to be a pattern involved. Based on the comments that some aren't able to reproduce it, I decided to compile the code, with gcc on a Linux based machine and clang on macOS; Linux seems to behave normally from what I can tell, however macOS does not. I even tried completely different code just make sure it wasn't something else, yet got the same result.

#include <cstdlib>
#include <iostream>
#include <ctime>

int main() 
{
    int min = 1;
    int max = 7;

    std::srand(std::time(0)); // use current time as seed for random generator
    // int random_variable = std::rand() % max; // always returns 6
    // int random_variable = std::rand() % (max - min) + min; // produces 'predictable' numbers based on the time.
    int random_variable = RAND_MAX % std::rand() % (max-min) + min; // also returns predicate results based on the timing, except in reverse.

    std::cout << "Random value on [0 " << RAND_MAX << "]: " 
              << random_variable << '\n';
}

The only way I was able to get seemingly random results from rand() was to do:

RAND_MAX % std::rand() % (max-min) + min; // predictable based on timing

The issue is odd, and might be a bug with Clang; I'm at a loss at to what exactly is at play here. I would probably recommend using something other than rand() such as the <random> library mentioned in the comments perhaps.

EDIT: After reporting this bug to Apple this was the response:

Apple Developer Relations July 27 2017, 11:27 AM

There are no plans to address this based on the following:

std::rand directly uses rand from the C library. rand is known and
documented to be broken (and is not going to change since people
depend on its specific behavior).

From the man page: RAND(3) BSD Library Functions Manual

NAME
rand, rand_r, srand, sranddev -- bad random number generator

DESCRIPTION
These interfaces are obsoleted by arc4random(3).

For good pseudorandom numbers in C++, look at from C++11.
E.g.: http://en.cppreference.com/w/cpp/numeric/random

Based on this information RAND() is broken and won't be fixed — use an alternative random number generator.

Does using a modulus with rand() limit results?

No. You are only using the result of the rand() function, so it has absolutely no effect on the output of the PRNG. Only if you used rand()%40 to successively seed the PRNG would you run into that limit.

Also, note that a PRNG is typically only seeded from the system clock once, at its initialization. From there on, each number "depends" on the previously outputted one.

Finally, be aware that using a modulus on the output of a PRNG will in almost all cases skew the resulting probability distribution. This effect is very very small, for small modulus, but may be important to consider, depending on your application.

c++ rand() modulo floating point numbers

Using the C++11 <random> solution could look something like this:

#include <random>
#include <iostream>

int main()
{
    const int length = 60;
    std::random_device rd;
    std::mt19937_64 mt(rd());
    std::uniform_real_distribution<double> distribution(0, M_PI/12);
    for(int i = 0; i < length; i++)
    {
        double d = distribution(mt);
    std::cout << "d = " << d << std::endl;
    }
}

Uniformity of random numbers taken modulo N

You are correct, rand() % N is not precisely uniformly distributed. Precisely how much that matters depends on the range of numbers you want and the degree of randomness you want, but if you want enough randomness that you'd even care about it you don't want to use rand() anyway. Get a real random number generator.

That said, to get a real random distribution, mod to the next power of 2 and sample until you get one in the range you want (e.g. for 0-9, use while(n = rand()%0x10 > 10);).

---

Related Topics