Metodo più efficiente per generare un numero casuale con un numero fisso di bit impostato

Question

Devo generare un numero casuale, ma deve essere selezionato dall'insieme di numeri binari con un numero uguale di bit impostati. Per esempio. scegliere un valore di byte casuale con esattamente 2 bit impostati ...

00000000 - no 
00000001 - no 
00000010 - no 
00000011 - YES 
00000100 - no 
00000101 - YES 
00000110 - YES 
... 

=> Set of possible numbers 3, 5, 6... 

Si noti che questo è un insieme semplificato di numeri. Pensa di più sulla falsariga di "Scegli un numero a 64 bit casuale con esattamente 40 bit impostati". Ogni numero dal set deve essere ugualmente suscettibile di sorgere.

Answer 1

Eseguire una selezione casuale dall'insieme di tutte le posizioni di bit, quindi impostare tali bit.

Esempio in Python:

def random_bits(word_size, bit_count): 
    number = 0 
    for bit in random.sample(range(word_size), bit_count): 
     number |= 1 << bit 
    return number 

risultati dell'esecuzione della sopra 10 volte:

0xb1f69da5cb867efbL 
0xfceff3c3e16ea92dL 
0xecaea89655befe77L 
0xbf7d57a9b62f338bL 
0x8cd1fee76f2c69f7L 
0x8563bfc6d9df32dfL 
0xdf0cdaebf0177e5fL 
0xf7ab75fe3e2d11c7L 
0x97f9f1cbb1f9e2f8L 
0x7f7f075de5b73362L 

Answer 2

dire il numero di bit da impostare è b e la dimensione della parola è w. Vorrei creare un vettore v di lunghezza w con i primi valori b impostati su 1 e il resto impostato su 0. Quindi solo shuffle v.

Answer 3

Ecco un'altra opzione che è molto semplice e abbastanza veloce nella pratica.

choose a bit at random 
if it is already set 
    do nothing 
else 
    set it 
    increment count 
end if 

Ripetere finché il conteggio è uguale al numero di bit che si desidera impostare.

Questo sarà solo lento quando il numero di bit che si desidera impostare (chiamarlo k) è più della metà della lunghezza della parola (chiamarlo N). In tal caso, utilizzare l'algoritmo per impostare invece N - k bit e quindi capovolgere tutti i bit nel risultato.

Scommetto che il tempo di esecuzione previsto qui è abbastanza buono, anche se sono troppo pigro/stupido per calcolarlo proprio adesso. Ma posso vincolarlo come meno di 2 * k ... Il numero previsto di lanci di una moneta per ottenere "teste" è due, e ogni iterazione qui ha una probabilità migliore di 1/2 di riuscire.

Answer 4

Se non si ha la comodità di Python random.sample, si potrebbe fare questo in C utilizzando il classico algoritmo di campionamento sequenziale:

unsigned long k_bit_helper(int n, int k, unsigned long bit, unsigned long accum) { 
    if !(n && k) 
    return accum; 
    if (k > rand() % n) 
    return k_bit_helper(n - 1, k - 1, bit + bit, accum + bit); 
    else 
    return k_bit_helper(n - 1, k, bit + bit, accum); 
} 

unsigned long random_k_bits(int k) { 
    return k_bit_helper(64, k, 1, 0); 
} 

Il costo di cui sopra sarà dominato dal costo di produzione del numeri casuali (vero anche nelle altre soluzioni, anche). Puoi ottimizzarlo un po 'se hai un buon numero di batch: ad esempio, dal momento che sai che i numeri casuali saranno in intervalli decrescenti, potresti ottenere i numeri casuali per n tramite n-3 ottenendo un numero casuale nell'intervallo. 0..(n * (n - 1) * (n - 2) * (n - 3)) e quindi estraendo i singoli numeri casuali:

r = randint(0, n * (n - 1) * (n - 2) * (n - 3) - 1); 
rn = r % n; r /= n 
rn1 = r % (n - 1); r /= (n - 1); 
rn2 = r % (n - 2); r /= (n - 2); 
rn3 = r % (n - 3); r /= (n - 3); 

il valore massimo di n è presumibilmente 64 o 2 , in modo che il valore massimo di questo prodotto è certamente inferiore a 2 . Infatti, se hai usato un prng a 64 bit, potresti estrarre fino a 10 numeri casuali. Tuttavia, non farlo a meno che non si sappia che il prng che si usa produce bit casuali indipendentemente.

Answer 5

Ho trovato una soluzione elegante: dicotomia casuale.

idea è che in media:

• e con un numero casuale viene divide per 2 il numero di bit impostati,
• o è l'aggiunta del 50% di bit impostati.

codice C per compilare con gcc (per avere __builtin_popcountll):

#include <assert.h> 
#include <stdint.h> 
#include <stdio.h> 
#include <stdlib.h> 
/// Return a random number, with nb_bits bits set out of the width LSB 
uint64_t random_bits(uint8_t width, uint8_t nb_bits) 
{ 
    assert(nb_bits <= width); 
    assert(width <= 64); 
    uint64_t x_min = 0; 
    uint64_t x_max = width == 64 ? (uint64_t)-1 : (1UL<<width)-1; 
    int n = 0; 

    while (n != nb_bits) 
    { 
     // generate a random value of at least width bits 
     uint64_t x = random(); 
     if (width > 31) 
      x ^= random() << 31; 
     if (width > 62) 
      x ^= random() << 33; 

     x = x_min | (x & x_max); // x_min is a subset of x, which is a subset of x_max 
     n = __builtin_popcountll(x); 
     printf("x_min = 0x%016lX, %d bits\n", x_min, __builtin_popcountll(x_min)); 
     printf("x_max = 0x%016lX, %d bits\n", x_max, __builtin_popcountll(x_max)); 
     printf("x  = 0x%016lX, %d bits\n\n", x, n); 
     if (n > nb_bits) 
      x_max = x; 
     else 
      x_min = x; 
    } 

    return x_min; 
} 

In generale meno di 10 cicli sono necessari per raggiungere il numero richiesto di bit (e con la fortuna si può prendere 2 o 3 loop). Casi d'angolo (nb_bits = 0,1, width-1, width) funzionano anche se un caso speciale sarebbe più veloce.

Esempio di risultato:

x_min = 0x0000000000000000, 0 bits 
x_max = 0x1FFFFFFFFFFFFFFF, 61 bits 
x  = 0x1492717D79B2F570, 33 bits 

x_min = 0x0000000000000000, 0 bits 
x_max = 0x1492717D79B2F570, 33 bits 
x  = 0x1000202C70305120, 14 bits 

x_min = 0x0000000000000000, 0 bits 
x_max = 0x1000202C70305120, 14 bits 
x  = 0x0000200C10200120, 7 bits 

x_min = 0x0000200C10200120, 7 bits 
x_max = 0x1000202C70305120, 14 bits 
x  = 0x1000200C70200120, 10 bits 

x_min = 0x1000200C70200120, 10 bits 
x_max = 0x1000202C70305120, 14 bits 
x  = 0x1000200C70201120, 11 bits 

x_min = 0x1000200C70201120, 11 bits 
x_max = 0x1000202C70305120, 14 bits 
x  = 0x1000200C70301120, 12 bits 

width = 61, nb_bits = 12, x = 0x1000200C70301120 

Naturalmente, è necessario un buon PRNG. Altrimenti puoi affrontare un ciclo infinito.

Answer 6

Ho un altro suggerimento basato sull'enumerazione: scegliere un numero casuale i compreso tra 1 e n scegliere k e generare la combinazione i-esimo. Ad esempio, per n = 6, k = 3 20 combinazioni sono:

000111 
001011 
010011 
100011 
001101 
010101 
100101 
011001 
101001 
110001 
001110 
010110 
100110 
011010 
101010 
110010 
011100 
101100 
110100 
111000 

Diciamo che casualmente scelto combinazione numero 7. innanzitutto verificare se ha un 1 nella ultima posizione: ha, perché la le prime 10 (5 scelte 2) hanno combinazioni. Quindi controlliamo in modo ricorsivo le posizioni rimanenti. Ecco il codice C++:

word ithCombination(int n, int k, word i) { 
    // i is zero-based 
    word x = 0; 
    word b = 1; 
    while (k) { 
     word c = binCoeff[n - 1][k - 1]; 
     if (i < c) { 
      x |= b; 
      --k; 
     } else { 
      i -= c; 
     } 
     --n; 
     b <<= 1; 
    } 
    return x; 
} 
word randomKBits(int k) { 
    word i = randomRange(0, binCoeff[BITS_PER_WORD][k] - 1); 
    return ithCombination(BITS_PER_WORD, k, i); 
} 

per essere veloce, usiamo coefficienti binomiali precalcolate in binCoeff. La funzione randomRange restituisce un numero intero casuale tra i due limiti (compreso).

Ho eseguito alcuni intervalli (source). Con il generatore di numeri casuali predefinito C++ 11, la maggior parte del tempo viene impiegata nella generazione di numeri casuali. Quindi questa soluzione è la più veloce, poiché utilizza il numero minimo assoluto di bit casuali possibili. Se utilizzo un generatore di numeri casuali veloce, la soluzione con mic006 è la più veloce. Se lo k è molto piccolo, è meglio impostare bit in modo casuale fino a quando non vengono impostati k.