Какая поддельная случайная функция, которая генерирует наиболее, казалось бы, случайное число от 0 до 1? - PullRequest
Новая
       94

Какая поддельная случайная функция, которая генерирует наиболее, казалось бы, случайное число от 0 до 1?

0 голосов
/ 20 мая 2019

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

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

Если честно, я хочу, чтобы алгоритм генерировал случайное число параллельно (и могло использоваться в GPU) только со случайным начальным числом в начале и индексом каждого элементав качестве входных данных

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

edit: спасибоВам для вас все предложение.У меня есть более четкое представление о том, что я хочу, и которое я могу объяснить

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

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

И буду более благодарен, если это очень быстрый алгоритм

Ответы [ 2 ]

3 голосов
/ 20 мая 2019

Есть несколько вариантов «чистых» случайных функций.Они включают в себя:

  • Хеш-функция.
  • Функция, которая заполняет генератор псевдослучайных чисел (PRNG) своим входом и возвращает вывод этого PRNG.
  • Функциякоторый принимает внутреннее состояние и выводит случайные числа и новое внутреннее состояние (этот подход хорошо подходит для Haskell и других функциональных языков программирования).

См. также мою статью по проектам для PRNG или статья L'Ecuyer, Munger и др. "Случайные числа для параллельных компьютеров: требования и методы с упором на графические процессоры" (2015).

Что касается хэш-функций для использования существуют различные варианты, в том числе SHA-1, SHA-256, xxHash, MurmurHash3 и другие;некоторые хеш-функции могут быть более подходящими, чем другие, в зависимости от того, требуется ли вам защита, помимо других факторов.

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

1 голос
/ 21 мая 2019

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

Поддельная случайная функция обычно называется генераторами псевдослучайных чисел (PRNG).

Вас могут заинтересовать двойники в [0 ...1) диапазон, но PRNG обычно генерирует одно целое число 64-битное (хорошо для двойного) или 32-битное (хорошо для поплавка).Преобразование в double, хотя и не совсем тривиально, довольно простая операция .

Типичный PRNG имеет состояние, инициируемое с начальным числом и выходом.Для простейших PRNG (таких как LCG) начальное значение, состояние и выход - это одно и то же, но в целом это не так.Обычно состояние характеризуется количеством битов (скажем, 64 бит для LCG до 19937 бит для Mersenne twister).

Создание чистых функций из любого алгоритма PRNG довольно просто - PRNG - это просто набор из трех функций в формеиз 

state_type make_state(seed_type seed) {
    // convert seeding to state, bits chopping
    return new_state;
}

state_type advance_state(state_type old_state) {
    // do bits chopping with old state
    // and advance to the next state
    return new_state;
}

uint64_t generate_output(state_type state) {
    // extract 64bits of randomness from state
    return new_random_number;
}

И это все, в PRNG больше нет ничего, кроме этих функций.

И, к вопросу под рукой

  1. Вы можете использовать некриптный хеш с хорошими лавинными свойствами , что в основном означает, что изменение входного значения на один бит (входное значение увеличено на 1) вызывает большие изменения выходного сигнала.Быстро, разумно, может быть не очень случайно.С шумом все в порядке, а также с Маминым хэшем .

  2. Крипто-шифр работает в режиме счетчика.Медленнее, чем вариант 1, но цифры высокого качества.Относительно большое состояние (скажем, 512 бит или около того).Я предпочитаю ChaCha20 - это хорошо известно, достаточно быстро, посмотрите код здесь .Оба варианта 1 и 2 предполагают, что в качестве входных данных используется только линейно увеличивающийся счетчик.

  3. Другой вариант - использование PRNG, который имеет функцию скачка вперед с логарифмической сложностью.Это можно начать с глобального семени, и если у вас есть 2 10 ядер CUDA, ваше первое ядро ​​будет использовать семя, второе будет прыгать вперед на 2 64 / 2 10 = 2 54 , что при сложности O (log 2 (N)) составляет всего 54 операции, третья будет прыгать впереди второй на 2 54 шаги и 54 операции и так далее и тому подобное.Из известных PRNG логарифмический скачок вперед работает для LCG, а также PCG .Я бы порекомендовал посмотреть на PCG.

Это означает, что есть нетривиальная функция в виде 

state_type advance_state(state_type old_state, int64_t distance) {
    // non-trivial advance by distance
    // non-trivial means it is not just a loop, it is better than linear algorithm
    return new_state;
}
...