Seedable JavaScript генератор случайных чисел
JavaScript Math.random() Функция возвращает случайное значение от 0 до 1, автоматически посеянное в зависимости от текущего времени (похоже на Java, я считаю). Тем не менее, я не думаю, что есть какой-то способ установить для вас свое семя.
Как я могу сделать генератор случайных чисел, для которого я могу предоставить свое собственное начальное значение, чтобы он мог генерировать повторяемую последовательность (псевдо) случайных чисел?
12 ответов
Одним из вариантов является http://davidbau.com/seedrandom который представляет собой замену Math.random() на основе RC4 с возможностью вставки с хорошими свойствами.
Если вам не нужна возможность высева, просто используйте Math.random() и построить вспомогательные функции вокруг него (например, randRange(start, end)).
Я не уверен, какую ГСЧ вы используете, но лучше знать и документировать ее, чтобы вы знали о ее характеристиках и ограничениях.
Как сказал Старкий, Mersenne Twister - хороший PRNG, но его нелегко реализовать. Если вы хотите сделать это сами, попробуйте внедрить LCG - это очень просто, обладает хорошими качествами случайности (не так хороши, как у Mersenne Twister), и вы можете использовать некоторые популярные константы.
function RNG(seed) {
// LCG using GCC's constants
this.m = 0x80000000; // 2**31;
this.a = 1103515245;
this.c = 12345;
this.state = seed ? seed : Math.floor(Math.random() * (this.m - 1));
}
RNG.prototype.nextInt = function() {
this.state = (this.a * this.state + this.c) % this.m;
return this.state;
}
RNG.prototype.nextFloat = function() {
// returns in range [0,1]
return this.nextInt() / (this.m - 1);
}
RNG.prototype.nextRange = function(start, end) {
// returns in range [start, end): including start, excluding end
// can't modulu nextInt because of weak randomness in lower bits
var rangeSize = end - start;
var randomUnder1 = this.nextInt() / this.m;
return start + Math.floor(randomUnder1 * rangeSize);
}
RNG.prototype.choice = function(array) {
return array[this.nextRange(0, array.length)];
}
var rng = new RNG(20);
for (var i = 0; i < 10; i++)
console.log(rng.nextRange(10, 50));
var digits = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
for (var i = 0; i < 10; i++)
console.log(rng.choice(digits));Если вы хотите иметь возможность указать начальное число, вам просто нужно заменить вызовы на getSeconds() а также getMinutes(), Вы можете передать int и использовать половину его mod 60 для значения секунд, а другую половину по модулю 60, чтобы дать вам другую часть.
При этом, этот метод выглядит как мусор. Делать правильную генерацию случайных чисел очень сложно. Очевидная проблема заключается в том, что начальное число случайных чисел основано на секундах и минутах. Чтобы угадать начальное число и воссоздать ваш поток случайных чисел, нужно всего лишь попробовать 3600 различных секундных и минутных комбинаций. Это также означает, что есть только 3600 различных возможных семян. Это исправимо, но я бы с самого начала с подозрением отнесся к этому ГСЧ.
Если вы хотите использовать более качественный ГСЧ, попробуйте Mersenne Twister. Это хорошо протестированный и достаточно надежный ГСЧ с огромной орбитой и отличной производительностью.
РЕДАКТИРОВАТЬ: Я действительно должен быть правильным и относиться к этому как генератор псевдослучайных чисел или PRNG.
"Любой, кто использует арифметические методы для получения случайных чисел, находится в состоянии греха".
--- Джон фон Нейман
Я использую порт JavaScript Mersenne Twister: https://gist.github.com/300494 Это позволяет вам установить начальное значение вручную. Кроме того, как уже упоминалось в других ответах, Mersenne Twister - действительно хороший PRNG.
Код, который вы перечислили, выглядит как Lehmer RNG. Если это так, то 2147483647 самое большое 32-разрядное целое число со знаком, 2147483647 является крупнейшим 32-разрядным простым, и 48271 множитель полного периода, который используется для генерации чисел
Если это правда, вы можете изменить RandomNumberGenerator принять дополнительный параметр seed, а затем установить this.seed в seed; но вы должны быть осторожны, чтобы убедиться, что начальное число приведет к хорошему распределению случайных чисел (Лемер может показаться странным), но с большинством семян все будет в порядке.
Ниже приведен PRNG, который можно подавать на заказ. призвание SeedRandom вернет случайную функцию генератора. SeedRandom может вызываться без аргументов, чтобы заполнить возвращаемую случайную функцию текущим временем, или она может быть вызвана с 1 или 2 неотрицательными числами в качестве аргументов, чтобы заполнить ее этими целыми числами. Из-за точности с плавающей точкой, заполнение только одним значением позволит генератору переключиться в одно из 2^53 различных состояний.
Возвращенная функция генератора случайных значений принимает 1 целочисленный аргумент limit, предел должен быть в диапазоне от 1 до 4294965886, функция вернет число в диапазоне от 0 до предела-1.
function SeedRandom(state1,state2){
var mod1=4294967087
var mul1=65539
var mod2=4294965887
var mul2=65537
if(typeof state1!="number"){
state1=+new Date()
}
if(typeof state2!="number"){
state2=state1
}
state1=state1%(mod1-1)+1
state2=state2%(mod2-1)+1
function random(limit){
state1=(state1*mul1)%mod1
state2=(state2*mul2)%mod2
if(state1<limit && state2<limit && state1<mod1%limit && state2<mod2%limit){
return random(limit)
}
return (state1+state2)%limit
}
return random
}
Пример использования:
var generator1=SeedRandom() //Seed with current time
var randomVariable=generator1(7) //Generate one of the numbers [0,1,2,3,4,5,6]
var generator2=SeedRandom(42) //Seed with a specific seed
var fixedVariable=generator2(7) //First value of this generator will always be
//1 because of the specific seed.
Этот генератор обладает следующими свойствами:
- Он имеет примерно 2^64 различных возможных внутренних состояний.
- Он имеет период приблизительно 2^63, что намного больше, чем кто-либо когда-либо реально будет нуждаться в программе JavaScript.
- Из-за
modзначения, являющиеся простыми числами, не имеют простого шаблона на выходе, независимо от выбранного предела. Это не похоже на некоторые более простые PRNG, которые демонстрируют некоторые довольно систематические закономерности. - Он отбрасывает некоторые результаты, чтобы получить идеальное распределение независимо от предела.
- Это относительно медленно, работает около 10 000 000 раз в секунду на моей машине.
Если вы программируете на Typescript, я адаптировал реализацию Mersenne Twister, приведенную в ответе Кристофа Хенкельмана на этот поток, как класс машинописного текста:
/**
* copied almost directly from Mersenne Twister implementation found in https://gist.github.com/banksean/300494
* all rights reserved to him.
*/
export class Random {
static N = 624;
static M = 397;
static MATRIX_A = 0x9908b0df;
/* constant vector a */
static UPPER_MASK = 0x80000000;
/* most significant w-r bits */
static LOWER_MASK = 0x7fffffff;
/* least significant r bits */
mt = new Array(Random.N);
/* the array for the state vector */
mti = Random.N + 1;
/* mti==N+1 means mt[N] is not initialized */
constructor(seed:number = null) {
if (seed == null) {
seed = new Date().getTime();
}
this.init_genrand(seed);
}
private init_genrand(s:number) {
this.mt[0] = s >>> 0;
for (this.mti = 1; this.mti < Random.N; this.mti++) {
var s = this.mt[this.mti - 1] ^ (this.mt[this.mti - 1] >>> 30);
this.mt[this.mti] = (((((s & 0xffff0000) >>> 16) * 1812433253) << 16) + (s & 0x0000ffff) * 1812433253)
+ this.mti;
/* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
/* In the previous versions, MSBs of the seed affect */
/* only MSBs of the array mt[]. */
/* 2002/01/09 modified by Makoto Matsumoto */
this.mt[this.mti] >>>= 0;
/* for >32 bit machines */
}
}
/**
* generates a random number on [0,0xffffffff]-interval
* @private
*/
private _nextInt32():number {
var y:number;
var mag01 = new Array(0x0, Random.MATRIX_A);
/* mag01[x] = x * MATRIX_A for x=0,1 */
if (this.mti >= Random.N) { /* generate N words at one time */
var kk:number;
if (this.mti == Random.N + 1) /* if init_genrand() has not been called, */
this.init_genrand(5489);
/* a default initial seed is used */
for (kk = 0; kk < Random.N - Random.M; kk++) {
y = (this.mt[kk] & Random.UPPER_MASK) | (this.mt[kk + 1] & Random.LOWER_MASK);
this.mt[kk] = this.mt[kk + Random.M] ^ (y >>> 1) ^ mag01[y & 0x1];
}
for (; kk < Random.N - 1; kk++) {
y = (this.mt[kk] & Random.UPPER_MASK) | (this.mt[kk + 1] & Random.LOWER_MASK);
this.mt[kk] = this.mt[kk + (Random.M - Random.N)] ^ (y >>> 1) ^ mag01[y & 0x1];
}
y = (this.mt[Random.N - 1] & Random.UPPER_MASK) | (this.mt[0] & Random.LOWER_MASK);
this.mt[Random.N - 1] = this.mt[Random.M - 1] ^ (y >>> 1) ^ mag01[y & 0x1];
this.mti = 0;
}
y = this.mt[this.mti++];
/* Tempering */
y ^= (y >>> 11);
y ^= (y << 7) & 0x9d2c5680;
y ^= (y << 15) & 0xefc60000;
y ^= (y >>> 18);
return y >>> 0;
}
/**
* generates an int32 pseudo random number
* @param range: an optional [from, to] range, if not specified the result will be in range [0,0xffffffff]
* @return {number}
*/
nextInt32(range:[number, number] = null):number {
var result = this._nextInt32();
if (range == null) {
return result;
}
return (result % (range[1] - range[0])) + range[0];
}
/**
* generates a random number on [0,0x7fffffff]-interval
*/
nextInt31():number {
return (this._nextInt32() >>> 1);
}
/**
* generates a random number on [0,1]-real-interval
*/
nextNumber():number {
return this._nextInt32() * (1.0 / 4294967295.0);
}
/**
* generates a random number on [0,1) with 53-bit resolution
*/
nextNumber53():number {
var a = this._nextInt32() >>> 5, b = this._nextInt32() >>> 6;
return (a * 67108864.0 + b) * (1.0 / 9007199254740992.0);
}
}
Вы можете использовать его следующим образом:
var random = new Random(132);
random.nextInt32(); //return a pseudo random int32 number
random.nextInt32([10,20]); //return a pseudo random int in range [10,20]
random.nextNumber(); //return a a pseudo random number in range [0,1]
проверьте источник для других методов.
Вот довольно эффективная, но простая функция PRNG javascript, которую я люблю использовать:
// The seed is the base number that the function works off
// The modulo is the highest number that the function can return
function PRNG(seed, modulo) {
str = `${(2**31-1&Math.imul(48271,seed))/2**31}`
.split('')
.slice(-10)
.join('') % modulo
return str
}
Надеюсь, это то, что вы ищете.
Примечание: этот код был изначально включен в вопрос выше. В целях краткости и сфокусированности вопроса я переместил его в этот ответ сообщества Wiki.
Я обнаружил, что этот код работает, и он работает нормально для получения случайного числа и последующего использования начального числа, но я не совсем уверен, как работает логика (например, откуда взялись числа 2345678901, 48271 и 2147483647).
function nextRandomNumber(){
var hi = this.seed / this.Q;
var lo = this.seed % this.Q;
var test = this.A * lo - this.R * hi;
if(test > 0){
this.seed = test;
} else {
this.seed = test + this.M;
}
return (this.seed * this.oneOverM);
}
function RandomNumberGenerator(){
var d = new Date();
this.seed = 2345678901 + (d.getSeconds() * 0xFFFFFF) + (d.getMinutes() * 0xFFFF);
this.A = 48271;
this.M = 2147483647;
this.Q = this.M / this.A;
this.R = this.M % this.A;
this.oneOverM = 1.0 / this.M;
this.next = nextRandomNumber;
return this;
}
function createRandomNumber(Min, Max){
var rand = new RandomNumberGenerator();
return Math.round((Max-Min) * rand.next() + Min);
}
//Thus I can now do:
var letters = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'];
var numbers = ['1','2','3','4','5','6','7','8','9','10'];
var colors = ['red','orange','yellow','green','blue','indigo','violet'];
var first = letters[createRandomNumber(0, letters.length)];
var second = numbers[createRandomNumber(0, numbers.length)];
var third = colors[createRandomNumber(0, colors.length)];
alert("Today's show was brought to you by the letter: " + first + ", the number " + second + ", and the color " + third + "!");
/*
If I could pass my own seed into the createRandomNumber(min, max, seed);
function then I could reproduce a random output later if desired.
*/
Следующий IIFE генерирует длинную последовательность воспроизводимых случайных 31-битных целых чисел. Он использует два 15-битных простых числа, чтобы избежать переполнения целых чисел JS.
let random = (function () {
let a = 1, b = 1;
return {
nextInt: function () {
a = (a * 67307) & 0xffff;
b = (b * 67427) & 0xffff;
return a ^ (b << 15);
},
reset(seed) {
a = b = seed | 0;
}
};
})();
Следующий код показывает, как его использовать...
random.reset(2); // Reset to start of sequence
// Log sequence of random numbers
for (let i = 0; i < 100; i++)
console.log(random.nextInt());
Спасибо, @aaaaaaaaaaaaa (принятый ответ)
Мне очень нужно было хорошее небиблиотечное решение (проще встроить)
Итак... я сделал этот класс для хранения семени и разрешил Unity-esque "Next"... но сохранил первоначальные результаты на основе Integer
class randS {
constructor(seed=null) {
if(seed!=null) {
this.seed = seed;
} else {
this.seed = Date.now()%4645455524863;
}
this.next = this.SeedRandom(this.seed);
this.last = 0;
}
Init(seed=this.seed) {
if (seed = this.seed) {
this.next = this.SeedRandom(this.seed);
} else {
this.seed=seed;
this.next = this.SeedRandom(this.seed);
}
}
SeedRandom(state1,state2){
var mod1=4294967087;
var mod2=4294965887;
var mul1=65539;
var mul2=65537;
if(typeof state1!="number"){
state1=+new Date();
}
if(typeof state2!="number"){
state2=state1;
}
state1=state1%(mod1-1)+1;
state2=state2%(mod2-1)+1;
function random(limit){
state1=(state1*mul1)%mod1;
state2=(state2*mul2)%mod2;
if(state1<limit && state2<limit && state1<mod1%limit && state2<mod2%limit){
this.last = random;
return random(limit);
}
this.last = (state1+state2)%limit;
return (state1+state2)%limit;
}
this.last = random;
return random;
}
}
А затем проверил это с помощью этих ... кажется, хорошо работает со случайным (но запрашиваемым) начальным значением (а-ля Minecraft) и даже сохраняет последнее возвращаемое значение (при необходимости)
var rng = new randS(9005646549);
console.log(rng.next(20)+' '+rng.next(20)+' '+rng.next(20)+' '+rng.next(20)+' '+rng.next(20)+' '+rng.next(20)+' '+rng.next(20));
console.log(rng.next(20) + ' ' + rng.next(20) + ' ' + rng.last);
который должен выводить (для всех)
6 7 8 14 1 12 6
9 1 1
РЕДАКТИРОВАТЬ: я заставил init() работать, если вам когда-либо нужно было повторно заполнить или проверить значения (это было необходимо и в моем контексте)
Хорошо, вот решение, на котором я остановился.
Сначала вы создаете начальное значение с помощью функции "newseed()". Затем вы передаете начальное значение в функцию "srandom()". Наконец, функция "srandom()" возвращает псевдослучайное значение между 0 и 1.
Ключевой бит в том, что начальное значение хранится в массиве. Если бы это было просто целое число или число с плавающей запятой, значение будет перезаписываться при каждом вызове функции, поскольку значения целых чисел, чисел с плавающей запятой, строк и т. Д. Хранятся непосредственно в стеке, а не только в указателях, как в случае массивов и другие объекты. Таким образом, ценность семени остается неизменной.
Наконец, можно определить функцию "srandom()" так, чтобы это был метод объекта "Math", но я оставлю это на ваше усмотрение, чтобы разобраться.;)
Удачи!
JavaScript:
// Global variables used for the seeded random functions, below.
var seedobja = 1103515245
var seedobjc = 12345
var seedobjm = 4294967295 //0x100000000
// Creates a new seed for seeded functions such as srandom().
function newseed(seednum)
{
return [seednum]
}
// Works like Math.random(), except you provide your own seed as the first argument.
function srandom(seedobj)
{
seedobj[0] = (seedobj[0] * seedobja + seedobjc) % seedobjm
return seedobj[0] / (seedobjm - 1)
}
// Store some test values in variables.
var my_seed_value = newseed(230951)
var my_random_value_1 = srandom(my_seed_value)
var my_random_value_2 = srandom(my_seed_value)
var my_random_value_3 = srandom(my_seed_value)
// Print the values to console. Replace "WScript.Echo()" with "alert()" if inside a Web browser.
WScript.Echo(my_random_value_1)
WScript.Echo(my_random_value_2)
WScript.Echo(my_random_value_3)
Lua 4 (моя личная целевая среда):
-- Global variables used for the seeded random functions, below.
seedobja = 1103515.245
seedobjc = 12345
seedobjm = 4294967.295 --0x100000000
-- Creates a new seed for seeded functions such as srandom().
function newseed(seednum)
return {seednum}
end
-- Works like random(), except you provide your own seed as the first argument.
function srandom(seedobj)
seedobj[1] = mod(seedobj[1] * seedobja + seedobjc, seedobjm)
return seedobj[1] / (seedobjm - 1)
end
-- Store some test values in variables.
my_seed_value = newseed(230951)
my_random_value_1 = srandom(my_seed_value)
my_random_value_2 = srandom(my_seed_value)
my_random_value_3 = srandom(my_seed_value)
-- Print the values to console.
print(my_random_value_1)
print(my_random_value_2)
print(my_random_value_3)