C++6: Algorithms and Randomness in C++

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!

(source)

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,

1. Too much writing (writing is tiring indeed)
2. 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!

Check out my GitHub and Portfolio!