蘭德功能在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); 
}