[PostgreSQL, SQL, Алгоритмы, Математика] Случайности не случайны

Автор Сообщение
news_bot ®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

Создавать темы news_bot ® написал(а)
15-Мар-2021 19:32


Можно ли достоверно предсказать будущее хоть на немного вперед? Иногда - вполне, надо только много везения... или немного знаний.Сегодня пронаблюдаем сеанс черной магии с последующим разоблачением, или «Я угадаю твой рандом с 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
===========

Похожие новости: Теги для поиска: #_postgresql, #_sql, #_algoritmy (Алгоритмы), #_matematika (Математика), #_postgresql, #_sql, #_random, #_double, #_blog_kompanii_tenzor (
Блог компании Тензор
)
, #_postgresql, #_sql, #_algoritmy (
Алгоритмы
)
, #_matematika (
Математика
)
Профиль  ЛС 
Показать сообщения:     

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 22-Ноя 15:25
Часовой пояс: UTC + 5