Как написать генератор случайных чисел и можно ли предсказать Math.random?19.03.2018 12:33

Но в 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<

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;
}

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