самый быстрый способ генерировать случайные биты

Question

Какой самый быстрый способ генерировать большое количество (псевдо) случайных битов. Каждый бит должен быть независимым и быть равным нулю или единице с равной вероятностью. Я, очевидно, мог бы сделать некоторые изменения на

randbit=rand()%2;

но я чувствую, что должен быть более быстрый способ, генерирующий несколько случайных битов от каждого вызова генератора случайных чисел. В идеале я хотел бы получить int или char, где каждый бит является случайным и независимым, но возможны и другие решения.

Приложение не является криптографическим по своей природе, поэтому сильная случайность не является основным фактором, тогда как скорость и получение правильного распределения важны.

Answer 1

преобразование случайного числа в двоичное
Почему бы не получить только одно число (соответствующего размера, чтобы получить достаточное количество битов), а затем преобразовать его в двоичный файл. На самом деле вы получите биты из случайного числа, что означает, что они также случайны.

Нули и единицы также имеют вероятность 50%, поскольку взятие всех чисел от 0 до некоторого предела 2 ^ n и подсчет количества нулей и единиц равны>, что означает, что вероятность нулей и единиц одинакова. *

относительно скорости
это, вероятно, будет очень быстро, так как получение только одного случайного числа по сравнению с количеством бит в нем происходит быстрее. теперь это зависит только от вашего двоичного преобразования.

Answer 2

Взгляните на Boost.Random , особенно boost::uniform_int<>.

Answer 3

Как вы говорите, генерируйте случайные целые числа.
Тогда у вас есть 32 случайных бита с единицами и нулями, одинаково вероятными.

Получить биты в цикле:

for (int i = 0; i < 32; i++)
{
  randomBit = (randomNum >> i) & 1
  ...
  // Do your thing
}

Повторяйте это столько раз, сколько вам нужно, чтобы получить правильное количество бит.

Answer 4

Вот очень быстрый код, который я кодировал на Java на основе алгоритма Джорджа Марсальи XORShift: вы получаете 64 бита за раз!

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

Answer 5

SMP Safe (т. Е. Самый быстрый способ, возможный в наши дни) и хорошие биты

Обратите внимание на использование атрибута [ThreadStatic], этот объект автоматически обрабатывает новый поток, без блокировки. Это единственный способ обеспечить высокопроизводительную произвольную работу без блокировки SMP.

http://blogs.msdn.com/pfxteam/archive/2009/02/19/9434171.aspx

Answer 6

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

В моем тесте потребовалось 4,5886e-05 с 256 битами.

Answer 7

если вам нужно только немного, попробуйте bool coinToss() { return rand()&1; } Технически это был бы более быстрый способ генерирования битов из-за замены% 2 на & 1, которые эквивалентны.

Answer 8

Насколько велико количество генерируемых битов? Если он не больше нескольких миллионов, и, учитывая, что вы не используете генератор для криптографии, я думаю, что самым быстрым из возможных способов будет предварительный расчет большого набора целых чисел с правильным распределением, преобразование его в текст файл вроде этого:

unsigned int numbers[] =
{
  0xABCDEF34, ...
};

, а затем скомпилируйте массив в вашу программу и пройдитесь по нему один раз за раз.

Таким образом, вы получаете 32 бита при каждом вызове (на 32-битном процессоре), время генерации является самым коротким из возможных, поскольку все числа генерируются заранее, а распределение контролируется вами. Недостатком является, конечно, то, что эти числа вовсе не случайны, что в зависимости от того, для чего вы используете PRNG, может иметь или не иметь значения.

Answer 9

Если я правильно помню, младшие значащие биты обычно имеют "менее случайный" распределение для большинства генераторов псевдослучайных чисел, поэтому использование модуля и / или каждого бита в сгенерированном числе будет плохим, если вы беспокоитесь о распределении.

(Может быть, вы должны хотя бы Google, что говорит Кнут ...)

Если это так (и трудно сказать, не зная точно, какой алгоритм вы используете), просто используйте старший бит в каждом сгенерированном числе.

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

Answer 10

Просто прочитайте немного памяти - возьмите n-битный раздел сырой памяти. Это будет довольно случайно.

Либо создайте большое случайное число типа int x и просто используйте значения битов.

for(int i = (bitcount-1); i >= 0 ; i--) bin += x & (1 << i);