Есть ли такая вещь, как случайно доступный генератор псевдослучайных чисел? (предпочтительно с открытым исходным кодом)

В первую очередь, существует такая вещь, как генератор случайных чисел произвольного доступа, где вы могли не только генерировать случайные числа, как мы все привыкли, предполагая, что rand100() всегда генерирует значение от 0 до 100:

for (int i=0;i<5;i++)
   print rand100()

output: 
14
75
36
22
67

но также случайным образом получить доступ к любому случайному значению, например:

rand100 (0) будет выводить 14 до тех пор, пока вы не измените семя

rand100 (3) всегда будет выводить 22

rand100 (4) всегда выводит 67

и т.д.

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

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

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

Ответ 1

семейство PCG генераторов псевдослучайных чисел может прыгать вперед и назад в логарифмическом времени (т.е. прыгать вперед 1000 номеров требует O (log ( 1000))), что, вероятно, достаточно хорошо, чтобы считаться случайным доступом. Реализация C и С++ поддерживает эту функцию.

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

Ответ 2

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

Ответ 3

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

Это класс perlin noise, который можно найти здесь. Я не уверен, насколько это сложно вычислить по сравнению с обычным генератором случайных чисел, что вызывает беспокойство, поскольку одной из плановых платформ является Android. Кроме того, perlin-шум - это не то же самое, что псевдослучайность, но из того, что я могу сказать, значение с высокой октавой и/или частотой должно обеспечивать подходящую случайность для некриптографических целей, где статистический уровень истинной случайности не так важен как простое появление случайности.

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

здесь приведен пример набора регулярной случайной С++ (rand %200) в левом столбце для сравнения и перлинного шума (с эквивалентом %200) справа:

оба были высеяны до 0

параметры шума перлина были

octaves = 8
amplitude = 100 
frequency = 9999
width/height = 10000,100

последовательный порядок выборки для перлингового шума был просто

for (int i=0;i<24;i++)
    floor(Get(i,i)+100);
//amplitude 100 generates noise between -100 and 100, 
//so adding 100 generates between 0 and 200

Ответ 4

Blum Blum Shub - генератор псевдослучайных чисел с посещением и произвольным доступом к любому генерируемому ему значению.

Ответ 5

Как только я прочитал действительно хорошее сообщение в блоге от парня, который работал в Google, который ответил на вопрос, очень похожий на ваш.

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

Например: скажем, вы хотите случайную перетасовку целых чисел от 0 до (2 ^ 32) -1. Вы можете достичь этого, используя блок-шифр, который принимает 4 байта ввода и возвращает 4 зашифрованных байта. Чтобы повторить цикл, сначала "зашифруйте" блок значения 0, затем 1, затем 2 и т.д. Если вам нужно только 1 миллионный элемент в перетасованной последовательности, вы просто зашифруете число 1,000,000.

"Случайные последовательности", которые вы получите с использованием шифрования, отличаются от того, что вы получили бы с помощью хэш-функции (как предлагал @MichaelBurr). Используя шифр, вы можете получить произвольную перестановку целого ряда целых чисел и пробовать любой элемент в этой перестановке в постоянное время. Другими словами, "случайные числа" не будут повторяться. Если вы используете хеш-функцию, числа в последовательности могут повторяться.

Сказав все это, решение @MichaelBurr более подходит для вашей ситуации, и я бы рекомендовал вам его использовать.

Ответ 6

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

Чтобы произвести наши случайные числа, мы предполагаем, что каждая из этих одноразовых прокладок должна быть зациклирована и выборочно выборочно; мы объединяем данные в каждом из них с помощью xor.

#define PRIME1 7001
#define PRIME2 7013
#define PRIME3 7019

static int pad1[PRIME1];
static int pad2[PRIME2];
static int pad3[PRIME3];

static void random_no_init (void)
{
  static int initialized = 0;
  int i;
  if (initialized)
    return;
  for (i = 0; i < PRIME1; i++) pad1[i] = random ();
  for (i = 0; i < PRIME2; i++) pad2[i] = random ();
  for (i = 0; i < PRIME3; i++) pad3[i] = random ();

  initialized = 1;
}

int random_no (int no)
{
   random_no_init ();
   return pad1[no % PRIME1] ^ pad2[no % PRIME2] ^ pad3[no % PRIME3];
}

В приведенном выше примере кода показан простой пример, который дает доступное 344618953247 случайным образом доступное. Чтобы обеспечить воспроизводимые результаты между прогонами, вы должны предоставить генератор случайных чисел семени. Более сложная система, построенная по тому же принципу с вариацией семян на основе выбора разных простых чисел, может быть найдена в http://git.gnome.org/browse/gegl/tree/gegl/gegl-random.c

Ответ 7

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

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

Или создайте длинный список и сохраните его.