Monday, November 1, 2010

PRNGs (Pseudo-Random Number Generator)

Computers cannot truly generate random numbers, as computers are simply mechanisms that react to actions that are enacted upon them. In order to compensate for this, to generate a random number computers use a PRNG (pseudo random number generator). PRNGs can generate seemingly random numbers rather effectively.

One way to generate a random number in C is to use the rand() function, which is lies within the standard library of C. Here is an example:

#include <stdio.h> /* included for printf */
#include <stdlib.h> /* included for rand */

int main(void)
{
  int i;

  for (i = 0; i < 10; i++)
    printf("%i\n", rand());

  return 0;
}

Depending on your compiler, the output of this program will output ten numbers. However, this program will always output the same ten numbers in the same order. I've learned that the GCC compiler will have the rand() function return a value with an upper bound of 2,147,483,647 (232-1), compared to upper bounds of 32,767 (216-1) from most other compilers.


In order to have this program output different numbers each time it is run, you need to do what is called seeding the PRNG. Seeding will affect the sequence in which the rand() function begins outputting numbers. In order to seed the rand() function, you use srand(). Here is an example:

#include <stdio.h> /* included for printf */
#include <stdlib.h> /* included for rand */

int main(void)
{
  int i;

  srand(1)
  for (i = 0; i < 10; i++)
    printf("%i\n", rand());

  return 0;
}

This seeded the PRNG with the integer 1, and will now output ten different numbers than the last program. Although, this still doesn't solve our problem; how do we randomly seed the PRNG? In order to do so, you can use the time() function. The time() function will return the number of seconds elapsed since Jan 1st 1970. This is the method of randomly seeding that DigiPen has shown their Freshman incoming students. Example:

#include <stdio.h> /* included for printf */
#include <stdlib.h> /* included for rand */

int main(void)
{
  int i;

  srand(time(0));
  for (i = 0; i < 10; i++)
    printf("%i\n", rand());

  return 0;
}

Now this program will produce a different set of numbers every time it is run. Although, what if you wanted to produce a random number within a specific range? You could use the modulo operator, like so:

#include <stdio.h> /* included for printf */
#include <stdlib.h> /* included for rand */

int main(void)
{
  int i;

  srand(time(0));
  for (i = 0; i < 10; i++)
    printf("%i\n", rand() % 10 + 1); //Random int from 1-10

  return 0;
}

Although I've been told this is error-prone and tedious, and it is much preferred to create your own wrapper function around rand().

int randomInt(int low, int high)
{
  return (rand() % (high - low + 1) + low);
}

2 comments:

  1. interesting, i didn't know computers couldn't truly randomize numbers.

    ReplyDelete
  2. Yeah, a PRNG will output a number, depending on what you input. If you use the same input each time you run the algorithm (in this case the algorithm being the rand() function) then you'll get the exact same output. So, you use the time() function to get different input every second.

    ReplyDelete

Note: Only a member of this blog may post a comment.