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:
Générez un nombre pseudo-aléatoire de 64 bits k .
Comptez les bits en k , en stockant le résultat en b .
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?
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 k … x 1nxk…x1
∑1≤i≤k(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:
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)=(x−1y)+(x−1y−1)
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;
}
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++)
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.k 1 c
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 .1 0
Soit donc le nombre de bits restant à déterminer et le nombre de bits restant à utiliser.x y
Nous savons que , et nous pouvons l'utiliser pour déterminer correctement le bit suivant du nombre à chaque étape:(xy)=(x−1y)+(x−1y−1)
la source
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:
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.
la source
Vous pouvez effectuer les opérations suivantes:
1) Générez un nombre aléatoire, compris entre et .k 1 64
2) Réglez th sur .k 0 1
3) Répétez les étapes 1 et 2 foisn
la source
1
s 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 plusieursk
s entrent en collision