C++ Int Array/Vector Over 100 Million

Question

Textbook style program that generates the values of two, six-sided dice; which are used to perform simple calculations. Recently, I saw an example using similar criteria that was able to utilize 360,000,000 rolls. However, I have not been able to initialize an array or vector containing more than 100 million elements.

Assuming typical settings/RAM, can this be accomplished without an intermediary step? I.E. creating two arrays, generating the values of the first, storing the calculations, and then destroying it before repeating the process. Other criticisms are welcome and encouraged. Thanks in advance.

The code below will support (tested) up to 36,000,000 on my machine; albeit it averages 58 seconds to run.

#include <iostream>
#include <vector>
#include <iomanip>
#include <time.h>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::setw;
using std::count;
using std::exception;
using std::vector;

int rollDice();

bool running(true);
char choice;

int main() {

while (running) {

    bool invalidChoice(true);

    srand((unsigned int)time(NULL));
    int numberRolls;
    double odds[11], percentage[11];
    int occurrence[11], possibleSums[11];
    // Odds for possible sums 2-12 for 2 dice. Index is # out of 36.
    int possibleOdds[11] = {1,2,3,4,5,6,5,4,3,2,1};
    vector<int> numberValues;

    cout << "How many times will the dice roll?\n" << endl;
    cin >> numberRolls;

    try {

        vector<int> numberValues(numberRolls);

        for (int i = 0; i <= numberRolls; i++) {
            numberValues.push_back(rollDice());
        }

        cout << "\nSimulating : " << numberRolls << " rolls...\n" << endl;
        cout << setw(6) << "Sum" << setw(18) << "#Rolled" << setw(18) << "Odds" << setw(18) << "%Error" << endl;

        int p = 2;
        while (p < 12) {
            for (int currentIndex = 0; currentIndex < 11; currentIndex++) {
                possibleSums[currentIndex] = p;
                    occurrence[currentIndex] = count(numberValues.begin(), numberValues.end(), p);
                if (numberRolls <= 36) {
                    odds[currentIndex] = possibleOdds[currentIndex];
                }
                // Scales odds for any number of dice rolls greater than 36 (Non-Multiples of 36)
                else { 
                    odds[currentIndex] = numberRolls / (((double)36) / ((double)possibleOdds[currentIndex]));
                }
                percentage[currentIndex] = ((((double)occurrence[currentIndex]) - ((double)(odds[currentIndex]))) / ((double)(odds[currentIndex]))) * 100;

                cout << setw(6) << possibleSums[currentIndex] << setw(18) << occurrence[currentIndex] << setw(18) << odds[currentIndex] << setw(18) << percentage[currentIndex] << endl;

                p++;

            }// Close for

        } // Close while

    } // Close try

    // Generalized Catch
    catch (exception & e) {
        cerr << "EXCEPTION CAUGHT : " << e.what() << '\n';
    }

    // Option to run again
    while (invalidChoice) {

        cout << "\nRun Again? (y/n): \n " << endl;
        cin >> choice;

        if (choice == 'y') {
            invalidChoice = false;
            cout << "\nSelected: \"" << choice << "\" *** RUNNING AGAIN. ***\n" << endl;
        }
        else if (choice == 'n') {
            invalidChoice = false;
            running = false;
            cout << "\nSelected: \"" << choice << "\" *** EXITING. ***\n" << endl;
        }
        else {
            cerr << "\nERROR: The only valid answers are y/n. \n" << endl;
        }

    }// Close option

}// Close running

// Pause before returning
system("pause");
return 0;

}// End Main

// Function to produce two dice values; returning their sum
int rollDice() {
    int dieI = (rand() % 6) + 1;
    int dieII = (rand() % 6) + 1;
    int sum = dieI + dieII;
    return sum;
}

Answer 1

using std::count;

You're missing <algorithm>, so this will result in a compilation error (unless some of the headers you do include happened to also include <algorithm>, but you can't depend on that).

Also you're only using that function once. Same for these two, only used once, so I'd remove them:

using std::exception;
using std::vector;

Well, in fact you're using vector twice, but that's a bug. numberValues inside the try block shadows the one outside it that you're not using. Remove it.

bool running(true);
char choice;

These two don't belong at global scope. Move them inside main, the closest you can to their first use.

while (p < 12) {
  for (int currentIndex = 0; currentIndex < 11; currentIndex++) {
    // ... stuff that doesn't modify p ...
    p++;
  }
}

The outer while is useless, remove it. p will be incremented 10 times inside the loop, there's no alternate control flow. (Except possibly an exception, but that will break out of the while anyway.)

Then you can actually remove p and replace it with currentIndex+2.

With that cleaned up you'll realize that each position in occurences, percentage and odds are written to once and read from once, only inside that loop. Hence, you don't need these arrays at all. You just need one int and two doubles.

    } // Close for
  } // Close while
} // Close try

If you need those comments, it means you've nested too deep or have too much code between the top and bottom of the blocks - or both. Use functions to reduce the nesting level and the amount of code that needs to be tracked at once.

system("pause");

That's not portable. Use std::getc, or remove that altogether.

Finally, your y/n loop will go wild if the user types ^D or closes the input stream (e.g. echo 100 | ./dice_game will go into an infinite loop). Error out if the read (in >> choice) fails.

---

As for the algorithm: you're using a lot of memory, and traversing the vector 10 times to count the various sums you got. This is not very efficient.

You don't need to remember the individual rolls here, only the counts of each sum you got.

In pseudo-code:

int count[12]
for (i in 1 .. num_rolls)
  count[ rollDice() ]++

---

rand() Considered Harmful

There are better alternatives in C++ for rand(). That video is well worth watching.

Here's an example of how to use <random> for the std::uniform_int_distribution page over at cppreference.com:

#include <random>
#include <iostream>

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 6);

    for (int n=0; n<10; ++n)
        std::cout << dis(gen) << ' ';
    std::cout << '\n';
}

Use this rather than rand() % non_power_of_two to avoid non-uniformity.

---

Here's an implementation of that logic, with the retry omitted, lines shortened and a few cosmetic changes.

Takes about 46s for one billion throws on my computer. (Limiting factor in terms of number of throws is the scale of int. Should probably be unsigned, and use a larger type of you want more than a few billion throws.)

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::setw;

int main()
{
  std::random_device rd;
  std::mt19937 gen(rd());
  std::uniform_int_distribution<> dis(1, 6);

  // Ideal frequency of a given sum (0-12) for 36 throws
  int frequency[13] = {0, 0, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1};

  cout << "How many times will the dice roll?" << endl;
  int rolls = 0;
  if (!(cin >> rolls)) {
    cerr << "Please enter a number." << endl;
    return 1;
  }

  cout << "Simulating : " << rolls << " rolls..." << endl;
  cout << setw(6) << "Sum" << setw(18) << "#Rolled" << setw(18) << "Ideal"
       << setw(18) << "%Error" << endl;

  int counts[13] = {0};
  for (int i = 0; i < rolls; i++) {
    counts[dis(gen) + dis(gen)]++;
  }

  for (int i = 2; i < 13; i++) {
    double ideal = frequency[i] * (std::max(36, rolls) / 36.0);
    double percentage = 100 * (counts[i] - ideal) / ideal;

    cout << setw(6) << i << setw(18) << counts[i] << setw(18) << ideal
         << setw(18) << percentage << endl;
  }
}

Answer 2

I suppose you got bad compile flags. Try compiling your code for x64. At first I got your code compiled and it gave me "bad allocation" exception. I changed compilation flags and it worked out well - started simulating rolls. And you are missing #include <algorithm>

You might also try OpenMP for some of the loops (although it might get tricky to make its performance to the top. Details here):

        vector<int> numberValues(numberRolls);
        int *nvPtr = &numberValues[0];

        #pragma omp parallel for 
        for (int i = 0; i < numberRolls; i++)
        {
            nvPtr[i] = rollDice();
        }

        cout << "\nSimulating : " << numberRolls << " rolls...\n" << endl;