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

Question

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

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

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

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

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

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

Answer 1

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

Схема этих попыток создания случайных чисел, где вероятность получить два бита одинаковыми в строке равна 0,5, а получить три бита подряд - 0,25 и т. Д.

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

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

Answer 2

Вот так я бы проверил число:

const int max_repeated_bits = 4;  /* or any other number that you prefer */

int examine_1(unsigned int x) {      
  for (int i=0; i<max_repeated_bits; ++i) x &= (x << 1);
  return x == 0;
}

int examine(unsigned int x) {
  return examine_1(x) && examine_1(~x);
}

Затем просто сгенерируйте число x, если exam (x) вернет 0, отклоните его и попробуйте снова. Вероятность получить 32-битное число с более чем 4 битами подряд составляет около 2/3, поэтому вам потребуется около 3 случайных вызовов генератора на число. Тем не менее, если вы разрешите более 4 бит, он станет лучше. Скажем, вероятность получить более 6 бит подряд только около 20%, поэтому вам потребуется всего 1,25 звонка на номер.