0

I know how rand() and srand() are related to each other, and I know how should I use them, but their mechanism of working was really interesting for me and I wanted to know How they really work?!, but I couldn't find any special thing.

So this is my question: What is going on in deep inside of rand() and srand() and how does it produce a random number? (If it's really producing a random one!) Does it have any special mathematics calculation or any special algorithm? what is it?

Aykhan Hagverdili
  • 28,141
  • 6
  • 41
  • 93
Farbod Ahmadian
  • 728
  • 6
  • 18
  • 1
    Rand is implementation defined, although it's typically implemented as a linear congruential generator. However, well defined generators can be found in the standard header. And are probably more worth looking at as rand is well known to _typically_ produce low quality random numbers. – George Sep 14 '19 at 08:49
  • If you want to know "*How they really work?!*" take a look at your standard library implementation – Aykhan Hagverdili Sep 14 '19 at 09:27
  • See https://stackoverflow.com/questions/24005459/implementation-of-the-random-number-generator-in-c-c/24005617 for what the standard says, and what most implementations do. Be prepared to be severely disillusioned. – Deduplicator Sep 14 '19 at 09:44
  • 1
    @George -- a bit hypertechnical, but the implementation of `rand()` is **implementation-specific**, not **implementation-defined**. In the C and C++ standards, "implementation defined" means that a conforming implementation must document what it does. That's not required for `rand()`. – Pete Becker Sep 14 '19 at 12:48

1 Answers1

4

First of all, rand() does not produce random numbers. It is a Pseudo Random Number Generator.

rand() is typically implemented as linear congruential generator. You can think that there is a variable seed, which holds previous state of generator, then rand() just uses this seed to generate next number in a sequence.

Something like this (very rough implementation, just to explain the idea):

const int RAND_MAX = 32767; // usually it is 2^15, but actually implementation specific
const int a = ...;          // implementation specific
const int c = ...;          // implementation specific
int seed = 0;               // current generator state

void srand(int _seed) {
  seed = _seed;
}

int rand() {
  int r = (a * seed + c) % RAND_MAX;
  seed = r;
  return r;
}

It will create the same sequence for the same initial state (seed value).

warchantua
  • 1,154
  • 1
  • 10
  • 24
  • 1
    "`rand()` is implemented as linear congruential generator", usually true but it's not a standard requirement. – George Sep 14 '19 at 09:16
  • 1
    Off-by-one error -- `RAND_MAX` is the maximum value that can be generated, so the remainder should be `RAND_MAX + 1`. Also, "usually it is 2^15" is, I think, overstated; it has to be at least 2^15, but the simplest implementation is to just use the hardware directly, which drops overflow bits, i.e., with 32-bit registers RAND_MAX is most naturally 2^31. +1. – Pete Becker Sep 14 '19 at 12:45