Как стать автором
Обновить

Комментарии 38

Может быть, это закладка NSA в Chrome :)
Скорее всего это какое то древнее наследие :)

P.S. в DC++, например, тоже свой генератор используется, но тут всё гораздо суровее и интереснее:
Спойлер
/* Below is a high-speed random number generator with much
   better granularity than the CRT one in msvc...(no, I didn't
   write it...see copyright) */
/* Copyright (C) 1997 Makoto Matsumoto and Takuji Nishimura.
   Any feedback is very welcome. For any question, comments,
   see http://www.math.keio.ac.jp/matumoto/emt.html or email
   matumoto@math.keio.ac.jp */
/* Period parameters */

// TODO óáðàòü ìàãè÷åñêèå ÷èñëà!!!
#define N 624
#define M 397
#define MATRIX_A 0x9908b0df   /* constant vector a */
#define UPPER_MASK 0x80000000 /* most significant w-r bits */
#define LOWER_MASK 0x7fffffff /* least significant r bits */

/* Tempering parameters */
#define TEMPERING_MASK_B 0x9d2c5680
#define TEMPERING_MASK_C 0xefc60000
#define TEMPERING_SHIFT_U(y)  (y >> 11)
#define TEMPERING_SHIFT_S(y)  (y << 7)
#define TEMPERING_SHIFT_T(y)  (y << 15)
#define TEMPERING_SHIFT_L(y)  (y >> 18)

static std::vector<unsigned long> g_mt(N + 1); /* the array for the state vector  */
static int g_mti = N + 1; /* mti==N+1 means mt[N] is not initialized */

/* initializing the array with a NONZERO seed */
static void sgenrand(unsigned long seed)
{
	/* setting initial seeds to mt[N] using         */
	/* the generator Line 25 of Table 1 in          */
	/* [KNUTH 1981, The Art of Computer Programming */
	/*    Vol. 2 (2nd Ed.), pp102]                  */
	g_mt[0] = seed & ULONG_MAX;
	for (g_mti = 1; g_mti < N; g_mti++)
		g_mt[g_mti] = (69069 * g_mt[g_mti - 1]) & ULONG_MAX;
}

uint32_t Util::rand()
{
	unsigned long y;
	/* mag01[x] = x * MATRIX_A  for x=0,1 */
	
	if (g_mti >= N)   /* generate N words at one time */
	{
		static unsigned long mag01[2] = {0x0, MATRIX_A};
		int kk;
		
		if (g_mti == N + 1) /* if sgenrand() has not been called, */
			sgenrand(4357); /* a default initial seed is used   */
			
		for (kk = 0; kk < N - M; kk++)
		{
			y = (g_mt[kk] & UPPER_MASK) | (g_mt[kk + 1] & LOWER_MASK);
			g_mt[kk] = g_mt[kk + M] ^(y >> 1) ^ mag01[y & 0x1];
		}
		for (; kk < N - 1; kk++)
		{
			y = (g_mt[kk] & UPPER_MASK) | (g_mt[kk + 1] & LOWER_MASK);
			g_mt[kk] = g_mt[kk + (M - N)] ^(y >> 1) ^ mag01[y & 0x1];
		}
		y = (g_mt[N - 1] & UPPER_MASK) | (g_mt[0] & LOWER_MASK);
		g_mt[N - 1] = g_mt[M - 1] ^(y >> 1) ^ mag01[y & 0x1];
		
		g_mti = 0;
	}
	
	y = g_mt[g_mti++];
	y ^= TEMPERING_SHIFT_U(y);
	y ^= TEMPERING_SHIFT_S(y) & TEMPERING_MASK_B;
	y ^= TEMPERING_SHIFT_T(y) & TEMPERING_MASK_C;
	y ^= TEMPERING_SHIFT_L(y);
	
	return y;
}


Чудесный TODO:
// TODO óáðàòü ìàãè÷åñêèå ÷èñëà!!!
)
// TODO убрать магические числа!!!
Дооо ) на самом деле там имелось ввиду, что необходимо обосновать использование именно таких значений N и M ибо они влияют на вероятность появления коллизий.

P.S. flexoid благодарю
Тут вполне я думаю применима Бритва Хэнлона:
Никогда не приписывайте злому умыслу то, что вполне можно объяснить глупостью
Так эта самая переведенная статья и послужила причиной смены алгоритма:
This has been pointed out to us, and having understood the problem and after some research, we decided to reimplement Math.random based on an algorithm called xorshift128+.
И было бы неплохо в конкретно этом переводе, опубликованном уже после внедрения нового алгоритма, об этом упомянуть.
Вероятность «раз в миллион лет» говорит о том, что за миллион лет событие скорее всего произойдет хотя бы один раз. Но она ничего не говорит о том, в какой день это событие произойдет. Оно может произойти в любой день, например, в первый.
Событие может и вообще не произойти, а может и 20000 раз произойти за «миллион лет». Случайность штука интересная.
А почему бы не добавлять какой-то идентификатор объекта, который сделал запрос к идентификатору запроса? Тогда бы и коллизий не было.
По сути получается то же самое, что и увеличение длины генерируемой последовательности.
Уменьшается вероятность коллизии. Так вам нужно уникальный в рамках всей системы, а так в рамках одного пользователя.
То есть по сути попытаться компенсировать низкое качество генератора добавлением лишнего источника энтропии. Точно так же можно добавлять системное время, например. Решить проблему это может помочь, колиизий станет меньше, но сам по себе генератор всё равно останется низкокачественным, к чему, кажется, и должна привлечь внимание статья.
str += ALPHABET.substring(rand, rand+1);

Вы просили не критиковать код, но всё же я не могу удержаться от вопроса: почему не ALPHABET.charAt(rand)? Или не ALPHABET[rand]? Есть какие-то неизвестные мне нюансы?
Это слегка перевод
Упс, не заметил. Пардон.
Если интересна разница, то она есть:

var str = '12345';

str.charAt(10) == '';
str[10] == undefined;
Меня интересовало, какие «фишки» есть у substring(rand, rand+1) по сравнению с приведёнными мной вариантами. С квадратными скобками я немного погорячился, но разве charAt(rand) не полный аналог?
>… пространство имеет размер 64^22 ≈ 2^132
Каким образом левая часть выражения приближенно равна правой части?
Спасибо!
Это перевод, в оригинале «64²² or ~2¹³²»
Имелось в виду, они просто равны.
Вот ещё недавно попалось на глаза: www.pcg-random.org
Очень быстрый, требует мало памяти, статистические тесты проходит «на отлично».
Также он обладает «k-размерной эквидистрибутивностью». Вот, например, с его помощью «генерируют» тексты Шекспира: www.pcg-random.org/party-tricks.html
Также он обладает «k-размерной эквидистрибутивностью».
DIEHARD, кажется проверял для k ~ 600, так что неполучение гиперплоскостей при генерации — вполне обычное требование для prng.
Я вот думаю, ну почему так долго развиваются инструкции процессора в сторону векторных вычислений (MMX, SSE, AVX, AVX2 и т.д.), но до сих пор не сделали инструкцию в один цикл, дающую абсолютно случайное число на аппаратном уровне? Или, например, регистр со случайным числом, которое меняется каждый цикл процессора. Хорошие псевдослучайные числа стоят очень дорого, если применять обычный конвейер вычислений, при этом запрос на быстрые случайные числа велик.
Это то, что нужно! В таком случае было бы хорошо, если бы стандартные библиотеки перестроились на использование именно этой инструкции. Для задач, в которых не важна конкретная реализация алгоритма случайных чисел.
Плохая идея. Как дополнительный источник энтропии RdRand/PadLock/прочие HwRng можно использовать, но как единственный — нет.
Потому что потом никто не будет уверен в надежности этих случайных чисел. Например пост Theodore Ts'o.
А никто и не будет использовать генераторы псевдослучайных чисел из стандартных библиотек для криптографических задач.
НЛО прилетело и опубликовало эту надпись здесь
У меня немного вопросы, еще к самому способу решения задачи:
1) Почему нельзя взять например nanoTime — счетчик и прибавить 8 бит какого-то случайного rpng. Вероятность совпадения будет гораздо ниже, потому что вероятность «дней рождения» велика за счет общности задачи. С другой же стороны всегда можно сказать, что пиковая пропускная способность в 1 секунду не превышает некоторого числа.

2) Почему использовалась функция Math.random() — double, а не Math.random(255) возвращающая один бит (не уверен на счет JS).
К примеру, при каждом запросе API генерируются случайные идентификаторы запроса. Они помещаются в подзапросы в заголовках, логируются и используются для сравнения и корреляции всех происходящих событий во всех сервисах, в качестве результата одного-единственного запроса. Ничего сложного в генерировании случайных идентификаторов нет. Требование одно:

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


А почему не GUID / UUID?
Они по такому же принципу создаются
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.