PRNG zur exakten Generierung von Zahlen mit n gesetzten Bits

12

Ich schreibe gerade Code, um Binärdaten zu generieren. Ich muss speziell 64-Bit-Zahlen mit einer bestimmten Anzahl von gesetzten Bits generieren. Genauer gesagt sollte die Prozedur einige annehmen und eine pseudozufällige 64-Bit-Zahl mit genau auf gesetzten Bits und den Rest auf 0 setzen.0<n<64n1

Mein aktueller Ansatz sieht ungefähr so ​​aus:

  1. Erzeugen Sie eine pseudozufällige 64-Bit-Zahl .k
  2. Zähle die Bits in und speichere das Ergebnis in .kb
  3. Wenn , wird ausgegeben ; ansonsten gehe zu 1.b=nk

Das funktioniert, aber es scheint unelegant. Gibt es eine Art PRNG-Algorithmus, der Zahlen mit gesetzten Bits eleganter erzeugen kann als dies?n

Koz Ross
quelle

Antworten:

12

Was Sie brauchen, ist eine Zufallszahl zwischen 0 und . Das Problem ist dann, dies in das Bitmuster umzuwandeln.(64n)1

Dies wird als Aufzählungscodierung bezeichnet und ist einer der ältesten verwendeten Komprimierungsalgorithmen. Der wahrscheinlich einfachste Algorithmus stammt von Thomas Cover. Es basiert auf der einfachen Beobachtung, dass, wenn Sie ein Wort haben, das Bits lang ist, wobei die gesetzten Bits x kx 1 in der höchstwertigen Bitreihenfolge sind, die Position dieses Wortes in der lexikografischen Reihenfolge aller Wörter mit diesem Eigentum ist:nxkx1

1ik(xii)

So zum Beispiel für ein 7-Bit-Wort:

i(0001011)= ( 3

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

...und so weiter.

Um das Bitmuster von der Ordnungszahl zu erhalten, dekodieren Sie einfach jedes Bit der Reihe nach. So etwas in einer C-ähnlichen Sprache:

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

Da Sie nur Binomialkoeffizienten bis zu 64 benötigen, können Sie diese vorberechnen.


  • Cover, T., Enumerative Source Encoding . IEEE Transactions on Information Theory, Band IT-19, Nr. 1, Januar 1973.
Pseudonym
quelle
Schön und elegant! Enumerative Codierung sieht nach etwas sehr Nützlichem aus - gibt es gute Ressourcen (vorzugsweise in Lehrbuchform)?
Koz Ross
Gibt dies tatsächlich eine bessere Leistung in der Praxis? (Natürlich hängt es von der Geschwindigkeit des RNG ab.) Wenn nicht, macht es keinen Sinn, komplexeren Code zu verwenden.
Gilles 'SO- hör auf böse zu sein'
1
@Giles Ich habe dies als eine Informatikfrage interpretiert, da dies cs.se ist. Ich habe den Quellcode nur angegeben, weil er zufällig von einer RRR-Array-Implementierung stammt. ( Eine Erläuterung der Bedeutung finden Sie beispielsweise unter alexbowe.com/rrr .)
Pseudonym
1
@Gilles Um Ihre Frage zu beantworten, habe ich sowohl meine naive als auch die von Pseudonym in Forth bereitgestellte Methode implementiert. Die naive Methode dauerte, selbst wenn ein sehr einfaches Xorshift-PRNG verwendet wurde, etwa 20 Sekunden pro Zahl , während die Methode von Pseudonym fast augenblicklich war. Ich habe dafür Tabellen vorberechneter Binome verwendet.
Koz Ross
1
@KozRoss Wenn Sie n-Bit-Zahlen generieren und nach Zahlen suchen, für die k Bits festgelegt sind, sind sie ziemlich selten, wenn k weit von n / 2 entfernt ist. das würde es erklären.
gnasher729
3

Sehr ähnlich der Antwort von Pseudonym, die mit anderen Mitteln erhalten wurde.

Die Gesamtzahl der verfügbaren Kombinationen kann mit der Sternen - und Balken - Methode ermittelt werden , daher muss . Die Gesamtzahl der 64-Bit-Nummern, von denen Sie versuchen würden, Ihre Nummer abzutasten, wäre offensichtlich viel höher.c=(64n)

Was Sie dann brauchen, ist eine Funktion, die Sie von einer Pseudozufallszahl im Bereich von 1 bis c zur entsprechenden 64-Bit-Kombination führen kann.k1c

Pascals Dreieck kann Ihnen dabei helfen, da der Wert jedes Knotens genau die Anzahl der Pfade von diesem Knoten zur Wurzel des Dreiecks darstellt und jeder Pfad eine der Zeichenfolgen darstellen kann, nach denen Sie suchen, wenn alle Linksabbiegungen vorhanden sind Beschriftet mit einer und bei jeder Rechtskurve mit einer 0 .10

Also sei die Anzahl der noch zu bestimmenden Bits und y die Anzahl der noch zu verwendenden Bits .xy

Wir wissen, dass , und wir können es verwenden, um das nächste Bit der Zahl bei jedem Schritt richtig zu bestimmen:(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
quelle
2

Eine andere sehr elegante Methode ist die Verwendung der in dieser Stapelüberlaufantwort beschriebenen Halbierung . Die Idee ist, zwei Wörter zu behalten, von denen bekannt ist, dass sie höchstens k Bits haben und von denen bekannt ist, dass sie mindestens k Bits haben, und Zufälligkeit zu verwenden, um eines von diesen zu bewegen, um genau k Bits zu haben. Hier ist ein Quellcode zur Veranschaulichung:

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

Ich habe einen Leistungsvergleich verschiedener Methoden durchgeführt. Diese Methode ist normalerweise die schnellste, es sei denn, k ist als sehr klein bekannt.

Falk Hüffner
quelle
0

Sie können Folgendes tun:

k164

k01

n

EIN[]640

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;
}
Benutzer nicht gefunden
quelle
Die Prosa scheint nicht mit Ihrem Code übereinzustimmen? Der Code weist 1dem Array niemals s zu. Auch scheint es keine einheitliche Verteilung (und keine geraden Zahlen, die die Bedingungen erfüllen) zu erzeugen, wenn mehrere ks kollidieren
Bergi
EIN[x]=1ichf(EIN[x]==0)k--;
Ah, ich verstehe jetzt. Der Prosa-Algorithmus erwähnte das Überspringen nicht.
Bergi
@ArghyaChakraborty Verwenden Sie dort eine 1-basierte Indizierung?
Koz Ross
ich=1,k=1EINEIN[1]==0truek--;k=0EIN[1]=1fÖr(x=0;x<64;x++)