Random Number Generator

[JB71]

Hello all,
I am a total noob when it comes to programming, and I am stuck on a problem that I have worked on for a few hours now. Basically, I need to write a C++ program that seeds a RNG, prompts the user for a minimum value and a max value. Then the program needs to prints 10 random integers between those two values, and 10 float values (with three decimal places).
Where I am stuck, is printing just 10 values between my chosen values, and printing float values. also, if there are good resources (besides this amazing website) to better understand C++ I am all ears, I really do want to learn this language. Thanks in advance.


#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main () {


int MIN_VALUE;
int MAX_VALUE;

cout << "Input minimum value; ";
cin >> MIN_VALUE;

cout << "input maximum value: ";
cin >> MAX_VALUE;

int value1;
int value2;
unsigned seed = time(0);


srand(seed);

//cout << "Randon values between minimum and maximum value: ";

value1 = (rand() % (MAX_VALUE - MIN_VALUE + 1) + MIN_VALUE);
value2 = (rand() / ((float) MAX_VALUE - MIN_VALUE +1) + MIN_VALUE);
for( int i = 1; i <= MAX_VALUE; i++ ) {
if( i >= MIN_VALUE && i <= MAX_VALUE)
cout << i << endl;


}



}

[TheIdeasMan]

Hi

Please always use code tags:

http://www.cplusplus.com/articles/z13hAqkS/

Look at the examples on these pages.

https://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution
https://en.cppreference.com/w/cpp/numeric/random/uniform_real_distribution

That is how I would do it, but it won't help for the assignment. You need to put the code that makes the random numbers inside the for loop.

cppreference is an awesome resource, also look at

https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines

Also, this should be in the beginners section.

[againtry]

#include <iostream>
#include <ctime>

using namespace std;

int main ()
{
    int MIN_VALUE;
    int MAX_VALUE;
    
    cout << "Input minimum value: ";
    cin >> MIN_VALUE;
    
    cout << "input maximum value: ";
    cin >> MAX_VALUE;
    
    int value1;
    float value2;
    
    unsigned seed = time(0);
    srand(seed);
    
    
    // INTEGERS
    for( int i = 0; i < 10; i++ )
    {
        value1 = rand() % (MAX_VALUE - MIN_VALUE - 1) + MIN_VALUE + 1;
        cout << value1 << ' ';
    }
    cout << '\n';
    
    // FLOATS (or doubles)
    for( int i = 0; i < 10; i++ )
    {
        value2 = (rand() % 999)/1000.;
        cout << (MAX_VALUE - MIN_VALUE - 1)* value2 + MIN_VALUE + 1 << ' ';
    }
    cout << '\n';
    
    return 0;
}

Input minimum value: 80
input maximum value: 90
88 89 84 84 83 86 85 81 81 87 
82.485 81.027 89.82 83.304 84.213 89.946 87.561 85.23 89.208 84.708 
Program ended with exit code: 0

[seeplus]

#include <iostream>
#include <iomanip>
#include <random>

constexpr size_t noInt {10};
constexpr size_t noReal {10};

int main() {
	std::mt19937 rng(std::random_device {}());
	size_t minValue {};
	size_t maxValue {};

	std::cout << "Input minimum value: ";
	std::cin >> minValue;

	std::cout << "input maximum value: ";
	std::cin >> maxValue;

	const std::uniform_int_distribution<size_t> intDistrib(minValue, maxValue);

	for (size_t i {}; i < noInt; ++i)
		std::cout << intDistrib(rng) << ' ';

	std::cout << '\n';

	const std::uniform_real_distribution<double> relDistrib(minValue, maxValue);

	std::cout << std::fixed << std::setprecision(3);
	for (size_t i {}; i < noReal; ++i)
		std::cout << relDistrib(rng) << ' ';

	std::cout << '\n';
}

Input minimum value: 45
input maximum value: 789
779 379 313 161 378 197 759 404 498 348
768.602 417.936 671.507 576.492 701.682 307.244 341.209 751.567 781.332 400.051

[George P]

https://www.learncpp.com/cpp-tutorial/random-number-generation/

A lot of people still use the C library random number generator in C++ code. Don't.

https://web.archive.org/web/20180123103235/http://cpp.indi.frih.net/blog/2014/12/the-bell-has-tolled-for-rand/

The C++ way of generating random numbers can at first look intimidating, there are so many choices. Especially when compared to how C generates random numbers.

With a bit of time and usage generating random numbers using <random> becomes easier.

You could even create a separate toolkit header/source file you add to your projects and the nitty-gritty details of generating random numbers is much easier.

http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3551.pdf

[George P]

You want a good online resource to learn C++?

There is a tutorial here:
http://www.cplusplus.com/doc/tutorial/

Good, but not as good as it could be since it hasn't been updated for C++14/17/20.

A better (IMO) online tutorial is Learn C++, it is updated frequently:
https://www.learncpp.com/

Neither tutorial will teach ALL of what C++ has to offer, especially C++20. There is a decent online reference resource for that, https://en.cppreference.com/w/

Lots of examples at all three links, but cppreference is not for learning. Lots of technical info and the examples there are not for beginners.

[George P]

Oh, and....

PLEASE learn to use code tags, they make reading and commenting on source code MUCH easier.

http://www.cplusplus.com/articles/jEywvCM9/
http://www.cplusplus.com/articles/z13hAqkS/

HINT: you can edit your post and add code tags.

Some formatting & indentation would not hurt either

[JB71]

Thank you so much for all your help. Apologies for not using code tags, and for using the wrong section. Again, Thank you so much

[Duthomhas]

So, you think you want a random number, huh?

Welcome to the rabbit hole, my friend.


T H E   P R O B L E M   W I T H   M O D U L O

Using remainder % directly with rand() gets you biased values. The reason has to do with the Pigeonhole Principle — named because we can visualize pigeons settling into a box of cubby holes.

Suppose RAND_MAX were 19 and (max-min+1) were 6. If I just used remainder, I would get:

    0..19      →   0  1  2  3  4  5    6  7  8  9 10 11   12 13 14 15 16 17   18 19    (pigeons)
    0..19 % 6  →   0  1  2  3  4  5    0  1  2  3  4  5    0  1  2  3  4  5    0  1    (cubby holes)

Notice how you are more likely (4:20 probability) to get a 0 or 1 than you are (3:20 probability) to get a 2, 3, 4, or 5. This is called bias, and it is basically a guaranteed consequence of using remainder directly on the result of rand() (since RAND_MAX is always going to be a value of the form 2ⁿ-1).

This looks like it shouldn’t matter much, but it actually has big consequences, even in games and systems where the user does not directly see the result of rolling his dice. I’m more likely to get asparagus than broccoli, and I can’t stand asparagus. Monster A is more likely to appear than Monster D, and Monster A is fiddly to defeat. The computer is more likely to roll a rock or paper than scissors, so playing paper every time increases your odds of winning. You get the idea.


The solution to this problem should be fairly obvious: we need to make sure that each cubby hole fits the same number of pigeons.


O B S E R V A T I O N   O N E

The first observation we can make is that we can simply ignore values we don’t want:

int value;
do value = rand();
while ((value < min) or (value > max));

std::cout << value << "\n";

This works because rand() is still just as likely to give us any random value as any other, but we are not packing uneven numbers of pigeons into their holes. We only pay attention to one set of pigeons and their holes, and enforce the idea of one pigeon per hole.

Simply ignoring pigeons we don’t want does not change the likelihood of any pigeon coming along. It does change the likelihood of a pigeon we want coming along, so we may have to wait, but when a pigeon we want does arrive it is just as likely as any other of our desired pigeons to have arrived.

Hence, there is no bias.

You may have noticed the drawback, though, and it can be significant. If we only want, say, 6 pigeons out 32,000, we can be stuck waiting a while.

Perhaps you can see where we are going with this:


O B S E R V A T I O N   T W O

We can put as many pigeons in each hole as we want as long as each hole gets the same number of pigeons.

Again suppose that RAND_MAX is 19, and (max-min+1) is 6. That gives us three whole divisions of [0..RAND_MAX] that we can map to a number in the domain [min..max]:

    00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
    └───────────────┘ └───────────────┘ └───────────────┘

Do you see why?
_{^{floor(20 / 6) → 3}}

Notice how there are two values that do not map into a full [min..max] domain. These are the two pigeons we will ignore.

The trick, then, is first to map our [min..max] to [0..N]:

int N = max - min; // [0..N] ←→ [min..max] 

To convert back, all we need to do is add min.

int value = value_0_to_N + min;

And second, we must divvy up [0..RAND_MAX] with the correct number of subranges to determine which numbers in [0..RAND_MAX] to ignore:

int our_rand_max = (RAND_MAX + 1) / (N+1) * (N+1); // warning! 

The above code has a potential problem, but it is unlikely to ever occur in any C-library implementation. Even so, let us be clean about it and avoid the potential overflow error (if RAND_MAX were the maximum int value):

int our_rand_max = (N == RAND_MAX)
  ? RAND_MAX
  : RAND_MAX - (RAND_MAX % (N+1)) + 1;

Yeah, it gets messy. And, it only works if N ≤ RAND_MAX. If (N > RAND_MAX) we've got new problems, but for now we will simply pretend they can’t ever happen.

Unless someone wants an answer here, but it involves modifying how we get a random value to begin with.

int random_int_in_range( int min, int max )
{
  int N = max - min;  // [0..N] ←→ [min..max]
  int our_rand_max = (N == RAND_MAX)
    ? RAND_MAX
    : RAND_MAX - RAND_MAX % (N+1) + 1;
  int value;
  do value = rand();
  while (value > our_rand_max);
  return value % (N+1) + min;
}

Okay, that’s messy enough, but it is how to do it in C.


C + +   M A K E S   T H I S   E A S Y

In fact, C++ makes this so easy it hurts to look at.

#include <random>

std::minstd_rand rng( std::random_device{}() );  // our RNG, properly seeded

int random_int_in_range( int min, int max )
{
  return std::uniform_int_distribution <> ( min, max )( rng );
}

That’s it!

C++ even makes it easy to get floating-point numbers:

int random_float_in_range( double min, double max )
{
  return std::uniform_real_distribution <> ( min, max )( rng );
}

You don’t even have to use minstd_rand. You can use any random number generator you wish. Heck, you could just use the random_device as your RNG.

int random_int_in_range( int min, int max )
{
  return std::uniform_int_distribution <> ( min, max )( std::random_device{}() );
}

int random_float_in_range( double min, double max )
{
  return std::uniform_real_distribution <> ( min, max )( std::random_device{}() );
}

There is a caveat here: random_device is an evil, heartless bastard child that can throw for all kinds of stupid reasons. Fortunately, if you’ve got yourself a modern compiler (no more than 4 years old), then it should behave. If not then you are better off seeding a different RNG using the clock in <chrono>. Let me know if you need to know more.

Again, if anyone wants a C-version, post and we can cover it.

Hope this helps.

[seeplus]

Great explanation - the best I've ever seen! :) :) :)

Could you similarly explain the difference in the <random> pseudo-random number engines (instantiations) - and when you'd choose one over the other. I've read that using mt19937 is the best - which I've since always used - but I've no idea why..

[Duthomhas]

Please forgive the crude graphics. This is crufted together from a FAQ I haven’t quite finished writing...

There are four types of random number generators, conveniently grouped via two criteria: security and sampling:

            insecure                secure
      ╔══════════════════╗   ╔══════════════════╗
      ║       PRNG       ║   ║      CSPRNG      ║
    p ╟──────────────────╢   ╟──────────────────╢
    s ║ rand()           ║   ║ /dev/urandom     ║
    e ║ LGC              ║ ← ║ MS Crypto API    ║
    u ║ Mersenne Twister ║   ║ Yarrow           ║
    d ║ XOR-Shift        ║   ║ ChaCha20         ║
    o ║                  ║   ║ Blum Blum Shlub  ║
      ╚══════════════════╝   ╚══════════════════╝
                                      ↑
      ╔══════════════════╗   ╔══════════════════╗
      ║       TRNG       ║   ║      STRNG       ║
      ╟──────────────────╢   ╟──────────────────╢
    t ║ Noise Sampling   ║   ║                  ║
    r ║ Radioactive Decay║ → ║     (this is     ║
    u ║ Lightning Strikes║   ║ “whitened” TRNG, ║
    e ║ Double Pendulums ║   ║   AKA unbiased)  ║
      ║                  ║   ║                  ║
      ╚══════════════════╝   ╚══════════════════╝

The arrows indicate a seed/source relationship.


TRNG                                                                                                                 

True random number generators gather data from the environment. They have a problem: they are biased, meaning they have observable patterns. So, you cannot really use them directly.


STRNG                                                                                                                

Strong true random number generators are just data from a TRNG that has been “whitened”, or unbiased. The basic idea is to throw out any patterns in the TRNG data, and is easier to do than you would think. I won’t go into it, though. (It’s minutiae.)


PRNG                                                                                                                 

Pseudo-random number generators generate apparently random sequences, but they aren’t actually random. They are generated via a mathematical formula that feeds back into itself, much like fractals.

••• LCG •••

One of the simplest (and near oldest) PRNGs is a linear congruential generator, which is a linear function modified with a remainder function (which creates the mathematical congruence — i.e. an overlapping of values). This gets you a graph that looks something like this:

       │
    N ─┼────•─────•─────•────
       │   •     •     •
       │  •     •     •
       │ •     •     •     •
       │•     •     •     •
       │     •     •     •
    0 ─┼─────────────────────

As you may guess, N is our modulus, which describes the range of our PRNG’s output.

Now all we need is to input any number on the X-axis, find where it crosses the line, and get as output our generated value:

       │
    N ─┼────•─────•─────•────
       │   •     •     •
 output│◄─┐     •     •
       │ •│    •     •     •
       │• │   •     •     •
       │  │  •     •     •
    0 ─┼──┴──────────────────
          input

By feeding the output number back into the equation we get a nice, uniform spread of numbers in [0,N-1].
    
       │                                │                                │
    N ─┼────•─────•─────•────        N ─┼────•─────•─────•────        N ─┼────•─────•─────•────
       │   •     •     •                │◄──•─────┐     •                │◄──•─────┐     •
 output│◄─┐     •     •                 │◄─┐     •│    •                 │◄─┐     •│    •
       │ •│    •     •     •            │ •│    • │   •     •            │ •│    • │   •     •
       │• │   •     •     •             │• │   •  │  •     •             │◄─┼───•──┼──┐     •
       │  │  •     •     •              │  │  •   │ •     •              │  │  •   │ •│    •
    0 ─┼──┴──────────────────        0 ─┼──┴──────┴───────────        0 ─┼──┴──────┴──┴────────
          input                            

We can change the way numbers get distributed by adjusting the slope of the line. In fact, the quality of the PRNG is dependent on both the slope and the modulus — both must be chosen carefully. (If any number in [0,N-1] is not possible to output then the generator would be biased.)

[Duthomhas]

The reason we call this a “linear congruential generator” is because it is a congruential equation of a line:

    y ≡ mx + b (mod N)

There are several neat things about LCGs:
  • its output appears to be sufficiently random that we can treat it as such
  • we can generate the same sequence as many times as we
     like by starting with the same first number (the seed)
  • it is really, really simple to implement

The hard things about LCGs are:
  • they are observable (i.e. predictable — more on that in a moment)
  • they are a bit tricky to balance for an unbiased, uniform output

C’s rand() is an LCG. These days, LCG* includes an entire class of algorithms where we just mix up the basic line equation to use different operators and perhaps additional terms.

••• Seeding a PRNG •••

The hardest part when using PRNGs is getting a good input value to start with. The most common method is to use the wall clock in the millisecond range or something like that, because we can often assume that program invocation is related to the moment a human’s finger pressed a button, which is somewhat random-ish.

Sometimes you will also see (bad) advise to involve hashes and PIDs and the like. Can you think of reasons why doing these things is bad?

Of course, the best choice to seed your PRNG is to use a CSPRNG.

••• Other types of PRNGs •••

The main problem with an LCG is that it is really, really easy to observe. Just watching a few iterations will get you the modulus, slope, y-intercept, and even the seed if you know how many generations it has run.

Other PRNGs exist to make it harder to observe them. Mersenne Twister, for example, was supposed to be the end-all solution to that, but it turns out as few as 600 iterations are enough to recover MT’s state and begin predicting its output.

Naturally this is a huge honking problem when doing things like gambling or cryptography, where predictability is a bad thing.

Another reason for variations is to overcome some behaviors common in other PRNGs. For example, the original LCG used for rand() tended to produce runs in the lower bits of a number. For example, you would get a very bad sequence if you just wanted bit 0 (for a true/false generator): too many ones followed by too many zeros, violating the probability of a true heads/tails sequence.

Almost every PRNG exists to improve a problem observed in other generators. (Or as an intellectual exercise in maths.)


CSPRNG                                                                                                               

Cryptographically-secure pseudo-random number generators might be described as something of a mutated zombie child of a PRNG and portal to a black hole. The idea is this: we cannot really escape using a PRNG (they are PRNGs), but we can mix things up by changing things like slope¹ and y-intercept¹ on the regular using data from a STRNG.

[1] This is by way of example for you, dear reader — CSPRNGs are a bit more mathematically interesting than a simple LCG.

They exist because it a TRNG takes time to gather data (what we call entropy), and if we are not careful we can use it up. The idea, then, is to reduce the number of times we need to sample the STRNG to simply mutate a PRNG on a regular, but not draining schedule.

Adding the unpredictability in makes the CSPRNG truly unpredictable.²

[2] Tautology club for the win!

But, what is especially nice, is that you can synchronize two separate instances of a CSPRNG so that you can use them as a secure encryption-decryption pad between two agents — such as your web browser and the website you are connected to. Those two agents can talk because they can predict each other.. but nothing listening in can.

But that’s before the math even begins to get interesting.


Alas, I’m done for now...

[JLBorges]

From boost:

The following table gives an overview of some characteristics of the (pseudo-random number) generators. The cycle length is a rough estimate of the quality of the generator; the approximate relative speed is a performance measure, higher numbers mean faster random number generation.
https://www.boost.org/doc/libs/1_78_0/doc/html/boost_random/reference.html#boost_random.reference.generators

...there is generally a quality/performance/memory trade-off to be decided upon when choosing a random-number generator. ... Additionally, employing several fundamentally different random number generators for a given application of Monte Carlo simulation will improve the confidence in the results.

If the names of the generators don't ring any bell and you have no idea which generator to use, it is reasonable to employ mt19937 for a start: It is fast and has acceptable quality.

Note: These random number generators are not intended for use in applications where non-deterministic random numbers are required.

[againtry]

Suppose RAND_MAX were 19 and (max-min+1) were 6.

The reality is RAND_MAX is library dependent with common values being 32767 and 2,147,483,647

[Duthomhas]

Yes, as noted, RAND_MAX is always going to be of the form 2ⁿ-1, but I’m not going to draw 32,000 pigeons.

[George P]

@Duthomhas,

If'n I understand your text and graphics correctly none of the C++ random engines are what would be classified as cryptographically-secure. No surprise there.

Except for maybe std::random_device, if the implementation has it working. Which hasn't always been the case.

No matter what PRNG engine one uses in C++ code it has to be better than using C's rand. Even std::default_random_engine being an alias for whatever engine a particular implementation wants to use.

I personally use std::default_random_engine as my primary "go-to" when writing code for generating random numbers. It works for me. YMMV.

I might consider making std::mt19937 my new "go-to."

[againtry]

@Duthomas
Unfortunately the pigeon hole calculation is misleading because the mod 19 mod 6 situation is not what happens in practice. It demonstrates a problem that doesn’t exist simply because RAND_MAX is so large.

rand() and mt19937 give similar results in uniform distribution calculations, both of which are close to ‘perfectly uniform’ and pigeon holes are not reason enough for using one over the other for normal day to day non-specialized stuff.

An array of RAND_MAX pigeon holes is no problem.

[Albatross]

Required reading: https://ericlippert.com/2013/12/16/how-much-bias-is-introduced-by-the-remainder-technique/

-Albatross

[George P]

Too many people still insist using rand and modulo clamping for getting a distributed range of pseudo-random numbers isn't a total hot mess of crap. They're wrong. Especially when C++ has better ways to do it.

[seeplus]

To me, once you know the magic incantations for C++ random (see above) it's much easier to use as you can specify the min/max numbers for the distribution. No more messing with a formula to get the range required (which often introduced issues apart from not being really evenly distributed).