Specjalny prosty generator liczb losowych

Question

Jak utworzyć funkcję, która przy każdym wywołaniu generuje losową liczbę całkowitą? Ta liczba musi być jak najbardziej losowa (zgodnie z uniform distribution). Dopuszczalne jest użycie tylko jednej zmiennej statycznej i co najwyżej 3 podstawowe etapy, przy czym każdy etap obejmuje tylko jeden podstawowych operacji arytmetycznych arity 1 lub 2.

Przykład:

int myrandom(void){ 
    static int x; 
    x = some_step1; 
    x = some_step2; 
    x = some_step3; 
    return x; 
} 

Podstawowe operacje arytmetyczne + , -,% i, nie, xor lub, lewe przesunięcie, prawe przesunięcie, mnożenie i dzielenie. Oczywiście żadna z rand(), random() lub podobnych rzeczy nie jest dozwolona.

Answer 1

liniowy przystający Generator rzecz jest jednym z najstarszych i najprostszych metod:

int seed = 123456789; 

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

Ony nieliczne wskazówki z podstawowych operacji arytmetycznych, to co potrzebne.

pamiętać, że ten algorytm działa dobrze tylko jeśli a, c i m wybierane są w sposób szczególny!

Aby zapewnić możliwie najdłuższy okres sekwencji C i m powinna być względnie pierwsze, A-1 powinna być podzielna przez czynniki-m a także do 4 jeżeli m jest podzielna przez 4.

niektórych przykładach wartości przedstawiono w Wikipedia: np ANSI C dla niektórych kompilatorów proponuje m = 2^32, a = 1103515245 i c = 12345

Answer 2

Możesz rzucić okiem na this. To daleki od bycia "idealnym" generatorem liczb losowych, ale spełnia moje wymagania, o ile widzę.

Here można znaleźć dodatkowe informacje na temat generowania liczb losowych.

Answer 3

Funkcja Boost ma bardzo ładną bibliotekę liczb losowych, a kod źródłowy jest dostępny, więc możesz spróbować sprawdzić i zastosować to, czego potrzebujesz (np. Wyciąć i wkleić).

Answer 4

Oto funkcja o rozkładzie równomiernym w całym zakresie int:

int rand() 
{ 
    static int random = 0; 
    return random++; 
} 

Answer 5

Jeśli piszę man rand, mogę czytać możliwy przykład, podany w POSIX.1-2001, za wdrożenie rand() i srand(). Zobacz np. here. Jeśli potrzebujesz czegoś bardziej wyrafinowanego, spójrz na GNU Scientific Library; możesz oczywiście pobrać kod i zobaczyć implementacje.

Answer 6

Używam tego

SUBROUTINE GNA(iiseed) 
    USE Variaveis 
    parameter (ia=843314861,ib=453816693,m=1073741824, r231=1./2147483648.) 
    INTEGER :: iiseed 

    iiseed = ib + ia*iiseed 
    if (iiseed.lt.0) iiseed = (iiseed+m) + m 
    RndNum = iiseed*r231 

END SUBROUTINE GNA 

Duży zysk losowości można osiągnąć bez spędzać więcej czasu obliczeniowego stworzenie generatora liczb losowych dla każdego połączenia generatora liczb losowych wykonany w programie.

To jest bardzo dobra sztuczka!

Answer 7

public long randomLong() { 
    x ^= (x << 21); 
    x ^= (x >>> 35); 
    x ^= (x << 4); 
    return x; 
} 

ziarno nie może być 0. Źródło: http://www.javamex.com/tutorials/random_numbers/xorshift.shtml#.VlcaYzKwEV8

Dodatkowe informacje w wiki: https://en.wikipedia.org/wiki/Xorshift