Быстрая генерация случайных чисел, которые кажутся случайными

Question

Я ищу эффективный способ генерировать числа, которые человек воспримет как случайные. По сути, я думаю об этом, как об избегании длинных последовательностей 0 или 1 бит. Я ожидаю, что люди будут просматривать битовую комбинацию, и процессор с очень низким энергопотреблением должен рассчитывать около тысячи из них в секунду.

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

1. Генерация случайного числа с фиксированным числом в один бит. Для 32-разрядного случайного числа требуется до 31 случайного числа с использованием алгоритма выбора Кнута. Есть ли более эффективный способ генерации случайного числа с некоторым количеством битов? К сожалению, 0000FFFF выглядит не очень случайно.

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

Надеюсь, есть еще один алгоритм, о котором я не задумывался. Заранее спасибо за помощь.

[EDIT] Я должен быть более ясным с тем, что я прошу -
(а) Существует ли эффективный способ генерирования случайных чисел без «длинных» последовательностей одного бита, где «длинный» является настраиваемым параметром?
(б) Другие предложения о том, что может сделать число менее случайным?

Answer 1

A регистр сдвига с линейной обратной связью , вероятно, делает то, что вы хотите.

Отредактируйте в свете обновленного вопроса: Вы должны взглянуть на сумку для случайного воспроизведения , хотя я не уверен, насколько быстро это может продолжаться. Смотрите также этот вопрос .

Answer 2

Я действительно не знаю, что вы подразумеваете под битовыми шаблонами, которые «выглядят» случайными. Есть ли какой-нибудь алгоритм для определения, что это такое? Одним из способов может быть составление массива, состоящего только из тех чисел, которые являются достаточно случайными для вашей цели, затем случайным образом выбирают элементы из этого массива и помещают их в поток. То, что вы пытаетесь сделать, кажется мне странным и может быть обречено на провал. Что произойдет, если у вас есть два 32-разрядных числа, которые взяты по отдельности, будут соответствовать вашим критериям очевидной случайности, но при расположении рядом друг с другом сделайте достаточно длинный поток из 0 или 1, чтобы выглядеть составленным?

Наконец, я не смог устоять перед этим.

Answer 3

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

Средняя длина прогона в случайных двоичных данных, конечно, равна 4 (сумма n / (2 ^ (n-1))), а средняя в режиме 1. Вот некоторые случайные биты (клянусь, это один прогон Я не выбрал значение, чтобы высказать свою точку зрения):

0111111011111110110001000101111001100000000111001010101101001000

Видите, там длина пробега 8. Это не особенно удивительно, поскольку длина прогона 8 должна происходить примерно каждые 256 бит, а я сгенерировал 64 бита.

Если это не выглядит «случайным» для вас из-за чрезмерной длины прогона, то генерируйте длины прогона с любым желаемым распределением. В псевдокоде:

loop
    get a random number
    output that many 1 bits
    get a random number
    output that many 0 bits
endloop

Возможно, вы захотите отбросить некоторые исходные данные из потока или рандомизировать первый бит, чтобы избежать проблемы, заключающейся в том, что первый бит всегда равен 1. Вероятность того, что N-й бит равен 1, зависит от того, как вы «получаете случайное число», но для всего, что достигает «коротких, но не слишком коротких» длин пробега, оно скоро будет настолько близко к 50%, что не имеет значения.

Например, «получить случайное число» может сделать это:

get a uniformly-distributed random number n from 1 to 81
if n is between 1 and 54, return 1
if n is between 55 and 72, return 2
if n is between 72 and 78, return 3
if n is between 79 and 80, return 4
return 5

Идея состоит в том, что вероятность прогона длины N равна одной трети вероятности прогона длины N-1, а не половине. Это даст намного меньшую среднюю длину пробега и самый длинный пробел из 5, и, следовательно, будет выглядеть «более случайным» для вас. Конечно, это не «выглядело бы случайным» для любого, кто привык иметь дело с последовательностями бросков монет, потому что они думали, что пробеги были слишком короткими. Вы также можете очень легко сказать с помощью статистических тестов, что значение цифры N коррелирует со значением цифры N-1.

Этот код использует как минимум log (81) = 6,34 "случайных битов" для генерации в среднем 1,44 битов вывода, поэтому он медленнее, чем просто генерация битов с равномерным распределением. Но это не должно быть намного больше, чем примерно в 7 / 1,44 = 5 раз медленнее, и LFSR довольно быстро начать с.

Answer 4

Если вы хотите избежать длительных запусков, как насчет чего-то простого, например:

#include <cstdlib>

class generator {
public:
   generator() : last_num(0), run_count(1) { }

   bool next_bit() {
      const bool flip = rand() > RAND_MAX / pow( 2, run_count);
                               // RAND_MAX >> run_count ? 
      if(flip) {
         run_count = 1;
         last_num = !last_num;
      } else
         ++run_count;

      return last_num;
   }
private:
   bool last_num;
   int run_count;
};

Прогоны становятся менее вероятными, чем дольше они продолжаются. Вы также можете сделать RAND_MAX / 1 + run_count, если вы хотите более длинные пробеги

Answer 5

Случайные числа часто имеют длинные последовательности 1 и 0, поэтому я не уверен, что полностью понимаю, почему вы не можете использовать простой линейный конгруэнтный генератор и сдвигать или сколько бит вам нужно. Они быстро светятся, выглядят очень случайными невооруженным глазом, и вы можете выбрать коэффициенты, которые будут давать случайные целые числа в любом положительном диапазоне, который вам нужен. Если вам нужно 32 «случайно выглядящих» бита, просто сгенерируйте четыре случайных числа и возьмите младшие 8 бит из каждого.

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

Если вы решили, что вам нужна конкретная плотность 1 с, вы всегда можете начать с числа, для которого установлено требуемое число 1 с

int a = 0x00FF;

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

Answer 6

Вот что я бы сделал. Я бы использовал число типа 00101011100101100110100101100101 и каждый раз поворачивал бы его на какую-то случайную величину.

Но вы уверены, что типичный псевдослучайный генератор не подойдет? Ты это пробовал? В любом случае, вы не очень много длинных строк, равных 0 и 1.

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

Answer 7

Вы должны решить, по каким именно правилам вы решите, если что-то «выглядит случайным». Затем вы берете генератор случайных чисел, который генерирует достаточно «реальной случайности» для вашей цели, и каждый раз, когда он генерирует число, которое выглядит недостаточно случайным, вы выбрасываете это число и генерируете новое.

Или вы напрямую создаете последовательность «случайных» битов, и каждый раз, когда генератор случайных чисел выводит «неправильный» следующий бит (который будет выглядеть не случайно), вы просто переворачиваете этот бит.

Answer 8

Один простой подход - генерировать по одному биту за раз с параметром настройки, чтобы контролировать вероятность того, что каждый новый бит соответствует предыдущему. Установив вероятность ниже 0,5, вы можете генерировать последовательности, которые с меньшей вероятностью будут содержать длинные серии повторяющихся битов (и вы можете настроить эту вероятность). Установка p = 0 дает повторяющуюся последовательность 1010101010101010; настройка p = 1 дает последовательность всех 0 или всех 1.

Вот немного C # для демонстрации:

double p = 0.3; // 0 <= p <= 1, probability of duplicating a bit

var r = new Random();
int bit = r.Next(2);    

for (int i = 0; i < 100; i++)
{
    if (r.NextDouble() > p)
    {
        bit = (bit + 1) % 2;
    }        

    Console.Write(bit);                
}

Это может быть слишком медленным для ваших нужд, так как вам нужно генерировать случайное двойное число, чтобы получить каждый новый случайный бит. Вместо этого вы можете сгенерировать случайный байт и использовать каждую пару битов для генерации нового бита (т. Е. Если оба равны нулю, оставьте тот же бит, в противном случае переверните его, если вас устраивает эквивалент фиксированного р = 0,25 ).

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

Answer 9

Не могу поверить, что никто не упомянул это: Если вы хотите, чтобы длительность (период) 2N повторялась:

PeopleRandom()
{
    while(1)
    {
        Number = randomN_bitNumber();
        if(Number && Number != MaxN_BitNumber)
            return Number;
    }
}

это дает гораздо лучшие результаты с точки зрения количества бросков, чем при использовании 32-битного и т. Д. Rand

плюсы:

• вы бросаете только значения 2/2 ^ N времени.
• Чем больше N, тем лучше результаты.

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

Answer 10

Проверьте GSL . Я считаю, что у него есть некоторые функции, которые делают именно то, что вы хотите. По крайней мере, они гарантированно являются случайными битовыми строками. Я не уверен, что они выглядят случайными, так как это скорее психологический вопрос.