Сколько времени занимает поток Random (). Next (), пока он не повторится? - PullRequest
Новая
       16

Сколько времени занимает поток Random (). Next (), пока он не повторится?

9 голосов
/ 12 января 2010

Рассмотрим поток .NET Random: 

var r = new Random(); 
while (true) 
{ 
    r.Next(); 
}

Сколько времени нужно, чтобы повторить?

1 Ответ

13 голосов
/ 12 января 2010

Согласно документации:

Псевдослучайные числа выбираются с равной вероятностью из конечного набор чисел. Выбранные номера не совсем случайно, потому что определенный математический алгоритм раньше выбирал их, но они достаточно случайным для практического цели. Текущая реализация Случайный класс основан на Дональде Вычитающее случайное число Э. Кнута алгоритм генератора. Для большего информация, см. Д. Е. Кнут. "Искусство компьютерного программирования, том 2: Получисленные алгоритмы ". Аддисон-Уэсли, Рединг, Массачусетс, второй издание, 1981.

Субтрактивный генератор (Кнут, Том 2) Xf, n = (Xf, n-k - Xf, n-j) mod 1. См. Кнут для таблицы возможных значений k и j. Мы выбираем k = 63, j = 31. Этот генератор интересен тем, что:

  • Это имеет длительный период. Период младшего значащего бита в этой последовательности равен 2 k -1. Фактический период намного длиннее этого.
  • С некоторыми мягкими ограничениями, арифметика с плавающей запятой является точной!

Второе свойство сохраняется, когда X имеет вид л 247 (0 м <247) Арифметика с одинарной точностью является точной для Crays (48-битная мантисса) и так же, как арифметика с двойной точностью для машин, соответствующих IEEE. </p>

Это позволяет генерировать основную последовательность случайных чисел с помощью кода Фортрана 

  x(n) = x(n-k) - x(n-j)
  if (x(n) < 0.0) x(n) = 1.0 + x(n)

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

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

...