wygenerować losową 64-bitową liczbę całkowitą

Question

Potrzebuję twojej pomocy i proszę dać mi radę. Od programowania perły wiem, że aby wygenerować losowy 30 bitową liczbę całkowitą powinniśmy napisać to tak:

RAND_MAX*rand()+rand() 

Ale co mogłem zrobić, aby nie generować 30, ale 64-bitowa liczba całkowita zamiast losowych? Myślę, że jest to bardzo nieefektywna metoda, jeśli pomnożę dwie 30-bitowe liczby całkowite, a następnie pomnożę ponownie 4-bitową liczbę całkowitą, więc jakiej metody powinienem użyć? Używam teraz popcount_1 innej metody dla 64-bitowej i chciałbym przetestować ją na losowych liczbach całkowitych (ja również mierzę czas, który każdy z nich wykonuje, aby wykonać zadanie)

Answer 1

To może być rozwiązanie, bez mnożenia:

r30 = RAND_MAX*rand()+rand() 
s30 = RAND_MAX*rand()+rand() 
t4 = rand() & 0xf 

res = (r30 << 34) + (s30 << 4) + t4 

Answer 2

Losowy 64-bitowy int jest w zasadzie 64 losowe bity interpretowane jako int.

Wypełnij tablicę bajtów o długości 8 bajtami losowymi (see here for how) i zinterpretuj je jako int (see here for how).

Answer 3

Jeśli opcja jest boost, można użyć boost random.

Answer 4

Po pierwsze, mam wątpliwości co do rozwiązania publikowanych na 30 bitowym całkowitej. RAND_MAX samo w sobie może być wartością 31-bitową, a RAND_MAX * rand() + rand() prawdopodobnie przepełni się, tworząc niezdefiniowane zachowanie (aw praktyce wartości ujemne).

Jeśli potrzebujesz wartość większą niż gwarantowanego minimum RAND_MAX lub o to chodzi, że nic nie jest znacząco mniejszy niż RAND_MAX, jedynym rozwiązaniem będzie wykorzystanie kolejnych połączeń do rand() i połączyć wartości, ale musisz to zrobić ostrożnie, a następnie sprawdź poprawność wyników. (. Większość implementacje rand() użytku liniowych przystających generatorów, które jednocześnie wystarczające dla niektórych zadań, nie są szczególnie dobre w tym przypadku) W każdym razie, coś jak:

unsigned 
rand256() 
{ 
    static unsigned const limit = RAND_MAX - RAND_MAX % 256; 
    unsigned result = rand(); 
    while (result >= limit) { 
     result = rand(); 
    } 
    return result % 256; 
} 

unsigned long long 
rand64bits() 
{ 
    unsigned long long results = 0ULL; 
    for (int count = 8; count > 0; -- count) { 
     results = 256U * results + rand256(); 
    } 
    return results; 
} 

(Kod w rand256 ma na celu wyeliminowanie skądinąd nieuniknione stronniczość uzyskać podczas mapowania RAND_MAX wartości do 256 wartości)

Answer 5

Ogólny rozwiązanie.

template <unsigned long long I> struct log2 { 
    static const int result = 1 + log2<I/2>::result; 
}; 
template <> struct log2<1> { 
    static const int result = 0; 
}; 

template <typename UINT> UINT genrand() { 
    UINT result = 0; 
    int bits = std::numeric_limits<UINT>::digits; 
    int rand_bits = log2<RAND_MAX>::result; 
    while (bits > 0) { 
    int r = rand(); 
    while (r >= (1<<rand_bits)) r = rand(); // Retry if too big. 
    result <<= rand_bits; 
    result += r; 
    bits -= rand_bits; 
    } 
    return result; 
} 

Zastosowanie: unsigned long long R = genrand<unsigned long long>();.

Licznik bits śledzi liczbę bitów, które są jeszcze potrzebne.

Answer 6

'Zwraca całkowitą pseudolosową wartość od 0 do RAND_MAX (w tym 0 i RAND_MAX).' - http://en.cppreference.com/w/cpp/numeric/random/rand

Powinieneś użyć RAND_MAX + 1 (to jak generowanie cyfry po cyfrze, a następnie konwertowanie jej do bazy 10) zamiast RAND_MAX. W ten sposób możesz generować liczby z jedną, dwiema, trzema itd. Cyframi w bazie RAND_MAX + 1 (prawdopodobnie z wiodącymi zerami) i konwertować je do bazy 10 i uzyskać dowolnie duże liczby.

Wszystko, co uzyskasz powyżej MAX_VALUE, może zostać odrzucone, a wciąż masz 1/(MAX_VALUE + 1) prawdopodobieństwo otrzymania każdego numeru.

Należy pamiętać, że ta metoda może chwilę potrwać, zwłaszcza jeśli żądana wartość MAX_VALUE jest dużo mniejsza niż maksymalna wartość, którą można uzyskać przed odrzuceniem liczb, które nie są pożądane, jako oczekiwaną liczbę kroków do uzyskania losowego liczba w [0, MAX_VALUE] z tym algorytmem wynosi: (MAX_OBTAINABLE_VALUE + 1)/(MAX_VALUE + 1)