15

I'm new to programming.

I want to know exactly what rand() does.

Searching only yields examples on its usage. But none explain each step of how the function generates a random number. They treat rand() as a blackbox.

I want to know what rand() is doing; each step.

Is there a resource that will allow me to see exactly what rand() does? This is all open source stuff isn't it? I'll settle for the disassembly, if there's no source.

I know it returns a random number, but how does it generate that number? I want to see each step.

Thank you.

Adrift
  • 58,167
  • 12
  • 92
  • 90
BBedit
  • 7,037
  • 7
  • 37
  • 50
  • 5
    What system do you care about? There are presumably almost as many implementations as there are environments. – Carl Norum Sep 23 '13 at 22:18
  • Your compiler may have the runtime library source available. The implementation can probably be found there. – Retired Ninja Sep 23 '13 at 22:20
  • 2
    rand uses a pseudo-random generator, so reading up on the theory behind PRNGs will be more enlightening than any piece of source code – Uku Loskit Sep 23 '13 at 22:20
  • [This paper](http://www.cems.uwe.ac.uk/~irjohnso/coursenotes/ufeen8-15-m/p1192-parkmiller.pdf) is a classic, not terribly hard to understand, and it covers the basics, though it is primitive by modern standards. (But so is `rand()`.) – Hot Licks Sep 23 '13 at 22:22

7 Answers7

17

Here is the current glibc implementation:

/* Return a random integer between 0 and RAND_MAX.  */
int
rand (void)
{
  return (int) __random ();
}

That's not much help, but __random eventually calls __random_r:

/* If we are using the trivial TYPE_0 R.N.G., just do the old linear
   congruential bit.  Otherwise, we do our fancy trinomial stuff, which is the
   same in all the other cases due to all the global variables that have been
   set up.  The basic operation is to add the number at the rear pointer into
   the one at the front pointer.  Then both pointers are advanced to the next
   location cyclically in the table.  The value returned is the sum generated,
   reduced to 31 bits by throwing away the "least random" low bit.
   Note: The code takes advantage of the fact that both the front and
   rear pointers can't wrap on the same call by not testing the rear
   pointer if the front one has wrapped.  Returns a 31-bit random number.  */

int
__random_r (buf, result)
     struct random_data *buf;
     int32_t *result;
{
  int32_t *state;

  if (buf == NULL || result == NULL)
    goto fail;

  state = buf->state;

  if (buf->rand_type == TYPE_0)
    {
      int32_t val = state[0];
      val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
      state[0] = val;
      *result = val;
    }
  else
    {
      int32_t *fptr = buf->fptr;
      int32_t *rptr = buf->rptr;
      int32_t *end_ptr = buf->end_ptr;
      int32_t val;

      val = *fptr += *rptr;
      /* Chucking least random bit.  */
      *result = (val >> 1) & 0x7fffffff;
      ++fptr;
      if (fptr >= end_ptr)
    {
      fptr = state;
      ++rptr;
    }
      else
    {
      ++rptr;
      if (rptr >= end_ptr)
        rptr = state;
    }
      buf->fptr = fptr;
      buf->rptr = rptr;
    }
  return 0;

 fail:
  __set_errno (EINVAL);
  return -1;
}
Carl Norum
  • 219,201
  • 40
  • 422
  • 469
15

This was 10 seconds of googling:

...

I was gonna list the actual search, but seeing this is clearly a dupe, I'll just vote as dupe

Community
  • 1
  • 1
sehe
  • 374,641
  • 47
  • 450
  • 633
  • 2
    Ok. I'm very new to programming (~3 days!) so I didn't know what to search for. I found the implementation that I need to study here: http://bioen.okstate.edu/Home/prashm%20-%20keep/prashant/VS.NET%20setup%20files/PROGRAM%20FILES/MICROSOFT%20VISUAL%20STUDIO%20.NET/VC7/CRT/SRC/RAND.C – BBedit Sep 23 '13 at 22:34
  • @user2071506 Oh well, I googled `GNU libc rand`, literally. It came up with the SO links as well. None of the links were from outside the top ~12 hits. :/ – sehe Sep 23 '13 at 22:37
  • @sehe `GNU libc rand` is hard. `sourcecode for rand() (C++)` literally copied from the title got me nice results too. – Bartek Banachewicz Sep 23 '13 at 22:38
4

You can browse the source code for different implementations of the C standard.

The question has been answered before, you might find what you're looking for at What common algorithms are used for C's rand()?

That answer provides code for glibc's implementation of rand()

Community
  • 1
  • 1
Johan Henriksson
  • 687
  • 3
  • 10
2

The simplest reasonably good pseudo-random number generators are Linear Congruential Generators (LCGs). These are iterations of a formula such as

X_{n+1} = (a * X_n  +  c) modulo m

The constants a, c, and m are chosen to given unpredictable sequences. X_0 is the random seed value. Many other algorithms exists, but this is probably enough to get you going.

Really good pseudo-random number generators are more complex, such as the Mersenne Twister.

Kevin A. Naudé
  • 3,992
  • 19
  • 20
2

I guess, THIS is what you are looking for. It contains the detailed explanation of random function, and simple C program to understand the algo.

Edit:

You should check THIS as well. A possible duplicate.

Community
  • 1
  • 1
Zeeshan
  • 2,884
  • 3
  • 28
  • 47
2

Well, I believe rand is from the C standard library, not the C++ standard library. There is no one implementation of either library, there are several.

You could go somewhere like this page to view the source code for glibc, the c library used on most Linux distributions. For glibc you'd find it in source files under stdlib such as rand.c and random.c.

A different implementation, such as uClibc might be easier to read. Try here under the libc/stdlib folder.

AndASM
  • 9,458
  • 1
  • 21
  • 33
0

Correct me if I'm wrong, but although this answer points to part of the implementation, I found that there is more to rand() used in stdlib, which is from [glibc][2]. From the 2.32 version obtained from here, the stdlib folder contains a random.c file which explains that a simple linear congruential algorithm is used. The folder also has rand.c and rand_r.c which can show you more of the source code. stdlib.h contained in the same folder will show you the values used for macros like RAND_MAX.

/* An improved random number generation package. In addition to the standard rand()/srand() like interface, this package also has a special state info interface. The initstate() routine is called with a seed, an array of bytes, and a count of how many bytes are being passed in; this array is then initialized to contain information for random number generation with that much state information. Good sizes for the amount of state information are 32, 64, 128, and 256 bytes. The state can be switched by calling the setstate() function with the same array as was initialized with initstate(). By default, the package runs with 128 bytes of state
information and generates far better random numbers than a linear
congruential generator. If the amount of state information is less than 32 bytes, a simple linear congruential R.N.G. is used. Internally, the state information is treated as an array of longs; the zeroth element of the array is the type of R.N.G. being used (small integer); the remainder of the array is the state information for the R.N.G. Thus, 32 bytes of state information will give 7 longs worth of state information, which will allow a degree seven polynomial. (Note: The zeroth word of state
information also has some other information stored in it; see setstate for details). The random number generation technique is a linear feedback shift register approach, employing trinomials (since there are fewer terms to sum up that way). In this approach, the least significant bit of all the numbers in the state table will act as a linear feedback shift register, and will have period 2^deg - 1 (where deg is the degree of the polynomial being used, assuming that the polynomial is irreducible and primitive). The higher order bits will have longer periods, since their values are also influenced by pseudo-random carries out of the lower bits. The
total period of the generator is approximately deg*(2deg - 1); thus doubling the amount of state information has a vast influence on the
period of the generator. Note: The deg*(2
deg - 1) is an approximation only good for large deg, when the period of the shift register is the dominant factor. With deg equal to seven, the period is actually much longer than the 7*(2**7 - 1) predicted by this formula. */

Nav
  • 19,885
  • 27
  • 92
  • 135