Random number generator with probably based on dice sides in the millions

Question

I'm trying to create a program that is designed to determine how many elements a video game character can control. In this setting, the general population can control at least 1 element. But I want 1 out of every 1000 people to have 2 elements they can control, 1 out of every 10,000 people can control 3 elements and 1 out of every 100,000 people can control 4.

The program start by asking how many are in the population. This will equal how many sides the die has. Then, it loops through, generating random numbers and then outputting how many people can control how many elements.

I run into an issue that I think had to do with my data type. Even if I put in a population of 1,000,000 the loop iterates a million times but never rolls numbers beyond 5 digits. so a population beyond 99,999 could technically never have 3 or 4 elements. It doesn't seem to go beyond 50k ish and I remember reading that one of the data types only does 65k-ish numbers. Is that the cause? What data types should I use to be able to roll random numbers between 0 and millions?

#include <iostream>
#include <ctime>
#include <iomanip>

using namespace std;


int main()
{
    int min = 1, max, sides, roll;
    double oneCounter = 0.0, twoCounter = 0.0, threeCounter = 0.0, fourCounter = 0.0;

    unsigned long seed = time(0);
    srand(seed);
    cout << "How many characters would you like to generate?: ";
    cin >> sides;
    max = sides;

    cout << "\n";

    for (int i = 0; i < sides; i++)
    {
        roll = rand() % (max - min + 1) + min;

        if (roll % 100000 == 0)
        {
            cout << roll << ": You will have 4 elements" <<endl;
            fourCounter++;
        }
        else if (roll % 10000 == 0)
        {
            cout << roll << ": You will have 3 elements" <<endl;
            threeCounter++;
        }
        else if (roll % 1000 == 0)
        {
            cout << roll << ": You will have 2 elements" <<endl;
            twoCounter++;
        }
        else
        {
            cout << roll << ": You will have 1 element." <<endl;
            oneCounter++;
        }
    }

    cout << left;
    cout << "\n==============================" <<endl;
    cout <<setw(11) << "Potential"
         << setw(10) << "QTY"
         << setw(10) << "Pct"
         << endl;
    cout << "==============================" <<endl;
    cout << setw(11) << "Single: " 
         << setw(10) << oneCounter
         << setw(10) << (oneCounter/sides)*100 <<endl;

    cout << setw(11) << "Double: " 
         << setw(10) << twoCounter 
         << setw(10) << (twoCounter/sides)*100 <<endl;

    cout << setw(11) << "Triple: " 
         << setw(10) << threeCounter 
         << setw(10) << (threeCounter/sides)*100 <<endl;

    cout << setw(11) << "Quadruple: " 
         << setw(10) << fourCounter 
         << setw(10) << (fourCounter/sides)*100 <<endl;


    cout << "\n\n";
    return 0;
}

I have included a screen shot of the results when done for a population (sides) of 100,000 people. The probabilities looks fine, but the numbers are never more than 5 digits long.

Answer 1

This issue does not have to do with the type ranges for the variables, as ints span from –2,147,483,648 to 2,147,483,647 (with a 32bit compiler, see comment below).

The error here is that the rand() function only returns up to a maximum number defined in the stdlib.h file, which is 32767. You should use the standard random library header to generate your random number. I recommend taking a look at this answer to see how to do that easily, How to generate very Large random number in c++

Edit: See user4581301's comment below. I had assumed the ints type range, but it would probably be safest to use long here to ensure the large numbers you are trying to get can fit in the variable.

Answer 2

rand comes from the dark ages when programmers had to grub around in the muck to get every last bit they could. If they had an 8-bit CPU they celebrated. For 16 bits, they sacrificed their firstborn. Good thing that I was child number two, eh?

Nah. Just kidding. My dad was an accountant. My big brother's fine.

Anyway, rand may not be sufficient to generate the numbers you need. Some implementations still cap the output at 15 bits, matching the best positive value you were going to get from an integer back in the old days. rand also had to be fast on severely resource-constrained computers and as a result it makes assumptions and requires usage patterns that flat-out suck.

Fast forward to today where integers are sometimes 64 bit and you may have more computing power in your pocket than the whole world had when C was first written. We can do a whole lot better. You could use std::uniform_int_distribution as an almost drop-in replacement for rand that will generate numbers the size you need, but we can do even better than that.

Note: All I've done here is modify the example code from std::discrete_distribution to use different weights for the purpose of this demonstration.

#include <iostream>
#include <map>
#include <random>

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::discrete_distribution<> d({ 1.0, 
                                     1.0 / 1000.0, 
                                     1.0 / 10000.0, 
                                     1.0 / 100000.0 });
    std::map<int, int> m;
    for (int n = 0; n<10000000; ++n) {
        ++m[d(gen)];
    }
    for (auto p : m) {
        std::cout << p.first + 1 << " generated " << p.second << " times\n";
    }
}

This does all of the magic for you and spits out 1 through 4 in proportion with the given weights. Virtually all of the code needed in the Asker's program to select the number of elements that could be controlled are gone.

This is really close and probably close enough, but as you can see, sums up to a combined weight of slightly over 1. Ooops. Not quite what you've coded where if you have a 1 in 100000 event it supersedes the 1 in 10000, 1 in 1000, and 1 in 1 events. We want something that looks more like

#include <iostream>
#include <map>
#include <random>

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::discrete_distribution<> d({ 100000 - 1000, 
                                     1000 - 100,
                                     100 - 1, 
                                     1});
    std::map<int, int> m;
    for (int n = 0; n<1000000; ++n) {
        ++m[d(gen)];
    }
    for (auto p : m) {
        std::cout << p.first + 1 << " generated " << p.second << " times\n";
    }
}

Caveats:

Make certain that random_device provides a useful seed on your system. MinGW's random_device implementation has an annoying habit of always returning 0, a perfectly valid random number but still useless if you get it all of the time (it's effectively a Randall Number Generator).