PRNG para gerar números com n bits definidos exatamente

12

Atualmente, estou escrevendo algum código para gerar dados binários. Eu preciso especificamente gerar números de 64 bits com um determinado número de bits definidos; mais precisamente, o procedimento deve levar cerca de e retornar um número pseudo-aleatório de 64 bits com exatamente n bits definido como 1 e o restante definido como 0.0<n<64n1

Minha abordagem atual envolve algo como isto:

  1. Gere um número pseudo-aleatório de 64 bits .k
  2. Conte os bits em , armazenando o resultado em b .kb
  3. Se , produza k ; caso contrário, vá para 1.b=nk

Isso funciona, mas parece deselegante. Existe algum tipo de algoritmo PRNG que pode gerar números com bits definidos de maneira mais elegante que isso?n

Koz Ross
fonte

Respostas:

12

Você precisa de um número aleatório entre 0 e . O problema então é transformar isso no padrão de bits.(64n)1

Isso é conhecido como codificação enumerativa e é um dos algoritmos de compactação implantados mais antigos. Provavelmente o algoritmo mais simples é de Thomas Cover. É baseado na simples observação de que se você tem uma palavra com bits de comprimento, em que os bits definidos são x kx 1 na ordem de bits mais significativa, a posição dessa palavra na ordem lexicográfica de todas as palavras com esse propriedade é:nxkx1

1ik(xii)

Então, por exemplo, para uma palavra de 7 bits:

i(0001011)= ( 3

i(0000111)=(23)+(12)+(01)=0
i(0001101)= ( 3
i(0001011)=(33)+(12)+(01)=1
i(0001101)=(33)+(22)+(01)=2

...e assim por diante.

Para obter o padrão de bits do ordinal, basta decodificar cada bit por vez. Algo assim, em uma linguagem 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;
}

Observe que, como você só precisa de coeficientes binomiais de até 64, pode pré-calculá-los.


  • Cover, T., codificação de fonte enumerativa . IEEE Transactions on Information Theory, Vol. IT-19, No 1, Jan 1973.
Pseudônimo
fonte
Bonito e elegante! A codificação enumerativa se parece com algo muito útil - existem bons recursos (de preferência em formato de livro didático)?
Koz Ross
Isso realmente oferece melhor desempenho na prática? (É claro que depende da velocidade do RNG.) Caso contrário, não faz sentido usar código mais complexo.
Gilles 'SO- stop be evil'
1
@Giles Eu interpretei isso como uma questão de ciência da computação, uma vez que é cs.se. Eu só forneci o código-fonte porque, por acaso, ele estava em uma implementação de matriz RRR. (Ver, por exemplo, alexbowe.com/rrr para uma explicação sobre o que isso significa.)
Pseudonym
1
@Gilles Para dar seguimento à sua pergunta, implementei tanto o meu método ingênuo quanto o fornecido pelo Pseudonym in Forth. O método ingênuo, mesmo ao usar um PRNG xorshift muito simples, levava algo na ordem de 20 segundos por número , enquanto o método de Pseudonym era quase instantâneo. Eu usei tabelas de binômios pré-computados para isso.
Koz Ross
1
@KozRoss Se você gerar n números de bits e procurar números com k bits definidos, eles seriam bastante raros se k estivesse longe de n / 2; isso explicaria isso.
gnasher729 22/01
3

Muito semelhante à resposta do pseudônimo, obtida por outros meios.

O número total de combinações disponíveis é acessível pelo método de estrelas e barras , portanto, ele terá que ser . O número total de números de 64 bits dos quais você tentaria amostrar seu número seria obviamente muito maior que isso.c=(64n)

O que você precisa então é de uma função que possa levar você de um número pseudoaleatório , variando de 1 a c , à combinação de 64 bits correspondente.k1c

O triângulo de Pascal pode ajudá-lo com isso, porque o valor de cada nó representa exatamente o número de caminhos desse nó até a raiz do triângulo, e todo caminho pode ser feito para representar uma das cadeias de caracteres que você está procurando, se todas as curvas à esquerda forem rotulado com e, a cada curva à direita, com 0 .10

Portanto, seja o número de bits restantes para determinar e y seja o número de bits restantes a serem utilizados.xy

Sabemos que , e podemos usá-lo para determinar adequadamente o próximo bit do número em cada etapa:(xy)=(x1y)+(x1y1)

whilex>0

ifx>y

ifk>(x1y):ss+"1",kk(x1y),yy1

else:ss+"0"

else:ss+"1",yy1

xx1

André Souza Lemos
fonte
2

Outro método bastante elegante é usar a bissecção conforme descrito nesta resposta do stackoverflow . A idéia é manter duas palavras, uma conhecida por ter no máximo k bits definidos e outra conhecida por ter pelo menos k bits definidos, e usar a aleatoriedade para mover uma delas para ter exatamente k bits. Aqui está um código-fonte para ilustrá-lo:

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;
}

Fiz uma comparação de desempenho de vários métodos e este é geralmente o mais rápido, a menos que se saiba que o k é muito pequeno.

Falk Hüffner
fonte
0

Você pode fazer o seguinte:

1) Gere um número aleatório,k entre 1 e 64.

2) Definir k º 0 0 para 1.

3) Repita as etapas 1 e 2 n vezes

UMA[] é 64 matriz de bits com todos 0 0s

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;
}
Usuário não encontrado
fonte
A prosa parece não corresponder ao seu código? O código nunca atribui 1s à matriz. Além disso, parece não gerar uma distribuição uniforme (e nem mesmo números que satisfazem as restrições) quando múltiplos ks colidem.
Bergi
@Bergi Ya esqueceu o UMA[x]=1line ... adicionou agora. E a colisão múltipla de k é tratada. O primeiro número escolhido é escolhido entre 1 e 64, o segundo entre 1 e o restante "63". Por isso, ignora o 1 enquanto conta ... veja oif(A[x]==0)k; line. And it is uniform distribution.
User Not Found
Ah, I see now. The prose algorithm didn't mention the skipping.
Bergi
@ArghyaChakraborty Are you using 1-based indexing there?
Koz Ross
@KozRoss Start with what happens if i=1,k=1 (of course A will be all zeroes) So, it will check A[1]==0 and get true meaning k; which gives k=0. So, sets A[1]=1 outside the loop. So yeah it is 1-based indexing. To make it 0 based all you have to do is change the inner for to (x=0;x<64;x++)
User Not Found