Duże liczby losowe w C

W dniu wczorajszym na forum 4programmers odbyła się bardzo ciekawa dyskusja na temat losowania dużych liczb w C z użyciem funkcji rand(). Wnioski z tej dyskusji mogą się przydać każdemu.

Funkcja rand() zwraca wynik w postaci dodatniej liczby typu signed int. Jest to istotne, gdyż:

  • int w zależności od platformy ma 2 bajtu lub 4 bajty
  • dodatnia liczba typu signed ma zawsze 0 na najstarszym bicie, więc de facto może przyjmować tylko połowę wartości, niż by to mogło się wydawać z liczby bitów
  • reasumując: na platfornie z sizeof(int)==2 może przyjmować wartości od 0 do 32767 (7FFFh), a na platformach z sizeof(int)==4 od 0 do 2147483647 (7FFFFFFFh)

Bardzo często konieczne jest wylosowanie większej liczby i sporo programistów zbyt lekko wykonuje sobie jakieś mnożenie lub dodawanie, aby otrzymać takową liczbę. Jest to bardzo zwodnicze i nie należy tego robić. Przykładowo, jeżeli ktoś chciałby wylosować liczbę od 0 do 1000000, mógłby wpaść na pomysł, aby zrobić to tak:

int mul = 1000000 / 32767;
int rand = mul * rand();

BŁĄD! Proszę zauważyć, że ten kod będzie losować tylko wilokrotności liczby 30. Ktoś inny mógłby zastosować bardziej wysublimowane rozwiązanie i zrobić to tak:

unsigned int most = rand();
unsigned int least = rand();
unsigned int random = ((most << 16) + least) % 1000000;

BŁĄD! Rand() daje zawsze 0 na najstarszym bicie, więc de facto daje tylko 15 bitów efektywnych. Powyższy kod pozostawia zawsze 2 bity wyzerowane. Dobrym rozwiązaniem jest poniższy kod:

long unsigned int = (rand() <<17 ) ^ (rand()<<N) ^ (rand());
gdzie za N można dać sobie dowolną liczbę z przedziału domkniętego <2,7>.