Fast C случайный логический генератор

Question

Я заинтересован в генерации быстрых случайных логических значений (или, что то же самое, случайной величины Бернулли (0,5)) в C. Конечно, если у вас есть быстрый генератор случайных чисел с приличным статистическим поведением, то проблема «выбрать случайную Бернулли (0,5) легко решается: выборка x равномерно в (0,1) и возврат 1, если x<0.5, 0 в противном случае.

Предположим, скорость - это самое главное, теперь у меня есть два вопроса / соображения:

1. Многие генераторы случайных двойников сначала генерируют целое число m равномерно в определенном диапазоне [0,M], а затем просто возвращают деление m/M. Разве не было бы быстрее просто проверить, является ли m < M/2 (здесь M/2 фиксированным, поэтому мы сохраняем одно деление)

   2. Есть ли более быстрый способ сделать это? В конце концов, мы просим гораздо меньше статистических свойств: возможно, мы все еще заинтересованы в длительном периоде, но, например, нас не волнует равномерность распределения (до тех пор, пока примерно 50% значения находятся в первой половине диапазона).

Answer 1

Я заинтересован в генерации быстрых случайных логических значений

Использование LCG может быть быстрым, тем не менее, поскольку OP требует только bool результата, рассмотрите возможность извлечения только 1 бита за раз из приемлемого генератора и сохраните оставшуюся часть на потом. @ Акшай Л Арадхья

Пример на основе @ R .. и @ R .. кода.

extern uint32_t lcg64_temper(uint64_t *seed); // see R.. code

static uint64_t gseed; //  Initialize this in some fashion.
static unsigned gcount = 0;

bool rand_bool(void) {
  static uint32_t rbits;
  if (gcount == 0) {
    gcount = 32;  // I'd consider using 31 here, just to cope with some LCG weaknesses.
    rbits = lcg64_temper(&gseed);  
  }
  gcount--;
  bool b = rbits & 1;
  rbits >>= 1;
  return b;
}

Answer 2

Извлечение, скажем, что последний бит случайного числа может нанести ущерб, так как линейные конгруэнтные генераторы могут чередовать нечетные и четные числа ¹ .Схема типа clock() & 1 также будет иметь ужасные корреляционные равнины.

---

Рассмотрим решение, основанное на быстром и грязном генераторе Дональда Кунта: для uint32_t I, последовательность

I = 1664525 * I + 1013904223;

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

Тестирование I <= 0x7FFFFFFF менее броское и может быть еще быстрее, ножесткое кодирование средней точки не совсем удовлетворительно.

---

¹ Генератор, который я здесь представляю, делает.