兰德功能在C

Question

可能重复：
What common algorithms are used for C's rand()?

是怎样的C库中定义rand函数。 rand函数的时间复杂度是多少？如果有人可以提供rand函数的源代码（我不需要它的实现，但是源代码），那会很好。 Thanx

Answer 1

它是实现定义的，每个库作者可以自由实现它，因为他们认为合适。但是，它们通常基于linear congruential generators，这是有限的。 POSIX标准给出了一个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; 
} 

我不知道你所说的“时间复杂度”在这里的意思; “时间复杂度”通常指的是运行时间相对于n（其中n是输入的大小或某物）的变化。

Answer 2

这是O（1）复杂性，没有输入，它返回一个int。

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

int rand() 
{ 
    return (((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff); 
}