Comments 38
Может быть, это закладка NSA в Chrome :)
Скорее всего это какое то древнее наследие :)
P.S. в DC++, например, тоже свой генератор используется, но тут всё гораздо суровее и интереснее:
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 благодарю
P.S. flexoid благодарю
Тут вполне я думаю применима Бритва Хэнлона:
Никогда не приписывайте злому умыслу то, что вполне можно объяснить глупостью
В следующих версиях починили
http://v8project.blogspot.ru/2015/12/theres-mathrandom-and-then-theres.html
http://v8project.blogspot.ru/2015/12/theres-mathrandom-and-then-theres.html
О том, что Math.random() в V8 ужасающего качества, было известно всегда. Начиная с версии 4.9.41.0 используется другой алгоритм. Описание и наглядное сравнение: v8project.blogspot.ru/2015/12/theres-mathrandom-and-then-theres.html
Так эта самая переведенная статья и послужила причиной смены алгоритма:
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+.
Вероятность «раз в миллион лет» говорит о том, что за миллион лет событие скорее всего произойдет хотя бы один раз. Но она ничего не говорит о том, в какой день это событие произойдет. Оно может произойти в любой день, например, в первый.
пример эксплуатации старого Math.random().
jonasnick.github.io/blog/2015/07/08/exploiting-csgojackpots-weak-rng
jonasnick.github.io/blog/2015/07/08/exploiting-csgojackpots-weak-rng
А почему бы не добавлять какой-то идентификатор объекта, который сделал запрос к идентификатору запроса? Тогда бы и коллизий не было.
По сути получается то же самое, что и увеличение длины генерируемой последовательности.
Уменьшается вероятность коллизии. Так вам нужно уникальный в рамках всей системы, а так в рамках одного пользователя.
То есть по сути попытаться компенсировать низкое качество генератора добавлением лишнего источника энтропии. Точно так же можно добавлять системное время, например. Решить проблему это может помочь, колиизий станет меньше, но сам по себе генератор всё равно останется низкокачественным, к чему, кажется, и должна привлечь внимание статья.
str += ALPHABET.substring(rand, rand+1);
Вы просили не критиковать код, но всё же я не могу удержаться от вопроса: почему не ALPHABET.charAt(rand)? Или не ALPHABET[rand]? Есть какие-то неизвестные мне нюансы?
>… пространство имеет размер 64^22 ≈ 2^132
Каким образом левая часть выражения приближенно равна правой части?
Каким образом левая часть выражения приближенно равна правой части?
Вот ещё недавно попалось на глаза: www.pcg-random.org
Очень быстрый, требует мало памяти, статистические тесты проходит «на отлично».
Также он обладает «k-размерной эквидистрибутивностью». Вот, например, с его помощью «генерируют» тексты Шекспира: www.pcg-random.org/party-tricks.html
Очень быстрый, требует мало памяти, статистические тесты проходит «на отлично».
Также он обладает «k-размерной эквидистрибутивностью». Вот, например, с его помощью «генерируют» тексты Шекспира: www.pcg-random.org/party-tricks.html
Я вот думаю, ну почему так долго развиваются инструкции процессора в сторону векторных вычислений (MMX, SSE, AVX, AVX2 и т.д.), но до сих пор не сделали инструкцию в один цикл, дающую абсолютно случайное число на аппаратном уровне? Или, например, регистр со случайным числом, которое меняется каждый цикл процессора. Хорошие псевдослучайные числа стоят очень дорого, если применять обычный конвейер вычислений, при этом запрос на быстрые случайные числа велик.
Потому что потом никто не будет уверен в надежности этих случайных чисел. Например пост Theodore Ts'o.
К слову, такой шум генерирует Фаерфокс №43:
И делает он это, к удивлению, на порядок быстрее Хромиума №47
шум
И делает он это, к удивлению, на порядок быстрее Хромиума №47
У меня немного вопросы, еще к самому способу решения задачи:
1) Почему нельзя взять например nanoTime — счетчик и прибавить 8 бит какого-то случайного rpng. Вероятность совпадения будет гораздо ниже, потому что вероятность «дней рождения» велика за счет общности задачи. С другой же стороны всегда можно сказать, что пиковая пропускная способность в 1 секунду не превышает некоторого числа.
2) Почему использовалась функция Math.random() — double, а не Math.random(255) возвращающая один бит (не уверен на счет JS).
1) Почему нельзя взять например nanoTime — счетчик и прибавить 8 бит какого-то случайного rpng. Вероятность совпадения будет гораздо ниже, потому что вероятность «дней рождения» велика за счет общности задачи. С другой же стороны всегда можно сказать, что пиковая пропускная способность в 1 секунду не превышает некоторого числа.
2) Почему использовалась функция Math.random() — double, а не Math.random(255) возвращающая один бит (не уверен на счет JS).
К примеру, при каждом запросе API генерируются случайные идентификаторы запроса. Они помещаются в подзапросы в заголовках, логируются и используются для сравнения и корреляции всех происходящих событий во всех сервисах, в качестве результата одного-единственного запроса. Ничего сложного в генерировании случайных идентификаторов нет. Требование одно:
Вероятность двукратного генерирования одного и того же идентификатора — возникновения коллизии — должна быть крайне мала.
А почему не GUID / UUID?
Sign up to leave a comment.
Проблемы при использовании Math.random()