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

Question

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

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

output: 
14
75
36
22
67

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

rand100 (0) выдаст 14, если вы не изменили начальное значение

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

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

и так далее ...

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

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

Вот пример набора обычной случайности c ++ (rand% 200) в левом столбце для сравнения и перлин-шума (с эквивалентом% 200) справа:

91 , 100
48 , 97
5 , 90
93 , 76
197 , 100
97 , 114
132 , 46
190 , 67
118 , 103
78 , 96
143 , 110
187 , 108
139 , 79
69 , 58
156 , 81
123 , 128
84 , 98
15 , 105
178 , 117
10 , 82
13 , 110
182 , 56
10 , 96
144 , 64
133 , 105

оба были посеяны до 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

Answer 5

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

Чтобы получить наши случайные числа, мы представляем, что каждая из этих одноразовых площадок циклично зацикливается и дискретизируется постепенно;мы объединяем данные в каждом из них, используя 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

Answer 6

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

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

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

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

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

Answer 7

взгляните на этот патент: Генератор случайных чисел псевдо с произвольным доступом https://patents.google.com/patent/US4791594

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

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

Answer 8

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

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

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