der Schnellste Weg zur Erzeugung von zufälligen bits

Was wäre der Schnellste Weg, um erzeugen eine große Anzahl von (pseudo-)zufällige bits. Jedes bit unabhängig sein müssen, und null oder eins mit gleicher Wahrscheinlichkeit auf. Ich könnte natürlich einige Variationen auf

randbit=rand()%2;

aber ich fühle mich wie es sollte eine Methode, die schneller, erzeugen einige zufällige bits von jedem Aufruf des Zufallszahlengenerators. Im Idealfall würde ich mag, um ein int oder ein char ist, bei dem jedes bit ist zufällig und unabhängig ist, aber andere Lösungen sind auch möglich.

Die Anwendung ist nicht kryptographische in der Natur so starke Zufälligkeit ist nicht ein wichtiger Faktor ist, in der Erwägung, dass die Geschwindigkeit und die richtige Verteilung ist wichtig.

Welche distribution Sie suchen? Und wie wählerisch sind Sie in Bezug auf die Richtigkeit der Verteilung. Wenn Sie wirklich wollen, P[x] = 1/n für die zahlen x im Intervall [1..n], dann müssen Sie noch einen guten rng-auch wenn Ihre Anwendung nicht crypto.
Was über so etwas wie ((int)rand*rand)%2?
Vielleicht ein Duplikat der stackoverflow.com/questions/25176423/... (diese Frage ist mehr breit als er fragt auch, über nicht bei 50:50-Distributionen)

InformationsquelleAutor dagw | 2009-05-15

c++random

5

konvertieren eine zufällige Zahl in Binär

Warum Holen Sie sich nicht nur eine Zahl (mit der passenden Größe, um genug bits, die Sie brauchen) und dann konvertieren Sie es in binäre. Werden Sie tatsächlich bit aus einer zufälligen Zahl, die bedeutet, Sie sind willkürlich.

Nullen und Einsen haben auch die Wahrscheinlichkeit von 50%, denn alle zahlen zwischen 0 und 2^n-Grenze und zählen die Anzahl der Nullen und Einsen gleich sind > was bedeutet, dass die Wahrscheinlichkeit von Nullen und Einsen ist gleich.

hinsichtlich der Geschwindigkeit

das wäre wahrscheinlich sehr schnell, da immer nur eine zufällige Zahl im Vergleich zur Anzahl der bits in es ist schneller. es rein hängt davon ab, Ihre binäre Konvertierung jetzt.
- kurze Anmerkung: Binär-Konvertierung eine einfache bitshift-Schleife: for ( i = 0; i < sizeof( randomNumber ) * 8; ++i ) { std::cout << ( randomNumber & 1U ); randimNumber >>= 1U; } vorausgesetzt randomNumber. ist eine vorzeichenlose Ganzzahl.
InformationsquelleAutor Robert Koritnik
4

Werfen Sie einen Blick auf Boost.Random, vor allem boost::uniform_int<>.

InformationsquelleAutor avakar
3

Wie Sie sagen, einfach erzeugen zufällige ganze zahlen.

Dann haben Sie 32 zufällige bits mit Einsen und Nullen gleich wahrscheinlich sind.

Holen Sie sich die bits in einer Schleife:
```
for (int i = 0; i < 32; i++)
{
  randomBit = (randomNum >> i) & 1
  ...
  //Do your thing
}
```
Wiederholen Sie diesen Schritt für wie viele Male Sie brauchen, um zu erhalten die richtige Menge an bits.
- rand ist nicht garantiert, zurück 32 zufällige bits. In der Tat, unter msvc, es gibt nur 16.
- Natürlich, es ist Plattform abhängig, aber das Prinzip ist immer noch die gleiche, unabhängig von der Plattform.
- Sind Sie wirklich gleich verteilt? Als ich diese Idee, konnte aber nicht ganz überzeugen Sie mich, dass jedes bit wäre gleichmäßig und unabhängig voneinander verteilt.
- Das kommt auf die Menge an bits. In kleineren Teilmengen, die Sie finden können schiefe Verteilungen, sondern das größere set je einheitlicher die Verteilung werden. Da Sie speziell wollte eine große Anzahl von bits, das sollte erfüllen Ihre Verteilung Richtigkeit.
- Ich denke, dass die Verteilung für jeden etwas tatsächlich werden nicht eaqually wahrscheinlich für die wenigsten signifikanten bits.
- Geht das etwas genauer? (Da Sie offensichtlich downvoted).
- Gemeinsame RNGs haben eine völlig nicht-zufällige LSB (immer klappt).
- Dies ist nicht eine Frage von RNGs (oder Antwort auf RNGs) dies ist ein Algorithmus in Frage. Unabhängig von der RNG. Da es 2^32 mögliche zahlen und der bit-Verteilung ist genau gleich, nicht etwas gleich oder fast gleich oder sogar fast gleich, aber GENAU gleich, die Verteilung der bits wird mehr und mehr uniform, die größer die Menge ist.
- Ich Stimme zu, wenn Sie begrenzt nicht die max Ergebnis von rand, Sie sind gleichmäßig verteilt.
InformationsquelleAutor Sani Singh Huttunen

Hier ist eine sehr schnelle ein-ich codiert in Java basierend auf George Marsaglia ist XORShift-Algorithmus: bekommt man 64 bits zu einer Zeit!

/**
 * State for random number generation
 */
private static volatile long state=xorShift64(System.nanoTime()|0xCAFEBABE);

/**
 * Gets a long random value
 * @return Random long value based on static state
 */
public static final long nextLong() {
    long a=state;
    state = xorShift64(a);
    return a;
}

/**
 * XORShift algorithm - credit to George Marsaglia!
 * @param a Initial state
 * @return new state
 */
public static final long xorShift64(long a) {
    a ^= (a << 21);
    a ^= (a >>> 35);
    a ^= (a << 4);
    return a;
}

Hinweis: der Grund, warum dieser Algorithmus so schnell ist, dass es nur mit einfachen bitweisen Operatoren in einer Sequenz, die erwiesen haben (Marsaglia) zum erzeugen einer "gut genug" Pseudo-random-Sequenz. Dies ist nicht kryptographisch stark, aber gut genug für games, Simulationen, etc.

InformationsquelleAutor mikera

1

SMP-Sicher (d.h. Schnellste Weg, possiable in diesen Tagen) und gute bits

Beachten Sie die Verwendung der [ThreadStatic] - Attribut, so wird dieses Objekt automatisch Griff ist der neue thread, keine sperren. Das ist der einzige Weg, Sie gehen, um zu gewährleisten, high-performance-random, SMP lockfree.

http://blogs.msdn.com/pfxteam/archive/2009/02/19/9434171.aspx
- Sehr interessanter Artikel, vielen Dank
InformationsquelleAutor RandomNickName42

#include <iostream>
#include <bitset>
#include <random>

int main()
{
    const size_t nrOfBits = 256;
    std::bitset<nrOfBits> randomBits;

    std::default_random_engine generator;
    std::uniform_real_distribution<float> distribution(0.0,1.0);

    float randNum;
    for(size_t i = 0; i < nrOfBits; i++)
    {
        randNum = distribution(generator);
        if(randNum < 0.5) {
            randNum = 0;
        } else {
            randNum = 1;
        }
        randomBits.set(i, randNum);
    }

    std::cout <<  "randomBits =\n" << randomBits << std::endl;
    return 0;
}

Dieser nahm 4.5886 e-05s bei meinem test mit 256 bit.

Ich mag diese Antwort, da es die einzige ist, zeigt der C++ Weg, aber ich denke, mit der bernoulli_distribution wäre noch besser gewesen, einfacher, schneller, und vieles mehr richtig!!!!
warum denken Sie so?
Denn Sie speichern, generieren eine ganze 32bit float und vergleichen und stattdessen einen random-bit aus einer hoch optimierten STL-Objekt speichern und auch einige code-Zeilen als auf die es hinausläuft: std::bernoulli_distribution bdist(0.5); for(size_t i = 0; i < nrOfBits; i++) randomBits.set(i, bdist(generator));

InformationsquelleAutor Anno

0

Können Sie sich eine Zufallszahl erzeugen und halten auf der rechten shifitng und Test der least significant bit, um die zufällige bits zu tun, anstatt eine mod-operation.

InformationsquelleAutor Naveen
0

Wenn ich erinnern, richtig, die am wenigsten signifikanten bits sind normalerweise mit einem "weniger zufällig"
die Verteilung für die meisten pseuodo Zufallszahlen-Generatoren, so dass die Verwendung von modulo und/oder jedes bit in die generierte Zahl wäre schlimm, wenn Sie sind besorgt über die Verteilung.

(Vielleicht sollte man wenigstens google, was Knuth sagt...)

Wenn das hält ( und das ist schwer zu sagen, ohne genau zu wissen, welchen Algorithmus Sie verwenden) verwenden nur das höchste bit in jede generierte Zahl ist.

http://en.wikipedia.org/wiki/Pseudo-random

InformationsquelleAutor KarlP
0

Wie groß brauchst du die Anzahl der erzeugten bits werden? Wenn es nicht größer als ein paar Millionen, und im Kopf behalten, dass Sie nicht über den generator für Kryptographie, dann denke ich der Schnellste Weg wäre precompute eine große Menge der ganzen zahlen mit der richtigen Verteilung, konvertieren Sie es in eine text-Datei wie folgt:
```
unsigned int numbers[] =
{
  0xABCDEF34, ...
};
```
- und kompilieren Sie dann das array in Ihrem Programm und durch die es eine Zahl zu einem Zeitpunkt.

So erhalten Sie 32 bits, die mit jedem Aufruf (auf einem 32-bit-Prozessor), die Generationszeit ist die kürzeste, weil alle zahlen, die generiert werden, im Voraus, und die Verteilung wird von Ihnen kontrolliert. Der Nachteil ist natürlich, dass diese zahlen nicht zufällig sind, was je nachdem, was Sie mit dem PRNG für möglicherweise oder möglicherweise keine Rolle.

InformationsquelleAutor ajanicij
0

wenn Sie nur ein wenig in einer Zeit versuchen
bool coinToss() { return rand()&1; } Es technisch ein schneller Weg zur Erzeugung von bits, da der Austausch der %2 &1, die gleichwertig sind.

InformationsquelleAutor user2146937
-3

Gerade gelesen, einige Speicher - nehmen Sie ein n-bit-Abschnitt von raw-Speicher. Es wird ziemlich random.

Alternativ, erzeugen eine große zufällige int x und verwenden nur die bit-Werte.
```
for(int i = (bitcount-1); i >= 0 ; i--) bin += x & (1 << i);
```
- Speicher nicht enthalten Zufallsdaten, im Gegenteil sogar: Sie wurden dort in einer strukturierten Art und Weise durch eine Anwendung.
- Die bits werden nach dem Zufallsprinzip angeordnet, für alle Absichten und Zwecke, da die Struktur relevanter Bedeutung. z.B. "mein Hund" ist ein bestelltes Stück von Daten, sondern seiner binäre ist 011011010111100100100000011001000110111101100111, das ist ziemlich random. Bitte geben Sie mir wieder meine +1, da bin ich richtig.
- Raw-Speicher im Allgemeinen ist keine gute Idee! E. g. in Ihrem Beispiel eine ASCII-Zeichenkette, jedes 8. bit ist 0, die als gültige Zeichen verwenden Sie nur die unteren 7 bits. Mehr über, es scheint, dass die bytes von 0 sind durchaus üblich (Polsterung, ungenutzten Speicher, zahlen, die nicht die volle Bandbreite, bools gespeichert in int32, ...) so könnte man mehr erwarten 0s dann 1s.
- Vereinbart. Ich dachte, dass das wie ich das oben geschrieben, aber die zweite Methode funktioniert gut,...
InformationsquelleAutor Antony Carthy

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.