PRNG pour générer des nombres avec n bits définis exactement

12

J'écris actuellement du code pour générer des données binaires. J'ai spécifiquement besoin de générer des nombres 64 bits avec un nombre donné de bits définis; plus précisément, la procédure devrait prendre quelque 0<n<64 et retourner un nombre pseudo-aléatoire de 64 bits avec exactement n bits définis sur 1 , et le reste réglé sur 0.

Mon approche actuelle implique quelque chose comme ceci:

  1. Générez un nombre pseudo-aléatoire de 64 bits k .
  2. Comptez les bits en k , en stockant le résultat en b .
  3. Si b=n , sortie k ; sinon, passez à 1.

Cela fonctionne, mais cela semble inélégant. Existe-t-il une sorte d'algorithme PRNG qui peut générer des nombres avec n bits définis plus élégamment que cela?

Koz Ross
la source

Réponses:

12

Ce dont vous avez besoin est un nombre aléatoire compris entre 0 et . Le problème est alors de transformer cela en motif binaire.(64n)1

C'est ce que l'on appelle le codage énumératif, et c'est l'un des plus anciens algorithmes de compression déployés. L'algorithme le plus simple est probablement celui de Thomas Cover. Il est basé sur la simple observation que si vous avez un mot de bits, où les bits définis sont dans l'ordre de bits le plus significatif, puis la position de ce mot dans l'ordre lexicographique de tous les mots avec cette propriété est:x kx 1nxkx1

1ik(xii)

Ainsi, par exemple, pour un mot 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

...etc.

Pour obtenir le modèle de bits de l'ordinal, il vous suffit de décoder chaque bit à son tour. Quelque chose comme ça, dans un langage de type 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;
}

Notez que comme vous n'avez besoin que de coefficients binomiaux jusqu'à 64, vous pouvez les précalculer.


  • Cover, T., Enumerative Source Encoding . Transactions de l'IEEE sur la théorie de l'information, vol IT-19, no 1, janvier 1973.
Pseudonyme
la source
Beau et élégant! Le codage énumératif ressemble à quelque chose de très utile - y a-t-il de bonnes ressources (de préférence sous forme de manuel)?
Koz Ross
Cela donne-t-il réellement de meilleures performances dans la pratique? (Bien sûr, cela dépend de la vitesse du RNG.) Sinon, il est inutile d'utiliser un code plus complexe.
Gilles 'SO- arrête d'être méchant'
1
@Giles J'ai interprété cela comme une question informatique, car c'est cs.se. Je n'ai donné le code source que parce que je l'avais trouvé autour d'une implémentation d'un tableau RRR. (Voir, par exemple, alexbowe.com/rrr pour une explication de ce que cela signifie.)
Pseudonyme
1
@Gilles Pour donner suite à votre question, j'ai mis en œuvre à la fois ma méthode naïve et celle fournie par Pseudonym in Forth. La méthode naïve, même en utilisant un PRNG xorshift très simple, prenait quelque chose de l'ordre de 20 secondes par numéro , tandis que la méthode de Pseudonym était presque instantanée. Pour cela, j'ai utilisé des tableaux de binômes précalculés.
Koz Ross du
1
@KozRoss Si vous générez des nombres à n bits et recherchez des nombres avec k bits définis, ils seraient assez rares si k est loin de n / 2; cela expliquerait cela.
gnasher729
3

Très similaire à la réponse du pseudonyme, obtenue par d'autres moyens.

Le nombre total de combinaisons disponibles est accessible par la méthode des étoiles et des barres , il devra donc être . Le nombre total de nombres 64 bits à partir duquel vous tenteriez d'échantillonner votre numéro serait évidemment beaucoup plus élevé que cela.c=(64n)

Il vous faut alors une fonction qui peut vous conduire d'un nombre pseudo-aléatoire , allant de à , à la combinaison 64 bits correspondante.k1c

Le triangle de Pascal peut vous aider, car la valeur de chaque nœud représente exactement le nombre de chemins de ce nœud à la racine du triangle, et chaque chemin peut être fait pour représenter l'une des chaînes que vous recherchez, si tous les virages à gauche sont étiqueté avec un , et chaque tour à droite avec un .10

Soit donc le nombre de bits restant à déterminer et le nombre de bits restant à utiliser.xy

Nous savons que , et nous pouvons l'utiliser pour déterminer correctement le bit suivant du nombre à chaque étape:(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
la source
2

Une autre méthode assez élégante consiste à utiliser la bissection comme décrit dans cette réponse stackoverflow . L'idée est de garder deux mots, l'un connu pour avoir au plus k bits définis et l'autre connu pour avoir au moins k bits définis, et utiliser l'aléatoire pour déplacer l'un de ces derniers vers exactement k bits. Voici du code source pour l'illustrer:

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

J'ai fait une comparaison des performances de différentes méthodes et celle-ci est généralement la plus rapide, sauf si k est connu pour être très petit.

Falk Hüffner
la source
0

Vous pouvez effectuer les opérations suivantes:

1) Générez un nombre aléatoire, compris entre et .k164

2) Réglez th sur .k01

3) Répétez les étapes 1 et 2 foisn

A[] est un tableau de bits avec tous les s640

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;
}
Utilisateur non trouvé
la source
La prose ne semble pas correspondre à votre code? Le code n'affecte jamais 1s au tableau. De plus, il ne semble pas générer une distribution uniforme (et même pas des nombres qui satisfont aux contraintes) lorsque plusieurs ks entrent en collision
Bergi
@Bergi Ya a oublié la ligne ... l'a ajouté maintenant. Et la collision multiple de k est gérée. Voir le premier nombre est choisi entre 1 et 64, le second entre 1 et 63 "restant". Il saute donc le 1 en comptant ... voir leligne. Et c'est une distribution uniforme. A[x]=1if(A[x]==0)k;
Utilisateur introuvable
Ah, je vois maintenant. L'algorithme de prose n'a pas mentionné le saut.
Bergi
@ArghyaChakraborty Utilisez-vous ici une indexation basée sur 1?
Koz Ross
@KozRoss Commencez par ce qui se passe si (bien sûr sera tous des zéros) Donc, il vérifiera et obtiendra le sensce qui donne . Donc, définit dehors de la boucle. Donc oui, c'est une indexation basée sur 1. Pour le rendre 0 sur la base tout ce que vous devez faire est de changer l'intérieur àA A [ 1 ] = = 0 t r u e k - - ; k = 0 A [ 1 ] = 1 f o r ( x = 0 ; x < 64 , x + + )i=1,k=1AA[1]==0truek;k=0A[1]=1for(x=0;x<64;x++)
Utilisateur non trouvé