[PostgreSQL, SQL, Алгоритмы, Математика] Случайности не случайны
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Можно ли достоверно предсказать будущее хоть на немного вперед? Иногда - вполне, надо только много везения... или немного знаний.Сегодня пронаблюдаем сеанс черной магии с последующим разоблачением, или «Я угадаю твой рандом с 3 строк!»:Немного магии
tst=# SELECT r random, magic(r) random_next FROM random() r;
random | random_next
--------------------+--------------------
0.3921143477755571 | 0.6377947747296489
tst=# SELECT r random, magic(r) random_next FROM random() r;
random | random_next
--------------------+--------------------
0.6377947747296489 | 0.5727554063674667
tst=# SELECT r random, magic(r) random_next FROM random() r;
random | random_next
--------------------+--------------------
0.5727554063674667 | 0.4979625995285346
Ты угадал следующий random оба раза?..Что же там "под капотом"?
CREATE OR REPLACE FUNCTION magic(r double precision) RETURNS double precision AS $$
SELECT
(
(
(r & x'FFFFFFFFFFFF'::bigint) * (mul & x'000000000FFF'::bigint)
+ (r & x'000FFFFFFFFF'::bigint) * (mul & x'000000FFF000'::bigint)
+ (r & x'000000FFFFFF'::bigint) * (mul & x'000FFF000000'::bigint)
+ (r & x'000000000FFF'::bigint) * (mul & x'FFF000000000'::bigint)
+ add
) & x'FFFFFFFFFFFF'::bigint
)::double precision / x'1000000000000'::bigint
FROM
(VALUES(
(r * x'1000000000000'::bigint)::bigint
, x'0005deece66d'::bigint
, x'000b'::bigint
)) T(r, mul, add)
$$ LANGUAGE sql;
Но как и почему это работает? Обратимся к документации:
Функция random() использует простой линейный конгруэнтный алгоритм. Она работает быстро, но не подходит для криптографических приложений; более безопасная альтернатива имеется в модуле pgcrypto. Если воспользоваться функцией setseed() и вызывать её с одним и тем же аргументом, результаты последующих вызовов random() в текущем сеансе будут повторяться.
Собственно, мы только что убедились, что если "случайности не случайны", то для криптографии тут места точно нет. Но что это за "простой линейный алгоритм"?
We Need To Go DeeperИдем на официальное github-зеркало PostgreSQL и находим определение setseed в float.c:
/*
* setseed - set seed for the random number generator
*/
Datum
setseed(PG_FUNCTION_ARGS)
{
float8 seed = PG_GETARG_FLOAT8(0);
uint64 iseed;
// ...
/* Use sign bit + 47 fractional bits to fill drandom_seed[] */
iseed = (int64) (seed * (float8) UINT64CONST(0x7FFFFFFFFFFF));
drandom_seed[0] = (unsigned short) iseed;
drandom_seed[1] = (unsigned short) (iseed >> 16);
drandom_seed[2] = (unsigned short) (iseed >> 32);
drandom_seed_set = true;
PG_RETURN_VOID();
}
Уже интересно - оказывается из float8-аргумента используется всего 48 бит.А теперь поднимемся чуть выше:
/*
* drandom - returns a random number
*/
Datum
drandom(PG_FUNCTION_ARGS)
{
float8 result;
/* Initialize random seed, if not done yet in this process */
if (unlikely(!drandom_seed_set))
{
/*
* If possible, initialize the seed using high-quality random bits.
* Should that fail for some reason, we fall back on a lower-quality
* seed based on current time and PID.
*/
if (!pg_strong_random(drandom_seed, sizeof(drandom_seed)))
{
TimestampTz now = GetCurrentTimestamp();
uint64 iseed;
/* Mix the PID with the most predictable bits of the timestamp */
iseed = (uint64) now ^ ((uint64) MyProcPid << 32);
drandom_seed[0] = (unsigned short) iseed;
drandom_seed[1] = (unsigned short) (iseed >> 16);
drandom_seed[2] = (unsigned short) (iseed >> 32);
}
drandom_seed_set = true;
}
/* pg_erand48 produces desired result range [0.0 - 1.0) */
result = pg_erand48(drandom_seed);
PG_RETURN_FLOAT8(result);
}
Название функции pg_erand48 подсказывает нам, что мы на верном пути - найдем ее в erand48.c:
/*
* Generate a random floating-point value using caller-supplied state.
* Values are uniformly distributed over the interval [0.0, 1.0).
*/
double
pg_erand48(unsigned short xseed[3])
{
uint64 x = _dorand48(xseed);
return ldexp((double) (x & UINT64CONST(0xFFFFFFFFFFFF)), -48);
}
Еще поднимемся на шаг за _dorand48:
/* These values are specified by POSIX */
#define RAND48_MULT UINT64CONST(0x0005deece66d)
#define RAND48_ADD UINT64CONST(0x000b)
/* POSIX specifies 0x330e's use in srand48, but the other bits are arbitrary */
#define RAND48_SEED_0 (0x330e)
#define RAND48_SEED_1 (0xabcd)
#define RAND48_SEED_2 (0x1234)
static unsigned short _rand48_seed[3] = {
RAND48_SEED_0,
RAND48_SEED_1,
RAND48_SEED_2
};
/*
* Advance the 48-bit value stored in xseed[] to the next "random" number.
*
* Also returns the value of that number --- without masking it to 48 bits.
* If caller uses the result, it must mask off the bits it wants.
*/
static uint64
_dorand48(unsigned short xseed[3])
{
/*
* We do the arithmetic in uint64; any type wider than 48 bits would work.
*/
uint64 in;
uint64 out;
in = (uint64) xseed[2] << 32 | (uint64) xseed[1] << 16 | (uint64) xseed[0];
out = in * RAND48_MULT + RAND48_ADD;
xseed[0] = out & 0xFFFF;
xseed[1] = (out >> 16) & 0xFFFF;
xseed[2] = (out >> 32) & 0xFFFF;
return out;
}
А вот и волшебные константы!Так что такое random()?Теперь у нас достаточно информации, чтобы понять, как вычисляется значение random()."Посев"При первом запросе random() в рамках PostgreSQL-процесса три 16-битных слова (48 бит) инициализируются значениями now-таймстампа "проксоренных" с PID процесса:
TimestampTz now = GetCurrentTimestamp();
uint64 iseed;
/* Mix the PID with the most predictable bits of the timestamp */
iseed = (uint64) now ^ ((uint64) MyProcPid << 32);
drandom_seed[0] = (unsigned short) iseed;
drandom_seed[1] = (unsigned short) (iseed >> 16);
drandom_seed[2] = (unsigned short) (iseed >> 32);
В последующем именно этот массив можно "засеять" своим значением с помощью setseed.Шаг вычисленийПри каждом следующем обращении этот массив рассматриваются как единое 48-битное число, которое умножается на RAND48_MULT (0x0005deece66d) и добавляется RAND48_ADD (0x000b).Результат сохраняется обратно и возвращается в виде double, состоящего из младших 48 бит.Эмулируем шаг вычислений на SQLФактически, надо просто взять последнее известное значение random(), умножить да сложить, но есть нюансы.double precision (double) <-> bigint (uint64)В C-исходниках одни и те же двоичные данные используются то как doublе,то как uint64 - в SQL мы так не можем. Зато можем призвать на помощь знание стандарта хранения чисел с плавающей точкой IEEE754 и математику.По стандарту, для хранения мантиссы используются младшие 52 бита. То есть наш 48-битный результат double precision прямо там и лежит, причем порядок обнулен - а, значит, достаточно умножить его на 2^48, и мы получим целочисленное bigint-представление:
SELECT (r::double precision * x'1000000000000'::bigint)::bigint;
Аналогично в обратную сторону:
SELECT r::double precision / x'1000000000000'::bigint;
Псевдодлинная арифметикаТеперь достаточно лишь умножить на 0x0005deece66d, и...
ОШИБКА: bigint вне диапазона
Вполне понятно - взяли 48-битное число, умножили на 35-битное - в 64 бита не влезли.Но нам же и не нужно даже 64 бита - всего лишь младшие 48! Умножим наши значения "столбиком" как 12-битные слова (поскольку 16-битные все-таки при умножении вылезают в знаковый бит) с ограничением разрядности:
12 12 12 12
48 bit = A B C D
* E F G H
--------------------
|AH BH CH DH = A B C D * 0 0 0 H
AG|BG CG DG = 0 B C D * 0 0 G 0
AF BF|CF DF = 0 0 C D * 0 F 0 0
AE BE CE|DE = 0 0 0 D * E 0 0 0
Осталось только это все сложить, добавить 0x000b, отбросить ненужные старшие биты и поделить, и - результат вы уже видели в самом начале статьи.
===========
Источник:
habr.com
===========
Похожие новости:
- [SQL, Microsoft SQL Server] Пожалуйста, прекратите использовать антипаттерн UPSERT (SQL Server) (перевод)
- [Oracle, PostgreSQL, Конференции, DevOps] 18 марта: DataBase Meetup Online
- [Программирование, C++, Алгоритмы] Ленивые операции над множествами в C++
- [Программирование, C++, Алгоритмы] Ленивые итераторы и диапазоны в C++
- [JavaScript, Анализ и проектирование систем, Алгоритмы, Обработка изображений, Машинное обучение] Мы создали Web приложение для определения лиц и масок для Google Chrome (перевод)
- [Разработка веб-сайтов, NoSQL, Node.JS] ArangoDB в реальном проекте
- [Программирование, .NET, Алгоритмы, C#, Математика] Compilation of math functions into Linq.Expression
- [SQL, Графический дизайн, IT-компании] Открытки в стиле SQL
- [Python, Алгоритмы, 1С] Tesseract vs таблицы. Распознавание документов
- [Программирование, .NET, Алгоритмы, C#, Математика] Компиляция математических выражений
Теги для поиска: #_postgresql, #_sql, #_algoritmy (Алгоритмы), #_matematika (Математика), #_postgresql, #_sql, #_random, #_double, #_blog_kompanii_tenzor (
Блог компании Тензор
), #_postgresql, #_sql, #_algoritmy (
Алгоритмы
), #_matematika (
Математика
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 20:51
Часовой пояс: UTC + 5
Автор | Сообщение |
---|---|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
Можно ли достоверно предсказать будущее хоть на немного вперед? Иногда - вполне, надо только много везения... или немного знаний.Сегодня пронаблюдаем сеанс черной магии с последующим разоблачением, или «Я угадаю твой рандом с 3 строк!»:Немного магии tst=# SELECT r random, magic(r) random_next FROM random() r;
random | random_next --------------------+-------------------- 0.3921143477755571 | 0.6377947747296489 tst=# SELECT r random, magic(r) random_next FROM random() r; random | random_next --------------------+-------------------- 0.6377947747296489 | 0.5727554063674667 tst=# SELECT r random, magic(r) random_next FROM random() r; random | random_next --------------------+-------------------- 0.5727554063674667 | 0.4979625995285346 Ты угадал следующий random оба раза?..Что же там "под капотом"? CREATE OR REPLACE FUNCTION magic(r double precision) RETURNS double precision AS $$
SELECT ( ( (r & x'FFFFFFFFFFFF'::bigint) * (mul & x'000000000FFF'::bigint) + (r & x'000FFFFFFFFF'::bigint) * (mul & x'000000FFF000'::bigint) + (r & x'000000FFFFFF'::bigint) * (mul & x'000FFF000000'::bigint) + (r & x'000000000FFF'::bigint) * (mul & x'FFF000000000'::bigint) + add ) & x'FFFFFFFFFFFF'::bigint )::double precision / x'1000000000000'::bigint FROM (VALUES( (r * x'1000000000000'::bigint)::bigint , x'0005deece66d'::bigint , x'000b'::bigint )) T(r, mul, add) $$ LANGUAGE sql; Функция random() использует простой линейный конгруэнтный алгоритм. Она работает быстро, но не подходит для криптографических приложений; более безопасная альтернатива имеется в модуле pgcrypto. Если воспользоваться функцией setseed() и вызывать её с одним и тем же аргументом, результаты последующих вызовов random() в текущем сеансе будут повторяться.
We Need To Go DeeperИдем на официальное github-зеркало PostgreSQL и находим определение setseed в float.c: /*
* setseed - set seed for the random number generator */ Datum setseed(PG_FUNCTION_ARGS) { float8 seed = PG_GETARG_FLOAT8(0); uint64 iseed; // ... /* Use sign bit + 47 fractional bits to fill drandom_seed[] */ iseed = (int64) (seed * (float8) UINT64CONST(0x7FFFFFFFFFFF)); drandom_seed[0] = (unsigned short) iseed; drandom_seed[1] = (unsigned short) (iseed >> 16); drandom_seed[2] = (unsigned short) (iseed >> 32); drandom_seed_set = true; PG_RETURN_VOID(); } /*
* drandom - returns a random number */ Datum drandom(PG_FUNCTION_ARGS) { float8 result; /* Initialize random seed, if not done yet in this process */ if (unlikely(!drandom_seed_set)) { /* * If possible, initialize the seed using high-quality random bits. * Should that fail for some reason, we fall back on a lower-quality * seed based on current time and PID. */ if (!pg_strong_random(drandom_seed, sizeof(drandom_seed))) { TimestampTz now = GetCurrentTimestamp(); uint64 iseed; /* Mix the PID with the most predictable bits of the timestamp */ iseed = (uint64) now ^ ((uint64) MyProcPid << 32); drandom_seed[0] = (unsigned short) iseed; drandom_seed[1] = (unsigned short) (iseed >> 16); drandom_seed[2] = (unsigned short) (iseed >> 32); } drandom_seed_set = true; } /* pg_erand48 produces desired result range [0.0 - 1.0) */ result = pg_erand48(drandom_seed); PG_RETURN_FLOAT8(result); } /*
* Generate a random floating-point value using caller-supplied state. * Values are uniformly distributed over the interval [0.0, 1.0). */ double pg_erand48(unsigned short xseed[3]) { uint64 x = _dorand48(xseed); return ldexp((double) (x & UINT64CONST(0xFFFFFFFFFFFF)), -48); } /* These values are specified by POSIX */
#define RAND48_MULT UINT64CONST(0x0005deece66d) #define RAND48_ADD UINT64CONST(0x000b) /* POSIX specifies 0x330e's use in srand48, but the other bits are arbitrary */ #define RAND48_SEED_0 (0x330e) #define RAND48_SEED_1 (0xabcd) #define RAND48_SEED_2 (0x1234) static unsigned short _rand48_seed[3] = { RAND48_SEED_0, RAND48_SEED_1, RAND48_SEED_2 }; /* * Advance the 48-bit value stored in xseed[] to the next "random" number. * * Also returns the value of that number --- without masking it to 48 bits. * If caller uses the result, it must mask off the bits it wants. */ static uint64 _dorand48(unsigned short xseed[3]) { /* * We do the arithmetic in uint64; any type wider than 48 bits would work. */ uint64 in; uint64 out; in = (uint64) xseed[2] << 32 | (uint64) xseed[1] << 16 | (uint64) xseed[0]; out = in * RAND48_MULT + RAND48_ADD; xseed[0] = out & 0xFFFF; xseed[1] = (out >> 16) & 0xFFFF; xseed[2] = (out >> 32) & 0xFFFF; return out; } TimestampTz now = GetCurrentTimestamp();
uint64 iseed; /* Mix the PID with the most predictable bits of the timestamp */ iseed = (uint64) now ^ ((uint64) MyProcPid << 32); drandom_seed[0] = (unsigned short) iseed; drandom_seed[1] = (unsigned short) (iseed >> 16); drandom_seed[2] = (unsigned short) (iseed >> 32); SELECT (r::double precision * x'1000000000000'::bigint)::bigint;
SELECT r::double precision / x'1000000000000'::bigint;
ОШИБКА: bigint вне диапазона
12 12 12 12
48 bit = A B C D * E F G H -------------------- |AH BH CH DH = A B C D * 0 0 0 H AG|BG CG DG = 0 B C D * 0 0 G 0 AF BF|CF DF = 0 0 C D * 0 F 0 0 AE BE CE|DE = 0 0 0 D * E 0 0 0 =========== Источник: habr.com =========== Похожие новости:
Блог компании Тензор ), #_postgresql, #_sql, #_algoritmy ( Алгоритмы ), #_matematika ( Математика ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 20:51
Часовой пояс: UTC + 5