PRNG do generowania liczb z n dokładnie ustawionymi bitami

12

Obecnie piszę kod do generowania danych binarnych. W szczególności muszę wygenerować liczby 64-bitowe przy określonej liczbie ustawionych bitów; dokładniej, procedura powinna zająć około i zwrócić pseudolosową 64-bitową liczbę z dokładnie bitami ustawionymi na , a resztą ustawioną na 0. $0 < n < 64$ $n$ $1$

Moje obecne podejście obejmuje coś takiego:

Wygeneruj pseudolosowy 64-bitowy numer . $k$
Policz bity w , przechowując wynik w . $k$ $b$
Jeśli , wyprowadza ; w przeciwnym razie przejdź do 1. $b = n$ $k$

To działa, ale wydaje się nieeleganckie. Czy istnieje jakiś algorytm PRNG, który może generować numery z bitów ustawionych bardziej elegancko niż to? $n$

algorithms information-theory coding-theory pseudo-random-generators Koz Ross
źródło

12

Potrzebujesz losowej liczby od 0 do . Problem polega zatem na przekształceniu tego w wzór bitowy. ${ 64 \choose n } - 1$

Jest to znane jako kodowanie wyliczeniowe i jest to jeden z najstarszych wdrożonych algorytmów kompresji. Prawdopodobnie najprostszy algorytm pochodzi od Thomasa Covera. Opiera się na prostej obserwacji, że jeśli masz słowo o długości bitów, gdzie ustawione bity to w najbardziej znaczącej kolejności bitów, to pozycja tego słowa w porządku leksykograficznym wszystkich słów o tej właściwości jest: $n$ $x_k \ldots x_1$

\sum_{1 \leq i \leq k} (\binom{x_{i}}{ja})

$\sum_{1 \le i \le k} { x_i \choose i}$

Na przykład 7-bitowe słowo:

ja (0000111) = (\binom{2)}{3)}) + (\binom{1}{2)}) + (\binom{0}{1}) = 0

$i(0000111) = { 2 \choose 3 } + {1 \choose 2 } + {0 \choose 1} = 0$

ja (0001011) = (\binom{3)}{3)}) + (\binom{1}{2)}) + (\binom{0}{1}) = 1

$i(0001011) = { 3 \choose 3 } + {1 \choose 2 } + {0 \choose 1} = 1$

ja (0001101) = (\binom{3)}{3)}) + (\binom{2)}{2)}) + (\binom{0}{1}) = 2)

$i(0001101) = { 3 \choose 3 } + {2 \choose 2 } + {0 \choose 1} = 2$

...i tak dalej.

Aby uzyskać wzór bitowy z porządkowej, po prostu dekodujesz kolejno każdy bit. Coś takiego w języku C:

uint64_t decode(uint64_t ones, uint64_t ordinal)
{
    uint64_t bits = 0;
    for (uint64_t bit = 63; ones > 0; --bit)
    {
        uint64_t nCk = choose(bit, ones);
        if (ordinal >= nCk)
        {
            ordinal -= nCk;
            bits |= 1 << bit;
            --ones;
        }
    }
    return bits;
}

Pamiętaj, że ponieważ potrzebujesz tylko współczynników dwumianowych do 64, możesz je wstępnie obliczyć.

Cover, T., Enumerative Source Encoding . Transakcje IEEE dotyczące teorii informacji, tom IT-19, nr 1, styczeń 1973.

Pseudonim
źródło

Piękny i elegancki! Kodowanie numeryczne wygląda na coś bardzo przydatnego - czy są na to jakieś dobre zasoby (najlepiej w formie podręcznika)?

Koz Ross,

Czy to faktycznie daje lepszą wydajność w praktyce? (Oczywiście zależy to od szybkości RNG.) Jeśli nie, nie ma sensu używać bardziej złożonego kodu.

Gilles „SO - przestań być zły”,

1

@Giles Zinterpretowałem to jako pytanie informatyczne, ponieważ jest to cs.se. Podałem tylko kod źródłowy, ponieważ zdarzyło mi się, że znajdowałem go w implementacji tablicy RRR. (Zobacz, na przykład, alexbowe.com/rrr, aby uzyskać wyjaśnienie, co to znaczy.)

pseudonim

1

@Gilles Aby odpowiedzieć na twoje pytanie, wdrożyłem zarówno moją naiwną metodę, jak i metodę podaną przez Pseudonim w Forth. Naiwna metoda, nawet przy użyciu bardzo prostego xorshift PRNG, wymagała około 20 sekund na liczbę , podczas gdy metoda Pseudonim była niemal natychmiastowa. Użyłem do tego tabel wstępnie obliczonych dwumianów.

Koz Ross,

1

@KozRoss Jeśli wygenerujesz n liczb bitowych i poszukasz liczb z zestawem k bitów, byłyby one dość rzadkie, gdyby k było daleko od n / 2; to by to wyjaśniało.

gnasher729

3

Bardzo podobny do odpowiedzi Pseudonim uzyskanej w inny sposób.

Całkowitą liczbę dostępnych kombinacji można uzyskać metodą gwiazdek i słupków , więc będzie to musiało wynosić . Całkowita liczba 64-bitowych liczb, z których próbujesz próbkować swoją liczbę, byłaby oczywiście znacznie wyższa. $c=\binom{64}{n}$

Potrzebujesz zatem funkcji, która może poprowadzić cię od pseudolosowej liczby , od do , do odpowiedniej kombinacji 64-bitowej. $k$ $1$ $c$

Trójkąt Pascala może ci w tym pomóc, ponieważ wartość każdego węzła reprezentuje dokładnie liczbę ścieżek od tego węzła do pierwiastka trójkąta, a każda ścieżka może być reprezentowana przez jeden z ciągów, których szukasz, jeśli wszystkie skręty w lewo są oznaczone , a każdy skręt w prawo . $1$ $0$

Niech będzie liczbą bitów pozostałych do ustalenia, a liczbą pozostałych do użycia. $x$ $y$

Wiemy, że , i możemy go użyć, aby poprawnie określić następny bit liczby na każdym kroku: $\binom{x}{y}=\binom{x-1}{y}+\binom{x-1}{y-1}$

$\mathtt{while}\;\;\; x>0$

$\quad \mathtt{if}\;\;\; x>y$

$\qquad \mathtt{if}\;\;\;k>\binom{x-1}{y}: \;\;\;s \leftarrow s\; + \mathtt{"1"}, \;k\leftarrow k-\binom{x-1}{y}, \;y \leftarrow y-1$

$\qquad \mathtt{else}:\; \;s \leftarrow s\; + \mathtt{"0"}$

$\quad \mathtt{else}: \;\;s \leftarrow s\; + \mathtt{"1"}, \;y \leftarrow y-1$

$\quad x \leftarrow x-1$

André Souza Lemos
źródło

2

Inną dość elegancką metodą jest użycie bisekcji, jak opisano w tej odpowiedzi na przepełnienie stosu . Pomysł polega na zachowaniu dwóch słów, z których jedno ma co najwyżej k bitów, a drugie co najmniej k bitów, i używa losowości, aby przesunąć jedno z nich w kierunku uzyskania dokładnie k bitów. Oto kod źródłowy, który to ilustruje:

word randomKBits(int k) {
    word min = 0;
    word max = word(~word(0)); // all 1s
    int n = 0;
    while (n != k) {
        word x = randomWord();
        x = min | (x & max);
        n = popcount(x);
        if (n > k)
            max = x;
        else
            min = x;
    }
    return min;
}

Zrobiłem porównanie skuteczności różnych metod i ten jest zwykle najszybszym chyba k jest znany jako bardzo małe.

Falk Hüffner
źródło

0

Możesz wykonać następujące czynności:

1) Wygeneruj liczbę losową, od do . $k$ $1$ $64$

2) Ustaw th na . $k$ $0$ $1$

3) Powtórz kroki 1 i 2 razy $n$

$A[]$ to tablica bitowa ze wszystkimi s $64$ $0$

for(i=1 to n)
{
    k=ran(1,65-i) % random number between 1 and 65-i
    for(x=1;x<65;x++)
    {
        if(A[x]==0)k--;
        if(k==0)break;
    }
    A[x]=1;
}

Użytkownik nie znaleziony
źródło

Proza wydaje się nie pasować do twojego kodu? Kod nigdy nie przypisuje 1s do tablicy. Również nie wydaje się generować jednolitego rozkładu (a nawet liczb, które spełniają ograniczenia), gdy kzderza się wiele s

Bergi

@Bergi Ya zapomniałem linii ... dodał ją teraz. Obsługiwane jest wielokrotne zderzenie k. Patrz, pierwsza liczba jest wybierana między 1 a 64, druga między 1 a „pozostałą” 63. Więc pomija 1 podczas liczenia ... zobaczlinia. I to jest jednolita dystrybucja.

A [x] = 1

$A[x]=1$

i f (A [x] == 0) k - -;

$if(A[x]==0)k--;$

Nie znaleziono użytkownika

Ach, rozumiem teraz. Algorytm prozy nie wspominał o pominięciu.

Bergi,

@ArghyaChakraborty Czy używasz tam indeksowania 1?

Koz Ross,

@KozRoss Zacznij od tego, co się stanie, jeśli (oczywiście będą zerami) Więc sprawdzi i uzyska znaczenieco daje . Ustawia poza pętlą. Więc tak, jest to indeksowanie 1. Żeby było 0 oparty wszystko co musisz zrobić, to zmienić wewnętrzna celu

i = 1, k = 1

$i=1,k=1$

A

$A$

A [1] == 0

$A[1]==0$

t r u e

$true$

k - -;

$k--;$

k = 0

$k=0$

A [1] = 1

$A[1]=1$

f o r

$for$

(x = 0; x < 64; x + +)

$(x=0;x<64;x++)$

User Not Found

PRNG do generowania liczb z n dokładnie ustawionymi bitami

Odpowiedzi: