Good evening, Medium! A few days ago, we learned about linkage and why global variables are evil in C++.
After a bit of time learning and speedrunning Chapter 8 on learncpp, I’ve decided that we’re going to look into pseudo random number generators (PRNGs) and a bunch of other algorithm topics this time around.
Let’s get to it!
PRNG
Before we can explain PRNGs and why computers suck at random number generation, we need to understand how algorithms work.
Algorithms are a finite set of instructions made to produce an output, given some amount of information.
Yes, I’m going to start using that to highlight key points. It looks cool.
Anyway, that’s all that algorithms are by definition. Additionally, algorithms can be stateful or stateless. A stateful algorithm holds information from previous calls, while a stateless algorithm holds no information from previous algorithms.
Consider the following algorithm:
#include <iostream>
int decrementSequence()
{
static int s_val { 1 };
return --s_val;
}
int main() {
std::cout << decrementSequence() << '\n'; // 0
std::cout << decrementSequence() << '\n'; // -1
std::cout << decrementSequence() << '\n'; // -2
std::cout << decrementSequence() << '\n'; // -3
return 0;
}
This is a stateful algorithm since it preserves the static variable s_val across all function calls (until the program terminates).
Algorithms can also be nondeterministic or deterministic. A deterministic algorithm will exhibit the same behaviour given the same input, whereas a nondeterministic will provide undefined/random behaviour despite being given the same input across all calls.
Consider the following algorithm:
// brought to you by:
// https://www.learncpp.com/cpp-tutorial/introduction-to-random-number-generation/
#include <iostream>
// For illustrative purposes only, don't use this
unsigned int LCG16() // our PRNG
{
static unsigned int s_state{ 0 }; // only initialized the first time this function is called
// Generate the next number
// We modify the state using large constants and intentional overflow to make it hard
// for someone to casually determine what the next number in the sequence will be.
s_state = 8253729 * s_state + 2396403; // first we modify the state
return s_state % 32768; // then we use the new state to generate the next number in the sequence
}
int main()
{
// Print 100 random numbers
for (int count{ 1 }; count <= 100; ++count)
{
std::cout << LCG16() << '\t';
// If we've printed 10 numbers, start a new row
if (count % 10 == 0)
std::cout << '\n';
}
return 0;
}
// OUTPUT
4339 838 25337 15372 6783 2642 6021 19992 14859 26462
25105 13860 28567 6762 17053 29744 15139 9078 14633 2108
7343 642 17845 29256 5179 14222 26689 12884 8647 17050
8397 18528 17747 9126 28505 13420 32479 23218 21477 30328
20075 26558 20081 3716 13303 19146 24317 31888 12163 982
1417 16540 16655 4834 16917 23208 26779 30702 5281 19124
9767 13050 32045 4288 31155 17414 31673 11468 25407 11026
4165 7896 25291 26654 15057 26340 30807 31530 31581 1264
9187 25654 20969 30972 25967 9026 15989 17160 15611 14414
16641 25364 10887 9050 22925 22816 11795 25702 2073 9516
This looks quite random but it really isn’t. Given someone manages to figure out that we do all those calculations on line 16 with all those integer literals, our PRNG algorithm is rather simple to crack.
A simple way of improving our current algorithm would be to generate and use a seed, which can assist with spicing up the random numbers using the added variability.
#include <iostream>
static int s_seed {};
unsigned int LCG16()
{
s_seed = 8253729 * s_seed + 2396403;
return s_seed % 32768;
}
int main()
{
std::cout << "Enter a seed (0-10): ";
std::cin >> s_seed;
for (int count{ 1 }; count <= 10; ++count)
{
std::cout << LCG16() << '\t';
if (count % 5 == 0)
std::cout << '\n';
}
return 0;
}
//OUTPUT
Enter a seed (0-10): 6
14265 26828 7999 4294960914 4294954053
23256 7883 4294943774 4294964945 8932
Enter a seed (0-10): 6
14265 26828 7999 4294960914 4294954053
23256 7883 4294943774 4294964945 8932
Enter a seed (0-10): 4
21879 4294941770 4294959229 11792 4355
4294939990 18185 12828 4294959759 4294960226
There is slight variability in our output using altering seeds now. Though, if we use the same seed over and over, we’ll get the same results over and over again, though this is far more “random” than our previous, more hardcoded algorithm.
std::cerr
That’s all I’m going to gloss over when it comes to algorithms. There’s a whole slew of information regarding PRNGs that I couldn’t fit here mainly because,
- Too much writing (writing is tiring indeed)
- Far too confusing on my mind given the depth of information I have to write on (will not lead to a concise blog)
As always, all of the info in this blog post can be found on learncpp both here and here, with both lessons going over random number generation and the <random> header respectively.
Over the next few days, I’ll be learning about error/exception handling a bit. Hopefully, I can get a blog out by midweek or Tuesday. If not, you can safely assume I’ve either given up on C++ or died.
Anyway, thanks for reading, Medium. Enjoy the rest of your weekend!
If you enjoyed this blog post, consider following me or subscribing to support me!