Как составить генерацию чисел

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

Случайными числами пользовались с самого зарождения математики. Сегодня их применяют во всевозможных научных изысканиях, при проверке математических теорем, в статистике и т.д. Также случайные числа широко используются в игровой индустрии для генерирования 3D-моделей, текстур и целых миров. Их применяют для создания вариативности поведения в играх и приложениях. 

Есть разные способы получения случайных чисел. Самый простой и понятный — это словари: мы предварительно собираем и сохраняем набор чисел и по мере надобности берём их по очереди. 

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

Сегодня мы с вами поговорим о генераторах псевдослучайных чисел — вычисляемых функциях. К ним предъявляются следующие требования:

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

• Портируемость алгоритма на различные системы. 

• Скорость получения последовательности. Чем быстрее, тем лучше. 

• Повторяемость результата. Это очень важный показатель. От него зависят все компьютерные игры, которые используют генераторы миров и различные системы с аналогичной функциональностью. Воспроизводимость даёт нам общий контент для всех, то есть мы можем генерировать на отдельных клиентах одинаковое содержимое. Также мы можем генерировать контент на лету в зависимости от входных данных, например, от местоположения игрока в мире. Ещё повторяемость случайных чисел используется для сохранения конкретного контента в виде зерна. То есть мы можем держать у себя только какое-то число или массив чисел, на основе которых будут генерироваться нужные нам параметры для заранее отобранного контента.

Зерно

Зерно — это основа генерирования. Оно представляет собой число или вектор чисел, который мы отправляем при инициализации генератора. 

var random = new Random(0);
var rn0 = random.Next();
var rn1 = random.Next();
var rn2 = random.Next();

На иллюстрации просто инициализирован стандартный генератор случайных чисел из стандартной библиотеки C#. При инициализации отправляем в него некоторое число — seed (зерно), — в данном случае это 0. Затем по очереди берём по одному числу методом Next. Но тут мы столкнёмся с первой проблемой: генерирование всегда будет последовательным. Мы не можем получить сразу i-тый элемент последовательности. Для получения второго элемента последовательности необходимо сначала задать зерно, потом вычислить нулевой элемент, за ним первый и только потом уже второй, третий и i-й. 

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

var X = 0;
var Y = 1;
var Z = 2;

var rs0 = new Random(X);
var rs1 = new Random(Y);
var rs2 = new Random(Z);

То есть берём несколько генераторов и задаём им разные зёрна. Но тут мы можем столкнуться со второй проблемой: нельзя гарантировать случайность i-тых элементов разных последовательностей с разными зёрнами. 

На иллюстрации изображён результат генерирования нулевого элемента последовательности с помощью стандартной библиотекой C#. Мы постепенно меняли зерно от 0 до N. 

Качество генератора

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

private static uint GetBytePart(uint i, int byteIndex)
{
   return ((i >> (8 * byteIndex)) % 256 + 256) % 256;
}

public static Color GetColor(uint i)
{
   float r = GetBytePart(i, 0) / 255f;
   float g = GetBytePart(i, 1) / 255f;
   float b = GetBytePart(i, 2) / 255f;
   return new Color(r, g, b);
}

Второй тип изображений — это пространственная интерпретация сгенерированной последовательности. Мы берём первые два бита числа (Х и Y), затем считаем количество попаданий в заданные точки и при визуализации вычитаем из 1 отношение количества попаданий в конкретный пиксель к максимальному количеству попаданий в какой-то другой пиксель. Черные пиксели — это точка, куда мы попадаем чаще всего, а белые — куда мы либо почти, либо совсем не попали. 

var max = 0;
for (var i = 0; i < ints.Length; i += 2)
{
   var x = GetBytePart(ints[i], ByteIndex);
   var y = GetBytePart(ints[i + 1], ByteIndex);
   var value = coords[x, y];
   value++;
   max = Mathf.Max(value, max);
   coords[x, y] = value;
}

Сравнение генераторов

Стандартные средства C#

Ниже я сравнил стандартный генератор из библиотеки С# и линейную последовательность. Первый столбец слева — это случайная последовательность от 0 до N в рамках одного зерна. В центре вверху показаны нулевые элементы случайных последовательностей при разных зёрнах от 0 до N. Вторая линейная последовательность — это числа от 0 до N, которые я визуализировал нашим алгоритмом. 

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

Линейный конгруэнтный генератор (LCG)

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

const long randMax = 4294967296;
state = 214013 * state + 2531011;
state ^= state >> 15;
return (uint) (state % randMax);

При генерировании с одним зерном паттерн нигде не образуется. Но при использовании i-тых элементов в последовательностях с различными зёрнами паттерн начинает прослеживаться. Причём его вид будет зависеть исключительно от коэффициентов, которые мы подобрали для генератора. Например, есть частный случай линейного конгруэнтного генератора — Randu. 

const long randMax = 2147483648;
state = 65539 * state + 0;
return (uint) (state % randMax);

Этот генератор страшен тем, что умножает одно большое число на другое и берёт остаток от деления на 2³¹. В результате формируется вот такая красивая картинка. 

XorShift

Давайте теперь посмотрим на более свежую разработку — XorShift. Этот алгоритм просто выполняет операцию Xor и сдвигает байт в несколько раз. У него тоже будет прослеживаться паттерн для i-тых элементов последовательностей.

state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
return state;

Вихрь Мерсенна

Неужели не существует генераторов без паттерна? Такой генератор есть — это вихрь Мерсенна. У этого алгоритма очень большой период, из-за чего появление паттерна на некотором количестве чисел физически невозможно. Однако и сложность этого алгоритма достаточно велика, в двух словах его не объяснить.

ulong x;
 if (mti >= NN)
 {
  // generate NN words at one time
  for (var i = 0; i < NN - MM; i++)
  {
   x = (mt[i] & UM) | (mt[i + 1] & LM);
   mt[i] = mt[i + MM] 
           ^ (x >> 1) ^ MAG01[(int) (x & 0x1L)];
  }
  for (var i = NN - MM; i < NN - 1; i++)
  {
   x = (mt[i] & UM) | (mt[i + 1] & LM);
   mt[i] = mt[i + (MM - NN)] 
           ^ (x >> 1) ^ MAG01[(int) (x & 0x1L)];
  }
  x = (mt[NN - 1] & UM) | (mt[0] & LM);
  mt[NN - 1] = mt[MM - 1] 
               ^ (x >> 1) ^ MAG01[(int) (x & 0x1L)];
  mti = 0;
 }
 x = mt[mti++];
 x ^= (x >> 29) & 0x5555555555555555L;
 x ^= (x << 17) & 0x71d67fffeda60000L;
 x ^= (x << 37) & 0xfff7eee000000000L;
 x ^= x >> 43;
 return x;

Unity — Random

Из других разработок стоит упомянуть генератор от компании Unity — Random, который используется в наборе стандартных библиотек для работы с Unity. При использовании первых элементов последовательности для разных зёрен у него будет прослеживаться паттерн, но при увеличении индекса паттерн исчезает и получается действительно случайная последовательность. 

Перемешанный конгруэнтный генератор (PCG)

Противоположностью юнитёвского Random’a является перемешанный конгруэнтный генератор. Его особенность в том, что для первых элементов с различными зёрнами отсутствует ярко выраженный паттерн. Но при увеличении индекса он всё же возникает.

Длительность последовательного генерирования

Это важная характеристика генераторов. В таблице приведена длительность для алгоритмов в миллисекундах. Замеры проводились на моём MacBook Pro 2019 года. 

Вихрь Мерсенна работает дольше всего, но даёт качественный результат. Стандартный генератор Random из библиотеки C# подходит для задач, в которых случайность вторична и не имеет какой-то значимой роли, то есть его можно использовать в рамках одного зерна. LCG (линейный конгруэнтный генератор) — это уже более серьёзный алгоритм, но требуется время на подбор нужных коэффициентов, чтобы получить адекватный паттерн. XorShift — самый быстрый алгоритм из всех рассмотренных. Его можно использовать там, где нужно быстро получить случайное значение, но помните про ярко выраженный паттерн с повторяющимся значением. Unity Random и PCG (перемешанный конгруэнтный генератор) сопоставимы по длительности работы, поэтому в разных ситуациях мы можем менять их местами: для длительных последовательностей использовать Unity, а для коротких — PCG.

Альтернатива генераторам — хеш-функции

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

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

Вот пример использования хеш-функции: можно либо создать конкретный класс, отправить туда зерно и постепенно запрашивать только конкретные состояния, либо написать статичную функцию, и отправить туда сразу и зерно, и конкретное состояние. Слева показан алгоритм работы MD5 из стандартной библиотеки C#. 

var hash = new Hash(0);
var rn0 = hash.GetHash(0);
var rn1 = hash.GetHash(1);
var rn2 = hash.GetHash(12);
var rn3 = hash.GetHash(13, 5);

var rn4 = Hash.GetHash(0, 0);
var rn5 = Hash.GetHash(0, 1);
var rn6 = Hash.GetHash(0, 12);
var rn7 = Hash.GetHash(0, 13, 5);

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

class HashRandom
{ 
	private int seed; 
	private int counter;  
	public HashRandom(int seed) 
{  
	this.seed = seed; 
	} 
	public uint Next() 
	{  
	return Hash.GetHash(seed, counter++); 
	}
}

Одни из самых популярных хеш-функций — это MurMur3 и WangHash.

MurMur3 не создаёт паттернов при использованиии i-тых элементов разных последовательностей при разных зёрнах. У WangHash статистические показатели образуют заметный паттерн. Но любую функцию можно прогнать через себя два раза и получить улучшенные показатели, как это показано в правом крайнем столбце WangDoubleHash. 

Также сегодня активно развивается и набирает популярность алгоритм xxHash.

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

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

Оптимизация хеш-функций

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

Что нужно сделать для оптимизации:

1. Убрать функцию включения хвоста. Это операция вставки недостающих элементов в конец массива для хеш-функции. Если его длина меньше требуемой для хеширования, недостающие элементы заполняются определёнными значениями, обычно нулями. 

2. Перевести обработку данных с типа byte на тип int.

3. Избавиться от конвертирования массива byte в одно число int.

Мы можем взять такую реализацию алгоритма xxHash:

uint h32;
var index = 0;
var len = buf.Length;

if (len >= 16)
{ 
	var limit = len - 16; 
	var v1 = seed + P1 + P2; 
	var v2 = seed + P2; 
	var v3 = seed + 0; 
	var v4 = seed - P1; 

	do 
	{  
		v1 = SubHash(v1, buf, index);  
		index += 4;  
		v2 = SubHash(v2, buf, index);  
		index += 4;  
		v3 = SubHash(v3, buf, index);  
		index += 4;  
		v4 = SubHash(v4, buf, index);  index += 4; 
	} while (index <= limit); 

	h32 = Rot32(v1, 1) + Rot32(v2, 7) + Rot32(v3, 12) + Rot32(v4, 18);
}
else
{ 
	h32 = seed + P5;
}
h32 += (uint) len;

while (index <= len — 4)
{ 
	h32 += BitConverter.ToUInt32(buf, index) * P3; 
	h32 = Rot32(h32, 17) * P4; 
	index += 4;
}

while (index < len)
{ 
	h32 += buf[index] * P5; 
	h32 = Rot32(h32, 11) * P1; 
	index++;
}
h32 ^= h32 >> 15;
h32 *= P2;
h32 ^= h32 >> 13;
h32 *= P3;
h32 ^= h32 >> 16;

return h32;

И уменьшить до такой:

public static uint GetHash(int buf, uint seed)
{ 
	var h32 = seed + P5; 
	h32 += 4U; 
	h32 += (uint) buf * P3; 
	h32 = Rot32(h32, 17) * P4; 
	h32 ^= h32 >> 15; 
	h32 *= P2; 
	h32 ^= h32 >> 13; 
	h32 *= P3; 
	h32 ^= h32 >> 16; 
	return h32;
}

Здесь Р1, Р2, Р3, Р4, Р5 — стандартные коэффициенты алгоритма xxHash. 

Комбинированные подходы

Комбинированные подходы бывают двух типов:

1. Сочетание хеш-функции и генератора случайных чисел. 

2. Иерархические генераторы. 

С первым всё предельно просто: берём хеш-функцию и получаем с её помощью зёрна, которые отправляем в другие генераторы. Слева показан результат работы комбинации стандартного Random из библиотеки C#, зёрна которому мы создавали с помощью хеш-функций. 

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

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

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

---

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

JavaScript, Node.JS

---

Рекомендация: подборка платных и бесплатных курсов таргетированной рекламе – https://katalog-kursov.ru/

Генератор псевдослучайных чисел и генератор случайных чисел

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

Этот источник используется для накопления энтропии с последующим получением из неё начального значения (initial value, seed), которое необходимо генераторам случайных чисел (ГСЧ) для формирования случайных чисел.

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

Энтропия?—?это мера беспорядка. Информационная энтропия?—?мера неопределённости или непредсказуемости информации.

Выходит, что чтобы создать псевдослучайную последовательность нам нужен алгоритм, который будет генерить некоторую последовательность на основании определенной формулы. Но такую последовательность можно будет предсказать. Тем не менее, давайте пофантазируем, как бы могли написать свой генератор случайных чисел, если бы у нас не было Math.random()

ГПСЧ имеет некоторый алгоритм, который можно воспроизвести.
ГСЧ?—?это получение чисел полностью из какого либо шума, возможность просчитать который стремится к нулю. При этом в ГСЧ есть определенные алгоритмы для выравнивания распределения.

Придумываем свой алгоритм ГПСЧ

Генератор псевдослучайных чисел (ГПСЧ, англ. pseudorandom number generator, PRNG)?—?алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).

Мы можем взять последовательность каких-то чисел и брать от них модуль числа. Самый простой пример, который приходит в голову. Нам нужно подумать, какую последовательность взять и модуль от чего. Если просто в лоб от 0 до N и модуль 2, то получится генератор 1 и 0:

function* rand() {
  const n = 100;
  const mod = 2;
  let i = 0;
  while (true) {
    yield i % mod;
    if (i++ > n) i = 0;
  }
}
let i = 0;
for (let x of rand()) {
 if (i++ > 100) break;
  console.log(x);
}

Эта функция генерит нам последовательность 01010101010101… и назвать ее даже псевдослучайной никак нельзя. Чтобы генератор был случайным, он должен проходить тест на следующий бит. Но у нас не стоит такой задачи. Тем не менее даже без всяких тестов мы можем предсказать следующую последовательность, значит такой алгоритм в лоб не подходит, но мы в нужном направлении.

А что если взять какую-то известную, но нелинейную последовательность, например число PI. А в качестве значения для модуля будем брать не 2, а что-то другое. Можно даже подумать на тему меняющегося значения модуля. Последовательность цифр в числе Pi считается случайной. Генератор может работать, используя числа Пи, начиная с какой-то неизвестной точки. Пример такого алгоритма, с последовательностью на базе PI и с изменяемым модулем:

const vector = [...Math.PI.toFixed(48).replace('.','')];
function* rand() {
 for (let i=3; i<1000; i++) {
   if (i > 99) i = 2;
    for (let n=0; n<vector.length; n++) {
      yield (vector[n] % i);
    }
  }
}

Но в JS число PI можно вывести только до 48 знака и не более. Поэтому предсказать такую последовательность все так же легко и каждый запуск такого генератора будет выдавать всегда одни и те же числа. Но наш генератор уже стал показывать числа от 0 до 9.

Мы получили генератор чисел от 0 до 9, но распределение очень неравномерное и каждый раз он будет генерировать одну и ту же последовательность.

Мы можем взять не число Pi, а время в числовом представлении и это число рассматривать как последовательность цифр, причем для того, чтобы каждый раз последовательность не повторялась, мы будем считывать ее с конца. Итого наш алгоритм нашего ГПСЧ будет выглядеть так:

function* rand() {
 let newNumVector = () => [...(+new Date)+''].reverse();
 let vector = newNumVector();
 let i=2;
 while (true) {
    if (i++ > 99) i = 2;
    let n=-1;
    while (++n < vector.length) yield (vector[n] % i);
    vector = newNumVector();
  }
}

// TEST:
let i = 0;
for (let x of rand()) {
  if (i++ > 100) break;
  console.log(x)
}

Вот это уже похоже на генератор псевдослучайных чисел. И тот же Math.random()?—?это ГПСЧ, про него мы поговорим чуть позже. При этом у нас каждый раз первое число получается разным.

Собственно на этих простых примерах можно понять как работают более сложные генераторы случайных числе. И есть даже готовые алгоритмы. Для примера разберем один из них?—?это Линейный конгруэнтный ГПСЧ(LCPRNG).

Линейный конгруэнтный ГПСЧ

Линейный конгруэнтный ГПСЧ(LCPRNG)?—?это распространённый метод для генерации псевдослучайных чисел. Он не обладает криптографической стойкостью. Этот метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой формулой. Получаемая последовательность зависит от выбора стартового числа?—?т.е. seed. При разных значениях seed получаются различные последовательности случайных чисел. Пример реализации такого алгоритма на JavaScript:

const a = 45;
const c = 21;
const m = 67;
var seed = 2;
const rand = () => seed = (a * seed + c) % m;
for(let i=0; i<30; i++)
  console.log( rand() )

Многие языки программирования используют LСPRNG (но не именно такой алгоритм(!)).

Как говорилось выше, такую последовательность можно предсказать. Так зачем нам ГПСЧ? Если говорить про безопасность, то ГПСЧ?—?это проблема. Если говорить про другие задачи, то эти свойства?—?могут сыграть в плюс. Например для различных спец эффектов и анимаций графики может понадобиться частый вызов random. И вот тут важны распределение значений и перформанс! Секурные алгоритмы не могут похвастать скоростью работы.

Еще одно свойство?—?воспроизводимость. Некоторые реализации позволяют задать seed, и это очень полезно, если последовательность должна повторяться. Воспроизведение нужно в тестах, например. И еще много других вещей существует, для которых не нужен безопасный ГСЧ.

Как устроен Math.random()

Метод Math.random() возвращает псевдослучайное число с плавающей запятой из диапазона [0, 1), то есть, от 0 (включительно) до 1 (но не включая 1), которое затем можно отмасштабировать до нужного диапазона. Реализация сама выбирает начальное зерно для алгоритма генерации случайных чисел; оно не может быть выбрано или сброшено пользователем.

Как устроен алгоритм Math.random()?—?интересный вопрос. До недавнего времени, а именно до 49 Chrome использовался алгоритм MWC1616:

uint32_t state0 = 1;
uint32_t state1 = 2;
uint32_t mwc1616() {
   state0 = 18030 * (state0 & 0xffff) + (state0 >> 16);
   state1 = 30903 * (state1 & 0xffff) + (state1 >> 16);
   return (state0 << 16) + (state1 & 0xffff);
}

Именно этот алгоритм генерит нам последовательность псевдослучайных чисел в промежутке между 0 и 1.

Предсказываем Math.random()

Чем это было чревато? Есть такой квест: alf.nu/ReturnTrue

В нем есть задача:

{
	let rand = Math.random();
	function random4(x) {
	    return rand === x;
	}
}

random4(???)

Что нужно вписать вместо вопросов, чтобы функция вернула true? Кажется что это невозможно. Но, это возможно, если вы заглядывали в спеку и видели алгоритм ГПСЧ V8. Решение этой задачи в свое время мне показал Роман Дворнов:

random4(function(){var A=18030,B=36969,F=65535,Z=16,M=Math,I=M.imul,c=M.random,M=M.pow(2,32),k,d,g=c()*M,h=c()*M;for(k=0;F^k&&(c=I(A,g>>>Z)+k++)&F^h>>>Z;);for(k=0;F^k&&(d=I(B,g&F)+k++)&F^h&F;);for(k=2;k—;g=c<<Z|d&F)c=c/A|c%A<<Z,d=d/B|d%B<<Z;return(g<0?g+M:g)/M}())

Этот код работал в 70% случаев для Chrome < 49 и Node.js < 5. Рома Дворнов, как всегда, показал чудеса магии, которая не что иное, как глубокое понимание внутренних механизмов браузеров. Я все жду, когда Роман сделает доклад на основе этих событий или напишет более подробную статью.

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

Видите эти равномерности на левом слайде? Изображение показывает проблему с распределением значений. На картинке слева видно, что значения местами сильно группируются, а местами выпадают большие фрагменты. Как следствие?—?числа можно предсказать.

Выходит что мы можем отреверсить Math.random() и предсказать, какое было загадано число на основе того, что получили в данный момент времени. Для этого получаем два значения через Math.random(). Затем вычисляем внутреннее состояние по этим значениям. Имея внутреннее состояние можем предсказывать следующие значения Math.random() при этом не меняя внутреннее состояние. Меняем код так так, чтобы вместо следующего возвращалось предыдущее значение. Собственно все это и описано в коде-решении для задачи random4. Но потом алгоритм изменили (подробности читайте в спеке). Его можно будет сломать, как только у нас в JS появится нормальная работа с 64 битными числами. Но это уже будет другая история.

Новый алгоритм выглядит так:

uint64_t state0 = 1;
uint64_t state1 = 2;
uint64_t xorshift128plus() {
   uint64_t s1 = state0;
   uint64_t s0 = state1;
   state0 = s0;
   s1 ^= s1 << 23;
   s1 ^= s1 >> 17;
   s1 ^= s0;
   s1 ^= s0 >> 26;
   state1 = s1;
   return state0 + state1;
}

Его все так же можно будет просчитать и предсказать. Но пока у нас нет “длинной математики” в JS. Можно попробовать через TypedArray сделать или использовать специальные библиотеки. Возможно кто-то однажды снова напишет предсказатель. Возможно это будешь ты, читатель. Кто знает 😉

Сrypto Random Values

Метод Math.random() не предоставляет криптографически стойкие случайные числа. Не используйте его ни для чего, связанного с безопасностью. Вместо него используйте Web Crypto API (API криптографии в вебе) и более точный метод window.crypto.getRandomValues().

Пример генерации случайного числа:

let [rvalue] = crypto.getRandomValues(new Uint8Array(1));
console.log( rvalue )

Но, в отличие от ГПСЧ Math.random(), этот метод очень ресурсоемкий. Дело в том, что данный генератор использует системные вызовы в ОС, чтобы получить доступ к источникам энтропии (мак адрес, цпу, температуре, etc…).

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

Содержание

• Как использовать модуль random в Python
• Генерация случайных чисел в Python
• Выбор случайного элемента из списка
• Python функции модуля random
• Случайное целое число — randint(a, b)
• Генерация случайного целого числа — randrange()
• Выбор случайного элемента из списка choice()
• Метод sample(population, k)
• Случайные элементы из списка — choices()
• Генератор псевдослучайных чисел — seed()
• Перемешивание данных — shuffle()
• Генерации числа с плавающей запятой — uniform()
• triangular(low, high, mode)
• Генератор случайной строки в Python
• Криптографическая зашита генератора случайных данных в Python
• getstate() и setstate() в генераторе случайных данных Python
• Состояние генератора getstate()
• Восстанавливает внутреннее состояние генератора — setstate()
• Зачем нужны функции getstate() и setstate()
• Numpy.random — Генератор псевдослучайных чисел
• Генерация случайного n-мерного массива вещественных чисел
• Генерация случайного n-мерного массива целых чисел
• Выбор случайного элемента из массива чисел или последовательности
• Генерация случайных универсально уникальных ID
• Игра в кости с использованием модуля random в Python

Список методов модуля random в Python:

Метод	Описание
seed()	Инициализация генератора случайных чисел
getstate()	Возвращает текущее внутренне состояние (state) генератора случайных чисел
setstate()	Восстанавливает внутреннее состояние (state) генератора случайных чисел
getrandbits()	Возвращает число, которое представляет собой случайные биты
randrange()	Возвращает случайное число в пределах заданного промежутка
randint()	Возвращает случайное число в пределах заданного промежутка
choice()	Возвращает случайный элемент заданной последовательности
choices()	Возвращает список со случайной выборкой из заданной последовательности
shuffle()	Берет последовательность и возвращает ее в перемешанном состоянии
sample()	Возвращает заданную выборку последовательности
random()	Возвращает случайное вещественное число в промежутке от 0 до 1
uniform()	Возвращает случайное вещественное число в указанном промежутке
triangular()	Возвращает случайное вещественное число в промежутке между двумя заданными параметрами. Также можно использовать параметр mode для уточнения середины между указанными параметрами
betavariate()	Возвращает случайное вещественное число в промежутке между 0 и 1, основываясь на Бета-распределении, которое используется в статистике
expovariate()	Возвращает случайное вещественное число в промежутке между 0 и 1, или же между 0 и -1, когда параметр отрицательный. За основу берется Экспоненциальное распределение, которое используется в статистике
gammavariate()	Возвращает случайное вещественное число в промежутке между 0 и 1, основываясь на Гамма-распределении, которое используется в статистике
gauss()	Возвращает случайное вещественное число в промежутке между 0 и 1, основываясь на Гауссовом распределении, которое используется в теории вероятности
lognormvariate()	Возвращает случайное вещественное число в промежутке между 0 и 1, основываясь на Логнормальном распределении, которое используется в теории вероятности
normalvariate()	Возвращает случайное вещественное число в промежутке между 0 и 1, основываясь на Нормальном распределении, которое используется в теории вероятности
vonmisesvariate()	Возвращает случайное вещественное число в промежутке между 0 и 1, основываясь на распределении фон Мизеса, которое используется в направленной статистике
paretovariate()	Возвращает случайное вещественное число в промежутке между 0 и 1, основываясь на распределении Парето, которое используется в теории вероятности
weibullvariate()	Возвращает случайное вещественное число в промежутке между 0 и 1, основываясь на распределении Вейбулла, которое используется в статистике

Цели данной статьи

Далее представлен список основных операций, которые будут описаны в руководстве:

• Генерация случайных чисел для различных распределений, которые включают целые и вещественные числа с плавающей запятой;
• Случайная выборка нескольких элементов последовательности population;
• Функции модуля random;
• Перемешивание элементов последовательности. Seed в генераторе случайных данных;
• Генерация случайных строки и паролей;
• Криптографическое обеспечение безопасности генератора случайных данных при помощи использования модуля secrets. Обеспечение безопасности токенов, ключей безопасности и URL;
• Способ настройки работы генератора случайных данных;
• Использование numpy.random для генерации случайных массивов;
• Использование модуля UUID для генерации уникальных ID.

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

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

В самом начале работы необходимо импортировать модуль random в программу. Только после этого его можно будет полноценно использовать. Оператор для импорта модуля random выглядит следующим образом:

Теперь рассмотрим использование самого модуля random на простом примере:

Вывод:

Как видите, в результате мы получили 0.9461613475266107. У вас, конечно, выйдет другое случайно число.

• random() является базовой функцией модуля random;
• Почти все функции модуля random зависят от базовой функции random();
• random() возвращает следующее случайное число с плавающей запятой в промежутке [0.0, 1.0].

Перед разбором функций модуля random давайте рассмотрим основные сферы их применения.

Генерация случайных чисел в Python

Давайте рассмотрим самый популярный случай использования модуля random — генерацию случайного числа. Для получения случайного целого числа в Python используется функция randint().

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

• randint()
• randrange()

В следующем примере показано, как получить случайно сгенерированное число в промежутке между 0 и 9.

Вывод:

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

Выбор случайного элемента из списка Python

Предположим, вам дан python список городов, и вы хотите вывести на экран случайно выбранный элемент из списка городов. Посмотрим, как это можно сделать:

Вывод:

Python функции модуля random

Рассмотрим разнообразные функции, доступные в модуле random.

Случайное целое число — randint(a, b) модуль random

• Возвращает случайное целое число Number, такое что a <= Number <= b;
• randint(a,b) работает только с целыми числами;
• Функция randint(a,b) принимает только два параметра, оба обязательны;
• Полученное в результате случайно число больше или равно a, а также меньше или равно b.

Пример использования random.randint() в Python:

Вывод:

Генерация случайного целого числа — randrange() модуль random

Метод random.randrange() используется для генерации случайного целого числа в пределах заданного промежутка. Скажем, для получения любого числа в диапазоне между 10 и 50.

Шаг показывает разницу между каждым числом заданной последовательности. Шаг по умолчанию равен 1, однако его значение можно изменить.

Пример использования random.randrange() в Python:

Вывод:

Выбор случайного элемента из списка choice() модуль random

Метод random.choice() используется для выбора случайного элемента из списка. Набор может быть представлен в виде списка или python строки. Метод возвращает один случайный элемент последовательности.

Пример использования random.choice() в Python:

Вывод:

Метод sample(population, k) из модуля random

Метод random.sample() используется, когда требуется выбрать несколько элементов из заданной последовательности population.

• Метод sample() возвращает список уникальных элементов, которые были выбраны из последовательности population. Итоговое количество элементов зависит от значения k;
• Значение в population может быть представлено в виде списка или любой другой последовательности.

Пример использования random.sample() в Python:

Вывод:

Случайные элементы из списка — choices() модуль random

• random.choices(population, weights=None, *, cum_weights=None, k=1)
• Метод random.choices() используется, когда требуется выбрать несколько случайных элементов из заданной последовательности.
• Метод choices() был введен в версии Python 3.6. Он также позволяет повторять несколько раз один и тот же элемент.

Пример использования random.choices() в Python:

Вывод:

Генератор псевдослучайных чисел —  seed() модуль random

• Метод seed() используется для инициализации генератора псевдослучайных чисел в Python;
• Модуль random использует значение из seed, или отправной точки как основу для генерации случайного числа. Если значения seed нет в наличии, тогда система будет отталкиваться от текущего времени.

Пример использования random.seed() в Python:

Вывод:

Перемешивание данных — shuffle() из модуля random

Метод random.shuffle() используется для перемешивания данных списка или другой последовательности. Метод shuffle() смешивает элементы списка на месте. Самый показательный пример использования — тасование карт.

Пример использования random.shuffle() в Python:

Вывод:

Генерации числа с плавающей запятой — uniform() модуль random

• random.uniform() используется для генерации числа с плавающей запятой в пределах заданного промежутка
• Значение конечной точки может включаться в диапазон, но это не обязательно. Все зависит от округления значения числа с плавающей запятой;
• Метод может, например, сгенерировать случайно вещественное число в промежутке между 10.5 и 25.5.

Пример использования random.uniform() в Python:

Вывод:

triangular(low, high, mode) из модуля random

Функция random.triangular() возвращает случайное вещественное число N с плавающей запятой, которое соответствует условию lower <= N <= upper, а также уточняющему значению mode.

Значение нижнего предела по умолчанию равно нулю, в верхнего — единице. Кроме того, пик аргумента по умолчанию установлен на середине границ, что обеспечивает симметричное распределение.

Функция random.triangular() используется в генерации случайных чисел для треугольного распределения с целью использования полученных значений в симуляции. Это значит, что в при генерации значения применяется треугольное распределение вероятности. 

Пример использования random.triangular() в Python:

Вывод:

Генератор случайной строки в Python

В данном разделе будет подробно расписано, как сгенерировать случайную строку фиксированной длины в Python.

Основные аспекты раздела:

• Генерация случайной строки фиксированной длины;
• Получение случайной алфавитно-цифровой строки, среди элементов которой будут как буквы, так и числа;
• Генерация случайного пароля, который будет содержать буквы, цифры и специальный символы.

Криптографическая зашита генератора случайных данных в Python

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

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

• Все функции криптографически надежного генератора возвращают полученные случайным образом байты;
• Значение случайных байтов, полученных в результате использования функции, зависит от источников ОС.
• Качество генерации также зависит от случайных источников ОС.

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

• Применение модуля secrets для защиты случайных данных;
• Использование из модуля os os.urandom();
• Использование класса random.SystemRandom.

Пример криптографически надежной генерации данных в Python:

Вывод:

getstate() и setstate() в генераторе случайных данных Python

Функции getstate() и setstate() модуля random позволяют зафиксировать текущее внутреннее состояние генератора.

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

Состояние генератора getstate() модуль random

Функция getstate() возвращает определенный объект, зафиксировав текущее внутреннее состояние генератора случайных данных. Данное состояние передается методу setstate() для восстановления полученного состояния в качестве текущего.

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

Восстанавливает внутреннее состояние генератора — setstate() модуль random

Функция setstate() восстанавливает внутреннее состояние генератора и передает его состоянию объекта. Это значит, что вновь будет использован тот же параметр состояния state. Объект state может быть получен при помощи вызова функции getstate().

Зачем нужны функции getstate() и setstate() ?

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

Для закрепления понимания принципов работы getstate() и setstate() в генераторе случайных данных Python рассмотрим следующий пример:

Вывод:

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

Numpy.random — Генератор псевдослучайных чисел

PRNG является англоязычным акронимом, который расшифровывается как «pseudorandom number generator» — генератор псевдослучайных чисел. Известно, что в Python модуль random можно использовать для генерации случайных скалярных числовых значений и данных.

• Для генерации массива случайных чисел необходимо использовать numpy.random();
• В модуле numpy есть пакет numpy.random, который содержит обширный набор функций для генерации случайных n-мерных массивов для различных распределений.

Рассмотрим несколько примеров использования numpy.random в Python.

Генерация случайного n-мерного массива вещественных чисел

• Использование numpy.random.rand() для генерации n-мерного массива случайных вещественных чисел в пределах [0.0, 1.0)
• Использование numpy.random.uniform() для генерации n-мерного массива случайных вещественных чисел в пределах [low, high)

Вывод:

Генерация случайного n-мерного массива целых чисел

Для генерации случайного n-мерного массива целых чисел используется numpy.random.random_integers():

Вывод:

Выбор случайного элемента из массива чисел или последовательности

• Использование numpy.random.choice() для генерации случайной выборки;
• Использование данного метода для получения одного или нескольких случайных чисел из n-мерного массива с заменой или без нее.

Рассмотрим следующий пример:

Вывод:

В будущих статьях будут описаны другие функции пакета random из nympy и способы их использования.

Генерация случайных универсально уникальных ID

Модуль Python UUID предоставляет неизменяемые UUID объекты. UUID является универсально уникальным идентификатором.

У модуля есть функции для генерации всех версий UUID. Используя функцию uuid.uuid4(), можно получить случайно сгенерированное уникальное ID длиной в 128 битов, которое к тому же является криптографически надежным.

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

Пример использования uuid.uuid4() в Python:

Вывод:

Игра в кости с использованием модуля random в Python

Далее представлен код простой игры в кости, которая поможет понять принцип работы функций модуля random. В игре два участника и два кубика.

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

Код программы для игры в кости Python:

Вывод:

Вот и все. Оставить комментарии можете в секции ниже.