C++ Int Array/Vector Over 100 Million

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;
}


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;
}
}

• Overall this was great advice, thank you it's greatly appreciated. Though, I am having trouble understanding counts[dis(gen) + dis(gen)]++;. I understand dis(gen) is an int ranging from 1 to 6, and when summed will effectively give a value for that instance of a roll. But why are you using that for an index of counts and then incrementing it? Is this meant to provide the frequency at which that sum occurred? The above code, along with what I have modified of my own returns numbers in the -858993### range; skewing other calculations. – Austin Sep 7 '15 at 1:26
• You've described it well. So counts[n] represents the number of times you got n as the sum of a two-dice throw. Looks like you found a bug in my code :-) I'm not initializing the counts array and got away with it in my tests... Fix it up with int counts[13] = {0}. – Mat Sep 7 '15 at 3:44
• Curious to what compiler/settings you are using. The above takes me about 3 min with VS2015 (default). Also over a billion throws frequency[i] * std::max(36, rolls) / 36.0; will return negative sometimes; consistently for the odds of rolling a 7. Might be just me? – Austin Sep 8 '15 at 3:08
• Missing a pair of parens, that will indeed overflow. Fix is freq*(rolls/36.0) otherwise the result of the multiplication (overflow here) is divided by 36. I'm using GCC and clang, both give about the same timings. – Mat Sep 8 '15 at 3:51

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;

• Appreciate the feedback. #pragma omp parallel for literally cut the execution time in half, very pleased. Though I should note (int i = 0; i <= numberRolls; i++) will add one to many elements and give an error along the lines of “CRT detected that the application wrote to memory after end of heap buffer”'. Seems that it should be changed to < instead of <=. – Austin Sep 7 '15 at 0:11
• Update : This was actually more than half; 1/6 of previous (83% faster). Awesome. Will bump this when the sign i < numberRolls` is fixed. – Austin Sep 7 '15 at 1:45
• Um, yeah, I didn't look through your code as thoroughly as Mat did. I edited my code segment. And I am also glad you found this useful as I'm still a beginner here at Code Review. – Stat1c_V01D Sep 7 '15 at 7:58
• No worries. I consider myself a beginner in most aspects. This was really valuable; wanted to validate your input. – Austin Sep 7 '15 at 10:06