-1

Possible Duplicate:
What common algorithms are used for C's rand()?

How is the rand function defined inside the c library. What is the time complexity of rand function. If someone can provide the source code for rand function(I don't need its implementation but the source code) it would be great. Thanx

Community
  • 1
  • 1
Prateek
  • 161
  • 2
  • 3
  • 9
  • 2
    Did you even try to find an answer on your own? The first hit when I google "c rand" is [this SO question](http://stackoverflow.com/questions/1026327/what-common-algorithms-are-used-for-cs-rand). – eaj Dec 28 '11 at 16:54
  • The source code should be available for whatever run-time library is included with your C compiler. Have you checked it out? This is very implementation-dependent, even if someone as smart as Oli can give you some general guidelines or educated guesses. – Cody Gray - on strike Dec 28 '11 at 16:58

2 Answers2

1

It's O(1) complexity, there is no input and it returns one int.

From http://www.jbox.dk/sanos/source/lib/stdlib.c.html :

int rand()
{
  return (((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
}
cyborg
  • 9,989
  • 4
  • 38
  • 56
0

It's implementation-defined, each library author is free to implement it as they see fit. However, they are normally based on linear congruential generators, which are somewhat limited. the POSIX standard gives an example implementation:

static unsigned long next = 1;

/* RAND_MAX assumed to be 32767 */
int myrand(void) {
    next = next * 1103515245 + 12345;
    return((unsigned)(next/65536) % 32768);
}

void mysrand(unsigned seed) {
    next = seed;
}

I'm not sure what you mean by "time complexity" here; "time complexity" normally refers to how the run-time varies with respect to n (where n is the size of the input or something).

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680