Search

5.9 — Random number generation

The ability to generate random numbers can be useful in certain kinds of programs, particularly in games, statistics modeling programs, and scientific simulations that need to model random events. Take games for example -- without random events, monsters would always attack you the same way, you’d always find the same treasure, the dungeon layout would never change, etc… and that would not make for a very good game.

So how do we generate random numbers? In real life, we often generate random results by doing things like flipping a coin, rolling a dice, or shuffling a deck of cards. These events involve so many physical variables (e.g. gravity, friction, air resistance, momentum, etc…) that they become almost impossible to predict or control, and produce results that are for all intents and purposes random.

However, computers aren’t designed to take advantage of physical variables -- your computer can’t toss a coin, throw a dice, or shuffle real cards. Computers live in a controlled electrical world where everything is binary (false or true) and there is no in-between. By their very nature, computers are designed to produce results that are as predictable as possible. When you tell the computer to calculate 2 + 2, you always want the answer to be 4. Not 3 or 5 on occasion.

Consequently, computers are generally incapable of generating random numbers. Instead, they must simulate randomness, which is most often done using pseudo-random number generators.

A pseudo-random number generator (PRNG) is a program that takes a starting number (called a seed), and performs mathematical operations on it to transform it into some other number that appears to be unrelated to the seed. It then takes that generated number and performs the same mathematical operation on it to transform it into a new number that appears unrelated to the number it was generated from. By continually applying the algorithm to the last generated number, it can generate a series of new numbers that will appear to be random if the algorithm is complex enough.

It’s actually fairly easy to write a PRNG. Here’s a short program that generates 100 pseudo-random numbers:

The result of this program is:

23070   27857   22756   10839   27946
11613   30448   21987   22070   1001
27388   5999    5442    28789   13576
28411   10830   29441   21780   23687
5466    2957    19232   24595   22118
14873   5932    31135   28018   32421
14648   10539   23166   22833   12612
28343   7562    18877   32592   19011
13974   20553   9052    15311   9634
27861   7528    17243   27310   8033
28020   24807   1466    26605   4992
5235    30406   18041   3980    24063
15826   15109   24984   15755   23262
17809   2468    13079   19946   26141
1968    16035   5878    7337    23484
24623   13826   26933   1480    6075
11022   19393   1492    25927   30234
17485   23520   18643   5926    21209
2028    16991   3634    30565   2552
20971   23358   12785   25092   30583

Each number appears to be pretty random with respect to the previous one. As it turns out, our algorithm actually isn’t very good, for reasons we will discuss later. But it does effectively illustrate the principle of PRNG number generation.

Generating random numbers in C++

C (and by extension C++) comes with a built-in pseudo-random number generator. It is implemented as two separate functions that live in the cstdlib header:

srand() sets the initial seed value to a value that is passed in by the caller. srand() should only be called once.

rand() generates the next random number in the sequence. That number will be a pseudo-random integer between 0 and RAND_MAX, a constant in cstdlib that is typically set to 32767.

Here’s a sample program using these functions:

Here’s the output of this program:

17421	8558	19487	1344	26934	
7796	28102	15201	17869	6911	
4981	417	12650	28759	20778	
31890	23714	29127	15819	29971	
1069	25403	24427	9087	24392	
15886	11466	15140	19801	14365	
18458	18935	1746	16672	22281	
16517	21847	27194	7163	13869	
5923	27598	13463	15757	4520	
15765	8582	23866	22389	29933	
31607	180	17757	23924	31079	
30105	23254	32726	11295	18712	
29087	2787	4862	6569	6310	
21221	28152	12539	5672	23344	
28895	31278	21786	7674	15329	
10307	16840	1645	15699	8401	
22972	20731	24749	32505	29409	
17906	11989	17051	32232	592	
17312	32714	18411	17112	15510	
8830	32592	25957	1269	6793

PRNG sequences and seeding

If you run the rand() sample program above multiple times, you will note that it prints the same result every time! This means that while each number in the sequence is seemingly random with regards to the previous ones, the entire sequence is not random at all! And that means our program ends up totally predictable (the same inputs lead to the same outputs every time). There are cases where this can be useful or even desired (e.g. you want a scientific simulation to be repeatable, or you’re trying to debug why your random dungeon generator crashes).

But often, this is not what is desired. If you’re writing a game of hi-lo (where the user has 10 tries to guess a number, and the computer tells them whether their guess is too high or too low), you don’t want the program picking the same numbers each time. So let’s take a deeper look at why this is happening, and how we can fix it.

Remember that each number in a PRNG sequence is generated from the previous number, in a deterministic way. Thus, given any starting seed number, PRNGs will always generate the same sequence of numbers from that seed as a result! We are getting the same sequence because our starting seed number is always 5323.

In order to make our entire sequence randomized, we need some way to pick a seed that’s not a fixed number. The first answer that probably comes to mind is that we need a random number! That’s a good thought, but if we need a random number to generate random numbers, then we’re in a catch-22. It turns out, we really don’t need our seed to be a random number -- we just need to pick something that changes each time the program is run. Then we can use our PRNG to generate a unique sequence of pseudo-random numbers from that seed.

The commonly accepted method for doing this is to enlist the system clock. Each time the user runs the program, the time will be different. If we use this time value as our seed, then our program will generate a different sequence of numbers each time it is run!

C comes with a function called time() that returns the number of seconds since midnight on Jan 1, 1970. To use it, we merely need to include the ctime header, and then initialize srand() with a call to time(0).

Here’s the same program as above, using a call to time() as the seed:

Now our program will generate a different sequence of random numbers every time! Run it a couple of times and see for yourself.

Generating random numbers between a given range

Generally, we do not want random numbers between 0 and RAND_MAX -- we want numbers between two other values, which we’ll call min and max. For example, if we’re trying to simulate the user rolling a die, we want random numbers between 1 and 6 (pedantic grammar note: yes, die is the singular of dice).

Here’s a short function that converts the result of rand() into the range we want:

To simulate the roll of a die, we’d call getRandomNumber(1, 6).

What is a good PRNG?

As I mentioned above, the PRNG we wrote isn’t a very good one. This section will discuss the reasons why. It is optional reading because it’s not strictly related to C or C++, but if you like programming you will probably find it interesting anyway.

In order to be a good PRNG, the PRNG needs to exhibit a number of properties:

First, the PRNG should generate each number with approximately the same probability. This is called distribution uniformity. If some numbers are generated more often than others, the result of the program that uses the PRNG will be biased!

For example, let’s say you’re trying to write a random item generator for a game. You’ll pick a random number between 1 and 10, and if the result is a 10, the monster will drop a powerful item instead of a common one. You would expect a 1 in 10 chance of this happening. But if the underlying PRNG is not uniform, and generates a lot more 10s than it should, your players will end up getting more rare items than you’d intended, possibly trivializing the difficulty of your game.

Generating PRNGs that produce uniform results is difficult, and it’s one of the main reasons the PRNG we wrote at the top of this lesson isn’t a very good PRNG.

Second, the method by which the next number in the sequence is generated shouldn’t be obvious or predictable. For example, consider the following PRNG algorithm: num = num + 1. This PRNG is perfectly uniform, but it’s not very useful as a sequence of random numbers!

Third, the PRNG should have a good dimensional distribution of numbers. This means it should return low numbers, middle numbers, and high numbers seemingly at random. A PRNG that returned all low numbers, then all high numbers may be uniform and non-predictable, but it’s still going to lead to biased results, particularly if the number of random numbers you actually use is small.

Fourth, all PRNGs are periodic, which means that at some point the sequence of numbers generated will eventually begin to repeat itself. As mentioned before, PRNGs are deterministic, and given an input number, a PRNG will produce the same output number every time. Consider what happens when a PRNG generates a number it has previously generated. From that point forward, it will begin to duplicate the sequence between the first occurrence of that number and the next occurrence of that number over and over. The length of this sequence is known as the period.

For example, here are the first 100 numbers generated from a PRNG with poor periodicity:

112	9	130	97	64	
31	152	119	86	53	
20	141	108	75	42	
9	130	97	64	31	
152	119	86	53	20	
141	108	75	42	9	
130	97	64	31	152	
119	86	53	20	141	
108	75	42	9	130	
97	64	31	152	119	
86	53	20	141	108	
75	42	9	130	97	
64	31	152	119	86	
53	20	141	108	75	
42	9	130	97	64	
31	152	119	86	53	
20	141	108	75	42	
9	130	97	64	31	
152	119	86	53	20	
141	108	75	42	9

You will note that it generated 9 as the second number, and 9 again as the 16th number. The PRNG gets stuck generating the sequence in-between these two 9’s repeatedly: 9-130-97-64-31-152-119-86-53-20-141-108-75-42-(repeat).

A good PRNG should have a long period for all seed numbers. Designing an algorithm that meets this property can be extremely difficult -- most PRNGs will have long periods for some seeds and short periods for others. If the user happens to pick a seed that has a short period, then the PRNG won’t be doing a good job.

Despite the difficulty in designing algorithms that meet all of these criteria, a lot of research has been done in this area because of its importance to scientific computing.

rand() is a mediocre PRNG

The algorithm used to implement rand() can vary from compiler to compiler, leading to results that may not be consistent across compilers. Most implementations of rand() use a method called a Linear Congruential Generator (LCG). If you have a look at the first example in this lesson, you’ll note that it’s actually a LCG, though one with intentionally picked poor constants. LCGs tend to have shortcomings that make them not good choices for most kinds of problems.

One of the main shortcomings of rand() is that RAND_MAX is usually set to 32767 (essentially 15-bits). This means if you want to generate numbers over a larger range (e.g. 32-bit integers), rand() is not suitable. Also, rand() isn’t good if you want to generate random floating point numbers (e.g. between 0.0 and 1.0), which is often useful when doing statistical modelling. Finally, rand() tends to have a relatively short period compared to other algorithms.

That said, rand() is perfectly suitable for learning how to program, and for programs in which a high-quality PRNG is not a necessity.

For applications where a high-quality PRNG is useful, I would recommend Mersenne Twister, which produces great results and is relatively easy to use.

A note for Visual Studio users

The implementation of rand() in Visual Studio has a flaw -- the first random number generated doesn’t change much for similar seed values. This means that when using time() to seed your random number generator, the first result from rand() won’t change much in successive runs. This problem is compounded by calling getRandomNumber(), which compresses similar inputs into the same output number.

However, there’s an easy fix: call rand() once and discard the result. Then you can use rand() as normal in your program.

Random numbers in C++11

C++11 added a ton of random number generation functionality to the C++ standard library, including the Mersenne Twister algorithm, as well as generators for different kinds of random distributions (uniform, normal, Poisson, etc…). This is accessed via the <random> header.

Here’s a short example showing how to generate random numbers in C++11 using Mersenne Twister:

You’ll note that Mersenne Twister generates random 32-bit unsigned integers (not 15-bit integers like rand()), giving a lot more range. There’s also a version (std::mt19937_64) for generating 64-bit unsigned integers!

There’s so much functionality in <random> that it really warrants its own section. We’ll look to cover that in a future lesson in more detail.

5.10 -- std::cin, extraction, and dealing with invalid text input
Index
5.8 -- Break and continue

131 comments to 5.9 — Random number generation

  • hi Alex, it’s good to see you’ve put in something about random numbers,now I can make games with random numbers….
    thanks for the great tutorial alex

  • Pathik

    This code in visual c++ 2005 express edition gives this error at compile time:

    ‘error C2661: ‘time’ : no overloaded function takes 0 arguments’

  • diyon

    Hi, I’m new to C++. and would like to know how to write a programe to generate random numbers uniformly distributed between 0 and 1.
    Thank you,

    • rand() generates numbers between 0 and RAND_MAX. So to generate numbers between 0 and 1, simply divide the result of rand() by RAND_MAX (make sure to use a cast to cast the result to a double, otherwise you’ll get integer division).

      eg.

      Note that this will only generate numbers that are a multiple of 1/ RAND_MAX. If you need something with more granularity, you’ll have to use a different algorithm, like Mersenne Twister.

  • Abby

    Is it possible to create a random statement for a group of words that I come up with, not just random numbers?

    • Not directly. However, there are a couple of options:

      1) Put your words in an array, and then use a random number to index that array. I cover arrays in the next chapter, I think.
      2) Write a function that uses a switch statement to return a given word for an input number.

  • Dan

    Hey Alex, thanks for making the great tutorials.

    I’m wondering if there’s any way to generate 30 random numbers and store them in an array. I’m able to generate a random number and store it in an array, but whenever I try to access the array every single indexed number in it is the same random number. I’m thinking that this is perhaps because the random number is based on the system clock and all 30 numbers are created at the same time?

    • I don’t see any reason why what you are doing wouldn’t work. If you initialize the array using a loop like this:

      you should get a different number in each slot.

      If you’re not, then I suspect you’re either initializing your array incorrectly or your rand() really isn’t returning random numbers for some reason.

  • Markos

    Hi , thank you for this information , but i have a question. Is there a way that i can generate a random number between two ranges of numbers( like, i want to generate a random number that is in (0 to 200) or (400 to 1300) ).

    with best wishes

    • Josh Browning

      I’m not sure if there’s a better way to do this, but you could generate a random boolean (i.e. rand()%2) and then use an if statement to determine which range to use. So, for example, if the random boolean is 0, then pick a random number between 0 to 200, else pick one between 400 to 1300. If you want one range to show up more often than the other, just pick a random integer first (maybe from 0 to 9) and have only 0 and 1 lead to the range 400 to 1300. Then, 80% of the time you will have a random number between 0 to 200, and 20% between 400 to 1300 (if your RNG is good).

  • once we needed to use the actual eth packet numbers and some system data to generate a rand number in an embedded device…

    in some cases it’s really difficult to generate (so-called)random numbers.

  • Why do you need to declare nSeed with the static key word with this? I don’t see the point in needing its file scope.

    • baldo

      nSeed is a local variable for the PRNG function. The static keyword has another meaning when used for local variables. In this case, nSeed variable “retains it’s value even after the scope in which it has been created has been exited! Fixed duration variables are only created (and initialized) once, and then they are persisted throughout the life of the program.” See more here: Lesson 4.3. the static keyword

      • sunoval

        baldo, Thanks for your useful comments. The use of “static” is definitely the core component of the whole algorithm here. I was trying to figure out the function of static here for a while although I have learned Lesson 4.3. before. Thanks

  • Hank

    I have an issue with your mapping implementation (the GetRandomNumber function). It’s fine for small ranges like the dice example, but for larger target ranges, you can get serious uniformity issues. For example, let’s say you want a random number between 0 and 21,844 (about 2/3 of rand()’s RAND_MAX). With GetRandomNumber, for numbers that already fall in the target range, you get a 1-to-1 mapping (0 becomes 0, 1 becomes 1, etc.), then for the rest of the domain of rand(), the output essentially starts over at 0 and overlaps onto the first half of the target range. Therefore, you’re twice as likely to get a number between 0 and 10,922 as you are to get one between 10,923 and 21,844, when the probabilities should be equal! Thus I’d recommend instead just using *, /, + and - to convert (probably need to cast to a float first, then truncate).

  • I dont understand in your first example how

    is going to give us a number between 0 and 32767.Isnt % supposed to give the remainder of the division?And since nSeed is always the same number,since we do the same arithetic operations with it each time,wont the remainder be the same,resulting in the return value being the same?

    I hope you understand my question ;P

    • A1) Remainder can’t be bigger than divider. That explains the range.

      A2) Since we used static keyword, compiler doesn’t reset the variable after using it. Seed changes everytime.

      nSeed = (8253729 * nSeed + 2396403)

      First time, nSeed is 5323. Second time, it becomes the result of that operation. Third time, it changes again and this goes on.

  • .......

    Any way to create a random char?

    • You can use ASCII numbers and use static_cast to make them into characters

    • You can use ASCII numbers like Mike said.


      //Setting the range between 97 and 122 (97 = a and 122 = z)
      int RandomNumber = ((rand() % 26) + 97);

      // I assigned the random created ASCI number to a char variable
      // If you just want to print, use "cout << static_cast<char>(RandomNumber)"
      char RandomCharacter = static_cast<char>(RandomNumber);

  • Alex, you have a v good understanding of the field which you deal with. Thanks for all these detailed tutorials. Keep up the good work.
    Thankyou Alex.

  • Jjtricky

    I really don’t get this line:

    Surely, this would break the line after the fourth number, as:

    Therefore, the line is ended

  • Jack Sparrow II

    My question is how do I generate random numbers without generating the same ones multiple times?

    • Wolf

      I’m wondering the same thing.

      I need to write a program that randomizes a deck of cards, but I can’t be assigning the same random value to multiple cards in the deck.

      • Alex

        Great questions. In this case, you don’t want random numbers, you want a random ordering of a fixed set of objects.

        I’d tackle the card shuffling exercise like this:
        * Give each card a unique identifier (an integer or an enumerator).
        * Create an array of length 52.
        * Add the cards to the array (in order is fine).
        * Use a for loop to step through each card in the array. For each card, pick a random number between 0 and 51, and swap that card with the card at the randomly picked location.

        That should give you a decent shuffle.

  • THE TERMINATOR

    HELP!!! MY PRNG KEEPS PRINTING “4 8 15 16 23 42” NO MATTER WHAT I DO!!!!!

  • Just a quick question, what will happen with the function time() in 69 years from 1970 (year 2039). Will every program in the world that uses time() crash? I imagine no one tought this would be an issue in 1970 xD.

    • Alex

      time() will experience overflow, and programs will think it’s 1970 again.

      I think this will be a much bigger deal than Y2K turned out to be.

  • cubbi

    While commonly used in bad textbooks, the % operator should NOT be used to limit the range of values produced by std::rand(): it results in a non-uniform distribution. If you must use std::rand(), divide by RAND_MAX (cast to double).

  • Dragon

    Where do you put the code that keeps the application up for more than a millisecond?

  • coyote

    Just as a heads up, I noticed that when I ran the last program for random numbers I did get output that was as high as: 2033645517. This is on a linux box so it might be that different systems/compilers have different defaults for the RAND_MAX constant.

  • So I tried to make a random number generator between 1 and 13. And at the end when you guess correctly it shows how many times you guessed. It is funny though because it seems whenever I enter 3 into the program it comes out blank and ends the program.

    Here is the code:
    #include
    #include
    #include

    using namespace std;

    int counter=0;

    unsigned int getRandom(int nHigh, int nLow){
    return (rand() % (nHigh - nLow + 1)) + nLow;
    }
    int main(){
    int x, y;
    x=1;
    y=13;
    int nGuess;

    cout << "Enter a gues between 1 and 6: " <> nGuess;
    getRandom(y,x);
    if (nGuess < getRandom(y,x)){
    cout << "too low try again" < getRandom(y,x)){
    cout << "Too high try again" << endl;
    counter=counter+1;
    main();
    }
    else if (nGuess == getRandom(y,x)){
    cout << "Congradulations!" << endl;
    cout << "Number of Guesses: " << counter << endl;

    }
    system ("PAUSE");
    return 0;
    }

  • mori

    If you are on a unix/linux system you should use /dev/random or /dev/urandom, those do have more “physical” randomness, mouse movements, etc.

  • dice3000

    srand(time(0)) - this kind of inital seed values is absolutely bad, because it is a timestamp (amount of seconds since 1970.01.01). So if you are calling your main function multiple times in a row, your random numbers will follow the same pattern, since the seed values only changes by a couple of seconds, and that is very small change to a number 1375984340 (2013.03.08 20:52). What wee need for a seed value is computer microtime (microseconds) of current time, because its changes rapidly

    • Alex

      You should only seed your random generator once per program. How close two seeds are together shouldn’t matter unless your PRNG is very poor. Even using rand(), which isn’t great, using two consecutive seed numbers (e.g. 5 vs 6) will generate vastly different sequences of numbers.

      The main problem with using a time-based seed is that a clever adversary could change the system clock to make your program run the same way every time. This could allow the adversary to game the system, or allow them to compromise some bit of crypto or security.

      But hopefully if that matters, you’re reading more advanced articles before attempting to write such a program. This is an introductory article.

  • Philorbust

    How to have the random generator only generate even numbers? Great site!

  • Jay

    Gives a complier warning in Xcode for Mac, says precision may be lost. I’m guessing its because of the different data types between what the srand() function expects and the time(0); function provides.

    To get round this issue I did this:

    Is there a better way?

    • Alex

      time() returns a value of type time_t, whereas srand() expects a value of type unsigned int.

      time_t is a typedef that doesn’t specify what the underlying data type is. Often it’s an unsigned int, but it could be something else. Many unix systems use a signed integer (either 32 or 64 bits).

      Using a static_cast as you have is a good way to tell the compiler “I meant to do this, so stop warning me about it”.

      Although you could lose precision by converting a 64-bit signed integer to a 32-bit unsigned integer, it’s unlikely to matter too much because it’s the low bits that change every second, and those are the ones that get preserved in the conversion.

  • Jatn

    I wanted to find out a correlation between the seed you provide and number rand () generates , so i made a program that forms a table of seed you give and the random number it forms with that seed and here it is .

    It worked well and i noticed that consecutive random numbers differ by either 3 or 4 . So i modified my program so that it clearly shows the difference between
    consecutive random numbers .Here is the code

    It also ran fine but unfortunately i couldn’t see any pattern of 3’s and 4’s in difference column .Sadly i can’t copy things from the ".exe" file. Try it guys and please let me know if u see a pattern.

  • C++ newbie

    Who the heck came up with "midnight on Jan 1, 1970"????  It’s so arbitrary…

    Why not 1971, or February 3?  Why Jan 1, 1970, 12:00 AM!?!?!?!?!?!??!?!?

    • Alex

      It seems arbitrary because… it was arbitrary. 🙂

      Unix engineers needed to pick a date and time to start counting from, so they picked the earliest time in the decade they were in. You can read more about it on the Wikipedia article on Unix time.

  • Todd

    Typos.

    "Take games for example -- Without (without) random events,"

    "take the result of rand() can (and) convert it"

    "The length of this sequence is known as the period" (you need to add a period (ironically) to the end of this sentence)

    "The PRNG gets stuck generating the sequence in-between these two 9’s repeatedly: 9-130-97-64-31-152-119-86-53-20-141-108-75-42-(repeat)." (this is a different sequence than the one in the table to which you’re referring)

    "because of it’s (its) importance to scientific computing."

  • Methos

    Is there any way to characterize how ‘good’ a PRNG has to be to not be observable in for example, a game?

    The only example I can think of was from one of the online guides for Final Fantasy 12 where you could (simplifying greatly) force a rare chest drop by loading the game, performing a fixed number of actions, and then using a particular spell that didn’t make random calls (it always teleported enemies ‘away’).

    If I had to guess, someone cracked the code of the game to find that, as I can’t imagine stumbling on that behavior as a player.

    If we’re writing a RNG from scratch, for whatever reason, I wonder if we might be better off making multiple time calls-once to get a seed, then say time()%X where we pick X to set a maximum number of times the scratch RNG function runs before a value is called to be used. I would think that would play havok with the period of the thing, so long as you had picked values (which if I understand the wikipedia link, it’s possible) that cover the range.

    • Alex

      > Is there any way to characterize how ‘good’ a PRNG has to be to not be observable in for example, a game?

      I think it really depends on how often you’re calling the PRNG, and whether the results are visible to the user. The more you call it and the more visible the results are, the more likely a bad PRNG will produce noticeably bad results.

      A good PRNG shouldn’t benefit from throwing a certain number of results away before using a result. Every result should be sufficiently randomized. However, a bad PRNG could (in theory) actually become less random by doing such a thing.

      • Methos

        Yeah, I guess it’s easier to understand the bad cases than the good.

        If I have a PRNG with period 30000, and my ‘solution’ is to skip 9 results (which seems at first to be the most obvious thing to do if you’ve ever shuffled cards until everyone at the table is happy), all I’ve done is give myself a PRNG with period 3000.

        I suspect, thinking a little further it wouldn’t have to be that good at all for entertainment purposes. I can see how for academic purposes, you’re going to want a very large period if your model requires a billion PRNG calls as fast as your hardware will allow, but not so much in a dungeon crawler, where all the user sees are:
        -Is there a monster in this area (yes/no)?
        -What kind is it (maybe three or four options in a given area)?
        -Does one attacker hit the other (yes/no) and for how much damage (could be d6+2 for something like a tabletop game)?
        -Loot (could be a check of a table like in Skyrim or fixed with one item possible like Dragon Warrior)?

        So, in 30 seconds of gameplay, that’s around 10-20 calls, or about 13 hours before you’d expect the sequence to repeat. Which is probably adequate for a single player game (where on will surely have moved on in that timeframe) but not for say, an MMO (where people grind endgame content for the better part of a year).

        • Alex

          Well, if the dungeons themselves are randomly generated, that’s a lot of randomization calls at the time the dungeon is generated.

          The period is also relevant only if you’re calculating the same results in the same order. For example, random value 55 (on a scale of 0 to 99) might map to “Orc” when generating a monster, but “dagger” when generating an item. If it’s used once in each context, even though the PRNG is repeating values, the results will be different because the context is different. So practically speaking, as long as you’re not using the randomized results in a homogenous manner, you could probably get away with a smaller period.

          • Methos

            I wrote the following mainly out of curiosity about the ‘bad’ numbers mentioned for LCGs. I just thought I’d post it in the event anyone might want to experiment a bit like I did. What I’m doing is simulating a four sided die roll and visually checking that the guys at wikipedia were right about full periods (they unsurprisingly appear to be, but it helps to actually see it) and checking via the tally array how often the same face is rolled consecutively (should be .25). Small or very large numbers were probably going to be bad (and were) but I was surprised how bad numbers for a around half of m turned out (a=65, c=1, m=128 gave a tally total of .5).

            A warning is probably warranted that if you don’t follow the rules for picking a, c, and m, there’s a chance your iterated value winds up in an endless loop that never hits 1 again.

  • cpplx

    yay! the infamous RNG.
    id say the optional tag shall be removed from the last part of the lesson for it is the most important part of it

  • SuperSiggson

    Isn’t something as simple as

    perfectly enough when generating random numbers of fairly trivial importance? I think its a lot easier to learn (and understand).

    • SuperSiggson

      Meant

      To clarify, if

      it would produce random numbers between (including) 250 and 284.

    • Alex

      Yes, and in fact, the previous version of the lesson used that algorithm.

      However, as some readers correctly noted, that algorithms really only works well when range is small. For larger ranges, you run into problems where lower numbers can occur more often than higher numbers. Consider a range of 10000 and min value of 0. If the random number picked is between 0 and 29999, the returned result is evenly distributed between 0 to 9999. However, if the random number picked is between 30000 and 32767, the returned result is only between 0 and 2767. That means the numbers between 0 and 2767 have a 33% greater chance of occurring than numbers between 2768 and 9999. That’s a pretty bad skew.

      The current algorithm is a little more complicated, but it also works for any range, small or large. For that reason, it’s a better solution, despite the small amount of additional complexity.

  • Edward

    Does anyone know how to solve the error below when running the Mersenne Twister example in Code::Blocks? I’m using version 13.12.

    terminate called after throwing an instance of ‘std::runtime_error’
      what():  random_device::random_device(const std::string&)

    This application has requested the Runtime to terminate it in an unusual way.
    Please contact the application’s support team for more information.

    • Alex

      Apparently MinGW doesn’t have an implementation of random_device on Windows. That’s annoying.

      Fortunately seeding with the system clock still works.

      On Code::Blocks, replace:

      with:

  • Chris

    I remember seeing another method for changing the range of numbers you get out of the rand() function using the remainder:

    cout << rand()%6 + minvalue << endl;

    This prints numbers from minvalue to minvalue + 5 (range of 6). I found this method a lot easier to understand than the one you used above, so I was wondering if there is a reason you picked that method instead of this one?

  • a good distribution uniformity and  good dimensional distribution is some of the things
    that may make a random generator less random than what you would find in real life.
    For instance:
    If you throw a dime, there is a big chance in reality, that you get 5 heads in a row.
    Real randomness is much cruder than a generator could possibly conceive, imo.

    Since computers calculate everything, one could generate random numbers by inputting
    values that the computer does not control.
    The system time/mouse movement is a good start.
    Or the amount of people that visited a dungeon in an mmo.

    Maybe there is the option to ping a list of random IP addresses in France (i hear, France has bad internet) ?
    Since many applications are connected to the internet, it should be
    possible to use this connectivity to actually create real random figures.

  • You state that one should seed only once, but with this type of a more
    volatile input, in the likes that I previously mentioned,
    could it be possible to start multiple new seeds over a period of time ?

    PS.
    Nice to see the ease by which one can leave a reply,
    instead of the need to create an account and such.
    This generates a low threshold to have a proper conversation. Nicely done 😉

  • Methos

    Another stake in the heart of LCG, I was just considering the rules for getting a full period (following the wikipedia link), which are easily obeyed if the modulus m is a power of two, and it occurs to me that if m is even and a and c are odd, the seed value alternates odd, even in a fixed way.

    Which is kind of bad if you’re generating a bool by taking seed % 2 as menitioned in the comments above.

  • Methos

    Also, alternating odd and even guarantees if your generating digits (seed%10) you will never see repeated digits, which is more bad.

    I looked up how the mersenne twister works, and while I understand what they did, I don’t get why it works with the period they claim, so I don’t know that I would use it (which is my version of sour grapes as my poor Vista machine won’t run the current compilers that use it), so I borrowed parts of what they did to write a PRNG I’m happy with (and it wouldn’t surprise me at all to find someone else has done this in the process of getting to where they are).

    So I’ve solved a number of problems I’ve been having with this code.
    Seeding with time(0)*time(0) corrects an issue where if I just printed out the seed values 20 at a time, the last few weren’t all that different from one run of the program to the next a few seconds later (this is less apparent the smaller your modulo is).

    For a given pair time(0) and shuffle, you have a pseudorandom sequence with period 4 billion (2^32), squared. There are 4 billion, cubed (divided by 2 because 2*shuffle will overflow for half the values of shuffle) such sequences. But allowing these to vary creates a situation where in order to repeat a period you would either have to make 2^(31+) calls to the function in less than a second (and I’m not entirely sure seed would have its original value at 2^31 calls, but eventually it would at some greater power of 2) or a century from now when time(0) returns the same value find your self back at the original seed with shuffle = 0 (This seems sufficiently unlikely and far off not to worry). So this PRNG for all intents and purposes has infinite period.

    The part I borrowed, sort of, is taking half the long long seed and XOR-ing it with the other half (they swap chunks of bits and XOR with fixed values). For a fixed pair of time(0) and shuffle, the period is full, which means each value of bottomseed will be mapped one to one to result by the available topseed values. Which is awkward to type, but what happens is result has period 4 billion squared, and takes each of its possible values 4 billion times. A quick check of the output of this function verified that it was not alternating odd even.

    With a range of 4 billion, the extra probability for small values in a specified range is going to be negligable. If for some reason I wanted a random value within a couple of orders of magnitude of 4 billion, I think you’ve taught us enough in the section on classes that we could write a bigger version of long long (addition is easy, modulo is free, multiplication is likely a pain, and division is…fortunately not required for this algorithm!).

    PRNGtest() checks a sequence of single digits thus generated. If you want to run it, you should alter the maximum count value I’ve tried to highlight, starting at 100 and adding a 0 each time to get a feel for what’s going on. The results are not perfect, in that sequences of repeated digits are a little slow to appear (specifically those you’d expect to see 10 of for a given count maximum value), but they seem generally good to me. Aside from that largest case, the rates of occurrence appear to be right around .1^N for a given length N as I’d expect, but not precisely that (and which digits occur more varies from one run to the next).

    • Methos

      In lines 56 to 59, those should obviously be tabs and newlines. They’re in my code, but somewhere between copy/pasting and editing the comment, my backslashes seem to have been eaten.

  • You forgot to include <ctime> here.

    " Taht(Taht should be That) number will be a pseudo-random integer between 0 and RAND_MAX, a constant in cstdlib that is typically set to 32767"

    This lesson is a bit tougher…

    I can’t understand the algorithm used here.

    • Methos

      He’s trying to get random ints without using the modulo operation because of the way it throws off probabilities for the low end of returned values as described in earlier comments.

      rand()        spits out a value between 0 and RAND_MAX.
      *fraction     gives a value between 0 and 1 - fraction
                    (Because he added 1 in the denominator, you can’t get 1 as a result here)
      *(max-min+1)  gives a value between 0 and (max-min+1)*(1-fraction)
      +min          gives a value between min and (max+1)-(max-min+1)*fraction
      static_cast throws away everything but the integer part.

      So, as desired, the minimum value is min. Because fraction is nonzero and positive, max+1 is not a possible result. So long as (max-min+1)*fraction is less than 1, max is the maximum result. However, for large values of max-min (namely RAND_MAX or larger) max isn’t possible either, though in that case you should already know rand() is inadequate.

      Unfortunately, it doesn’t actually solve the probability problem. Consider RAND_MAX = 15,
      min = 0, max = 10. Using the modulo(11) algorithm, the results 0, 1, 2, 3, 4 are twice as likely as 6, 7, 8, 9, 10. Under this method, rand() returns map to algorithm returns as follows
      rand() = 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
      return = 0  0  1  2  2  3  4  4  5  6   6   7   8   8   9  10
      As you can see, the values of 0, 2, 4, 6, and 8 now have twice the probability of appearing as the other values. Now, this method is better in the sense that the expectation of the modulo method is 4.0625 vs 4.6875 for this method (it should be 5), which is to say the extra results are more spread out. But the problem we were trying to address is one of the pigeonhole principle. Namely unless we are fortunate in our choices of min, max, and (someone else’s choice) of RAND_MAX, there are always going to be ‘extra’ results from rand() that have to go somewhere.

      The best solution for that, I think, is to write a PRNG that has a very large equivalent of RAND_MAX (the one I wrote above returns an int [RAND_MAX equivalent of 2^32-1] for this reason, and could go bigger if I was willing to write a class bigger than long long). You will still have the extra results, but because so many results are potentially available, the probability the extra ones represent is vanishingly small.

  • lalit

    I have tried generate random numbers between 2 digits but not getting the correct output.. Can you plz tell me where am I going wrong?

    • Alex

      You need to initialize srand() with something that changes every time you run your program, like the system clock. the rand() function inside getRandomNumber() is dependent upon srand() being called properly first. Since you haven’t done that, the results of getRandomNumber() aren’t random, which means srand() isn’t get a random parameter, which means future calls to getRandomNumber() aren’t random either. 🙂

  • Quang

    typo "dice" not "die", it sounds deadly Alex!
    by the way awesome tutorial, thank you so much!

  • Pat

    I copy and pasted the getRandomNumber function. For some reason whenever I call the function the value returned is always what my min value is. So if I call getRandomNumber(1,6); I will always get 1 as the return value. I’m not sure why this is happening but any help would be great.

    • Alex

      Did you remember to seed your random number generator using srand()?

      • Pat

        Yes you were totally right. But now it consistently produces the answer 4 with the following code and I can’t quite figure out why:

        #include "stdafx.h"
        #include <iostream>
        #include <cstdlib> // for rand() and srand()
        #include <ctime> // for time()

        unsigned int getRandomNumber(int min, int max)
        {
            srand(static_cast<unsigned int>(time(0)));

            static const double fraction = 1.0 / (static_cast<double>(RAND_MAX)+1.0);
            

            return static_cast<int>(rand() * fraction * (max - min + 1) + min);
        }

        int main()
        {
                std::cout << getRandomNumber(1, 6);
            return 0;
        }

        • Alex

          srand() should only be called once at the beginning of your program. Move the srand() line to the top of main().

          There’s also a bug with Visual Studio where the first random number isn’t very random if you use the system clock to seed. Call rand() once and ignore the result before using it again.

          • Sandro

            I use Code::Blocks. Got this problem of getting the same value. To fix it, I assigned the first rand() number to a useless variable:

            Otherwise I only get the number six.

  • Nemesh

    im having trouble with using the <randon> rd()
    i tried to use your function that restrict the random numbers generated  to that of a die (1-6) and it will generate up to 7.
    using the <cstdlib> and using rand() will work fine and generate numbers betwwen 1-6. what is the diffrence? whats causing the problem?

  • Annibale

    Just a comment from a mathematician … nice game: you always win 😀

  • Annibale

    I can not understand why you write the random number generator like this

    and not like this

    Do I miss something? Thanks in advance!

    • Alex

      Nope, I made a mistake. It should be as you suggest. I’ve updated the lesson.

      • Mike

        I believe that the current version of getRandomNumber(int min, int max) is not correct either. Suppose that min = 1 and max = 6. Here’s the current code:

        The problem is with number 6. We expect to get it with the probability of 1/6. But this function will only return 6 when rand() == RAND_MAX. By default RAND_MAX is 32767, so the probability of rand() == RAND_MAX is 1/32767, which is much less than expected 1/6.

        I believe that this would work correctly:

        Here the result of rand() is projected onto the range of 1 to 7 (includes 1, but never reaches 7), and static_cast<int> returns 1 to 6 with about equal probability.

        Alex, your tutorial is great beyond any measure, thank you so much!

        • Alex

          Upon reflection, I agree. The only difference is that the + 1 should be outside the static_cast since RAND_MAX+1 could overflow an integer before being converted to a double.

          • Matthieu B.

            Maybe you should add a short explanation as to why there is a + 1 in the denominator of fraction and another + 1 after (max - min) in the lesson.
            Now that I read what Mike wrote I understand what’s going on, but I was confused at first and I think that this may confuse other readers as well.

            • Alex

              This is something I continually struggle with. It’s interesting, but how this works isn’t really germane to the content the lesson is trying to get across. I try not to let things get bogged down in minutia. So this is something that I’ll probably leave as a topic for discussion in the comments section for interested readers.

  • Dagmawi Eshete

    Can someone help me with this? Write, compile, and run a C++ program that generates 200 random integers in between 1 to 200. Some of the randomly generated integers may be repeated as well. Next sort the randomly generated 200 integers using the Selection sort algorithm. Store the sorted numbers in an output data file. Then prompt the user to enter an integer in between 1 to 200 (inclusive) out of the keyboard as a key element. Next find out the location of the key element in the sorted array using both the binary search and the sequential search algorithms. The result returned by binary search and the sequential search algorithm may vary for repeated elements inside the sorted array. This is acceptable. Please write out the results returned by the binary search and the sequential search algorithms to the output data file.

    • Alex

      What part do you need help with? Random number generation is discussed in this chapter. Arrays are discussed in lesson 6.1, and selection sort in lesson 6.4. Binary search is part of the quiz for chapter 7. Sequential search is covered in lesson 6.3. File I/O is covered in chapter 13.

      • Dag

        I just need help with how to generate a random number. IDK how to start it

        • Alex

          In the section “PRNG sequences and seeding”, there’s an example showing one way to generate random numbers. Since you need to generate random numbers between 1 and 200, you can use the getRandomNumber() function in place of rand().

  • This comment is a mistake: the value is between 0 and 32766 (as 32767 % 32767 would produce a 0).
    Apparently, the code should have actually been:

  • Aymen

    Spelling mistake when defining what rand does, ‘taht’ instead of ‘that’

    Loving these tutorials - maybe you should do a graphical version!

  • Shiva

    Typo.

    Example #1 last comment:
    "….start a new column (should be row)"

    Really, really useful lesson. Sparked a lot interest. I’ve used Math.random() in JavaScript, and ever since wondered (and wanted to know) how such functions worked.

    But I do wonder how this section came about in Control Flow. I mean, apart from using a loop to print 100 random numbers, the concept of PRNG does not seem to build directly upon the concept of control-flow statements the way the topics in this tutorial usually do. May be there’s a reason I’m unaware of.

    Anyway thanks for the lesson, Alex. 🙂

    • Alex

      Typo fixed. It seemed like the appropriate time to introduce the lesson, and I didn’t want to have a chapter just for one lesson. So I tacked it on to the end of the flow control chapter. No relationship intended to be implied.

  • Elpidius

    Hey Alex,

    The result of your first example is not what the output should be. This is because the results you’ve provided are only the case when your return is expression is:

    However since you’ve altered the return expression (after Alex Qyoun-ae pointed out a mistake), you’ve forgotten to alter the output of example 1. It’s not a big deal, but I thought I’d let you know for consistency.

    The ouput of:

    is actually:
    23070    27857    22756    10839    27946
    11613    30448    22070    1011     etc…

    Also, you have a typo in the second-to-last paragraph:
    "…generates random 32-bit unsigned integers (not 15-bit integers like rand())…"

    It should read "not 16-bit integers like…"

    • Alex

      Thanks for the correction on the program output.

      I intentionally used the term “15-bit integers” because rand() is generally set to generate a number between 0 and 32767, which only requires 15 bits to store.

  • Elpidius

    Hey Alex,

    Under the section "Generating random numbers between a given range", instead of using your getRandomNumber() function, what if I did this instead?

    Since all other numbers outside the range of 1-6 are ignored its periodicity would be reduced. But would this program still have uniform distribution?

    • sharaf

      I did same. but in my cases even in 1000 integers i didn’t get my required number printed.

    • Alex

      It would have a uniform distribution no better than rand(), but most likely worse. Consider a hypothetical case where rand() generated the following sequence over and over:
      7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30.

      Although this is clearly missing numbers 0-6, it’s somewhat uniform otherwise. However, you’ll get no results with your program! Now, odds are things won’t be this bad in reality, but due to the relatively low periodicity of rand() you could end up having some numbers never generated using this method! It’s also really inefficient.

  • May

    Hello I’m teacher Mhay from Bulacan, this is my assignment in my masteral. I want to ask for your help please. Thanks in advance and God bless

  • Simanchal

    Well.  please help me to figure out the predictable outputs of this and please explain me how each line is happening… please help

    int main()
    {
    int guess[4]={100, 50, 200, 20};
    int taker= random(2) + 2;
    for(int chance =0; chance<taker; chance++)
    cout<<guess[chance]<<‘#’;
    }

  • Daniel Casellas

    Hello Alex!
    First of all THANKYOU for this tutorials. I am a Systems Engineer (C# and Java are my languages) and now im looking into C++ because i want to get into game programming (As a hobby, but you never know).

    I wanted to point out a small typo " if we’re trying to simulate the user rolling a die" (It should be dice).

    I know it is unimportant for the purpose of the lecture, but this tutorial is just so great that its a small way to contirbute.

    Thanks again!

    • Alex

      Actually, die is correct. Die is the singular of dice. In this case, we’re just rolling a single die, not a pair of dice.

      • Daniel Casellas

        Oh Thanks Alex, My bad. English isn’t my main lang.

        By the way, do you know where can i learn about directX and HLSL? (Any tutorial or resource as good ad this).

  • An Amazing feature of c++ , more amazing was your way of describing this feature to us.Yes i am talking about you Alex bro….. Thank you for such amazing tutorials.

    I was just reading the comments and i noticed your reply to Dan, in the reply you used a word ‘slot’ from which i got upon a idea of creating a slot machine game (:p) . And after some minutes i write all the code in the IDE  for my first ever game in c++ …. But at the time of compiling i was hopeless with the number of errors it gave to me,i tried to fix them but all in vain then i rewrote the whole code again. This time i have few errors which i copied and pasted into google and somehow figured out the i have to use ‘ time.h ‘ header, after adding the header i compiled the code again and this time it compiles without any problem.So i am sharing my code here maybe it help someone someday…:p

        

    Alex bro is there any newbie mistakes i have done in writing this code or is there any better method to write it?

    • Alex

      Cool idea! This would definitely benefit from some functions. I’d make pulling the slot a function.

      Also, in the case where the user enters 2, new random numbers aren’t chosen, but the slot still gets pulled because your if/else statement is broken.

  • J3ANP3T3R

    "std::random_device rd; // Use a hardware entropy source if available, otherwise use PRNG"

    o_O ?

    • Alex

      Some machines have sources of hardware that can be used for random number generation. A compiler can, in theory, leverage these. But in most cases, it’ll just a PRNG.

  • J3ANP3T3R

    is it safe to use srand(static_cast<unsigned int>(time(0))); on each iteration of a loop instead of declaring the value once for the whole program ?

    • Alex

      Not only is it _not_ safer, it’s actually a bad thing do use srand more than once. It will mess up the randomness of your programs if you call it more than once.

  • Darren

    For a (very) thorough and (very) (very) technical article on pseudo random number generation and entropy in C++ have a look here at http://www.pcg-random.org/

  • Rafael

    Hi Alex:
    Is there a way to specify a range (like in the getRandomNumber example) using Mersenne Twister instead of rand()? My compiler is Visual Studio 2015

  • Pip

    Hi Alex,

    Please could you elucidate why in the getRandomNumber function the denominator of the static const fraction is (RAND_MAX + 1) and not just (RAND_MAX)?

    • Alex

      rand() generates numbers between 0 and 32,767 (2^15 - 1), so RAND_MAX is set to 32,767. However, that’s 32,768 unique value (because 0 is a valid value). We use RAND_MAX+1 to represent the 32,768 unique values, to ensure our distribution isn’t skewed.

      • Pip

        Ah, and is it also to ensure that (rand() * fraction * (max - min + 1) + min) (line 7) is always slightly less than max + 1, so that the return value, being cast to type int, cannot exceed max?

        • Alex

          Yep! The goal is to map random numbers [0, RAND_MAX] to [min, max] in such a way that every number in min,max has an even a chance as possible of being mapped to. Since any number between [min, min+1) maps to min, we need to ensure that all numbers in the range [max, max+1) map to max -- that means we need to generate numbers just short of max+1, so they can get truncated to max.

  • Hugh O'Brien

    Hi Alex!

    I was wondering if you could explain the following code in a bit more detail. Is this just a basic algorithm used to randomise our number patterns? Can this code be something different is what I’m asking?

    • Alex

      rand() always generates numbers between 0 and RAND_MAX. If we want to simulate rolling a 6-sided die, generating a number between 0 and RAND_MAX doesn’t really help. What we really want is to generate a number between 1 and 6. This algorithm generates a random number between 0 and RAND_MAX, and then scales it down as evenly as possible so the final result falls between values min and max (inclusive).

  • reznov

    Under the header Generating random numbers between a given range you talk about rolling a "die". I understand you mean dice there but I thought I’d give you a heads up.

    • Alex

      Die is the singular of dice. Although in modern grammar, dice is now sometimes accepted for singular use, if I used dice to mean a singular die, just as many readers would tell me that I should have used die instead. Heh, there’s no winning here.

  • Ayush Sharma

    there are different library functions like math.max() for finding out the greater of two numbers,
    isnt there a similar library function to generate random numbers between two given numbers?

    • Alex

      You would think so, but there isn’t prior to C++11. C++11 sort of added this capability as part of the random number functionality (you can define a std::uniform_int_distribution between min and max). But you have to create a new generator every time you want to change your min or max. I’m not sure how performant this is.

Leave a Comment

Put C++ code inside [code][/code] tags to use the syntax highlighter