Как работает XorShift32?

Question

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

Я пытаюсь напечатать сгенерированное число, но я не знаю, как вызвать функцию xorshift32 из-за аргумента состояния [статический 1].

uint32_t xorshift32(uint32_t state[static 1])
{
    uint32_t x = state[0];
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    state[0] = x;
    return x;
}

У меня мало информациина xorshft32 другое то что есть в википедии (en.wikipedia.org/wiki/Xorshift).

Answer 1

Это расширенный комментарий к хорошему ответу Jabberwocky .

Варианты Xorshift, rand() и, в основном, все функции генератора случайных чисел, на самом деле псевдослучайные числагенераторы .Они не являются «реальными случайными», потому что последовательность чисел, которые они генерируют, зависит от их внутреннего состояния;но они "псевдослучайные" , потому что если вы не знаете внутреннего состояния генератора, последовательность чисел, которую они генерируют, является случайной в статистическом смысле.

Джордж Марсаглия , автор семейства генераторов псевдослучайных чисел Xorshift, также разработал набор статистических инструментов, называемых Diehard tests , которые можно использовать для анализа «случайности» генерируемых последовательностей.В настоящее время тесты TestU01 являются, вероятно, наиболее широко используемыми и заслуживающими доверия;в частности, набор BigCrush с 160 тестами.

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

Мой собственный любимый PRNG - Xorshift64 *, который имеетпериод 2 ⁶⁴ -1 и проходит все, кроме теста MatrixRank в BigCrush.В C99 и более поздних версиях вы можете реализовать его, используя

#include <inttypes.h>

typedef struct {
    uint64_t  state;
} prng_state;

static inline uint64_t prng_u64(prng_state *const p)
{
    uint64_t  state = p->state;
    state ^= state >> 12;
    state ^= state << 25;
    state ^= state >> 27;
    p->state = state;
    return state * UINT64_C(2685821657736338717);
}

Состояние может быть инициализировано любым ненулевым uint64_t.(Нулевое состояние приведет к тому, что генератор будет генерировать все нули до бесконечности. Период равен 2 ⁶⁴ -1, поскольку генератор будет иметь каждое 64-битное состояние (исключая ноль) ровно один раз в течение каждого периода.)

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

Обратите внимание, что вариант, который возвращает равномерное распределение между 0 и 1,

static inline double prng_one(prng_state *p)
{
    return prng_u64(p) / 18446744073709551616.0;
}

использует старшие биты;старшие 32 бита последовательности проходят все тесты BigCrunch в наборе TestU01, так что это удивительно хороший генератор (случайность и эффективность) для равномерных случайных чисел двойной точности - мой типичный пример использования.

Форматвыше позволяет несколько независимых генераторов в одном процессе, указав состояние генератора в качестве параметра.Если базовый генератор реализован в заголовочном файле (то есть static inline; это макроподобная функция препроцессора), вы можете переключаться между генераторами, переключаясь между заголовочными файлами и перекомпилируя двоичный файл.

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

Функция rand() в большинстве реализаций стандартной библиотеки C представляет собой линейно-конгруэнтный генератор .Они часто страдают от плохого выбора коэффициентов, а в настоящее время также от относительной медленности оператора по модулю (когда модуль не является степенью двойки).

Наиболее широко используемый генератор псевдослучайных чисел - это Мерсенн Твистер , Макото Мацумото (松本 眞) и Такудзи Нисимура (西村 拓 士).Это скрученный обобщенный регистр сдвига с линейной обратной связью, имеющий довольно большое состояние (около 2500 байт) и очень длинный период (2 ¹⁹⁹³⁷ -1).

---

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

В Linux, Mac OS и BSD, по крайней мере, ядро ​​операционной системы предоставляет источник псевдослучайных чисел (getentropy() вLinux и OpenBSD, getrandom() в Linux, /dev/urandom, /dev/arandom, /dev/random во многих Unixes и т. Д.).Энтропия собирается из физических электронных источников, таких как задержки внутренних процессоров, синхронизация физических линий прерываний, синхронизация жесткого диска (вращающегося диска), возможно, даже клавиатуры и мыши.Многие материнские платы и некоторые процессоры даже имеют аппаратные источники случайных чисел , которые могут использоваться в качестве источников энтропии (или даже непосредственно как "надежные источники случайности").

эксклюзивно-илиоперация (^ в C) используется для случайного смешивания с состоянием генератора.Это работает, потому что исключительный или между известным битом и случайным битом приводит к случайному биту;XOR сохраняет случайность.При смешивании пулов энтропии (с некоторой степенью случайности в битовых состояниях) с использованием XOR результат будет иметь по меньшей мере такую ​​же энтропию, что и источники.

Обратите внимание, что это означает , а не что вы получаете «лучшие» случайные числа, смешивая выходные данные двух или более генераторов.Статистику истинной случайности трудно поймать людям (достаточно взглянуть на то, насколько плохими были ранние реализации rand()! УЖАСНО!).Лучше выбрать генератор (или набор генераторов для переключения во время компиляции или во время выполнения), который проходит тесты BigCrunch, и обеспечивает хорошее случайное начальное состояние при каждом запуске.Таким образом, вы используете работу многих математиков и других, которые десятилетиями работали над этими вещами, и можете сосредоточиться на других вещах, в чем вы сами хороши.

Answer 2

Код C в статье в Википедии несколько вводит в заблуждение:

Вот рабочий пример, который использует как 32-битную, так и 64-битную версии:

#include <stdio.h>
#include <stdint.h>

/* The state word must be initialized to non-zero */
uint32_t xorshift32(uint32_t state[])
{
  /* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */
  uint32_t x = state[0];
  x ^= x << 13;
  x ^= x >> 17;
  x ^= x << 5;
  state[0] = x;
  return x;
}

uint64_t xorshift64(uint64_t state[])
{
  uint64_t x = state[0];
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  state[0] = x;
  return x;
}

int main()
{
  uint32_t state[1] = {1234};  // "seed" (can be anthing but 0)

  for (int i = 0; i < 50; i++)
  {
    printf("%u\n", xorshift32(state));
  }

  uint64_t state64[1] = { 1234 };  // "seed" (can be anthing but 0)

  for (int i = 0; i < 50; i++)
  {
    printf("%llu\n", xorshift64(state64));
  }
}

Математические аспектыобъяснено в статье в википедии и в ее сносках.

Остальное - базовые знания языка C, ^ - побитовый оператор C XOR.