Случайные числа и детерминистичная симуляция



    Совсем недавно, помогая коллеге в решении вопроса о неповторяемости работы ряда тестов, я в очередной раз натолкнулся на задачу симуляции устройства, генерирующего последовательности случайных чисел. В этой статье я расскажу о том, какие сложности были обнаружены, какой подход к их разрешению был выбран, и как я проверял, что новое решение лучше предыдущего. Сразу отмечу, что вопрос создания и верификации случайных последовательностей очень тонкий, и почти никакое решение не может считаться в нём окончательным. Буду признателен за комментарии и исправления.

    Вначале я кратко расскажу о предметной области аппаратных и псевдослучайных генераторов, об их характеристиках и требованиях к ним. Затем перейду к своему частному случаю — области программной симуляции вычислительных систем, и к конкретной задаче, которую нужно было решить.


    Иногда самый надёжный способ получить случайное число — взять его из справочника. Источник изображения: www.flickr.com/photos/nothingpersonal/337684768


    Введение: ГСЧ, ГПСЧ, RNG, DRNG


    Задача получения «случайной» последовательности чисел с помощью компьютера на удивление сложна. Интуитивно это можно обосновать тем фактом, что философия цифровых систем и архитектура современных ЭВМ направлены на достижение абсолютной точности, на изничтожение даже намёка на неопределённость в результате работы. Хранимые и передаваемые данные заверяются контрольными суммами, электрические цепи дублируются. Случайность изгнана, так как же её вернуть? И зачем?

    На самом деле, многие практические задачи требуют для своего решения реализовывать алгоритмы, использующие достаточно длинные случайные последовательности. Имитационное моделирование, генетические алгоритмы, численное интегрирование и решение систем линейных уравнений (методы Монте Карло), компьютерные игры и современная криптография. В каждом случае имеется собственное понимание того, какие последовательности уже можно считать случайными, а какие ещё нет. Различаются и используемые генераторы случайных чисел (ГСЧ, англ. RNG — random number generator).

    Казалось бы, природа предоставляет достаточно хаоса, куда тут человечеству за ним угнаться. Достаточно сделать оцифровывающее устройство для некоторого процесса (тепловые шумы, вспышки на солнце, кидание монетки), подключить его к компьютеру, и дело в шляпе.

    Однако практическое применение «чистых» аппаратных ГСЧ ограничено следующими факторами. Во-первых, скорость генерации чисел может быть недостаточно высокой, а приложения могут потреблять их так быстро, что даже современные интерфейсы типа PCI-Express будут загружены под завязку. Во-вторых, статистические характеристики такой последовательности могут быть не самые лучшие — распределение не то или меняется со временем, ширина чисел меньше требуемой, тенденция выдавать нули чаще, чем единицы (англ. bias) и т.п. В-третьих, цена подобного качественного устройства может быть достаточно высокой, что будет ограничивать его область применения областями с самыми жёсткими требованиями к случайности. Наконец, энергопотребление и размеры ГСЧ могут быть неподходящими для мобильных устройств.

    По этой причине часто используется комбинированный подход: первоначальное значение (seed) берётся из случайного источника, и вся последовательность генерируется из него с помощью неслучайной функции:

    (a1, s1) = f(seed)
    (a2, s2) = f(s1)
    (a3, s3) = f(s2)


    Здесь a1, a2,… — выходная псевдослучайная последовательность, а s1, s2,… — внутреннее состояние генератора. Результирующая конструкция называется генератор псевдослучайных чисел (ГПСЧ, англ. PRNG — pseudo-random number generator).
    Качество последовательности, очевидно, зависит от выбора функции f(), а иногда также от значения seed (например, f(x) = a*x mod m выдаёт последовательность нулей при seed = 0). История знает множество случаев использования плохих функций. Дам лишь два примера.
    1. ai+1 = 65539 * ai mod 231, seed — нечётный. Это классическая RANDU, широко использовавшаяся в UNIX в 1960-1970 годах. Проваливает даже простейшие тесты (о них будет сказано далее).
    2. Дональд Кнут в [5] описывает свою попытку в 1959 году сделать супер-ГПСЧ с помощью алгоритма из 13 шагов, один запутаннее другого. На практике оказалось, что последовательность немедленно сошлась к одному числу, которое затем преобразовывалось само в себя.


    Источники случайности в вычислительных платформах


    Вернёмся к аппаратным ГСЧ. В архитектуре IBM PC они присутствуют уже некоторое время и предлагаются как в компонентах Intel, так и других вендоров. Несколько примеров ниже.
    • В конце 20 века аппаратный ГСЧ был встроен в Intel 82802 Firmware Hub [3]. Работал он исправно, однако к нему были претензии по энергопотреблению, скорости генерации, а также по совместимости со всё время уменьшающимися размерами техпроцесса.
    • По этой причине был спроектирован новый ГСЧ, находящийся прямо в ядре ЦПУ. Он был представлен в процессорах микроархитектуры Ivy Bridge в качестве инструкции RDRAND [4]. В дальнейшем он также начал использоваться для инструкции RDSEED. О различиях между этими двумя командами написано здесь. Пара статей на Хабре про RDRAND: habrahabr.ru/post/128666 habrahabr.ru/post/145188
    • В современных платформах собственный ГСЧ находится в модуле TPM (англ. trusted platform module) и может быть использован как для нужд криптографии, так и для других целей. Подробнее о скорости работы и качестве выдаваемых чисел рассказывается в [8].
    • Компания VIA также предлагает аппаратный ГСЧ в составе своих процессоров VIA C3 [6].


    Общие требования к ГСЧ


    Так как я работаю над программными моделями аппаратуры, возникает задача моделирования присутствующих в них ГСЧ. Модель, т.е. в конечном счёте реализующая генератор функция на Си, должна удовлетворять требованиям, выдвигаемым на физические ГСЧ. Если же это не так, то отличия должны быть поняты и объяснены особенностями процесса моделирования — нельзя оставлять такой вопрос на самотёк. В конце концов, всякая модель — это лишь приближение реальности, важно, чтобы оно было достаточно хорошо для практических нужд, а его ограничения были осознаны.
    • Случайность. Самый расплывчатый критерий, и к нему мы ещё вернёмся. Но уже понятно, что стоит с умом подойти к выбору функции и проверить её тестами.
    • Распределение. Будем считать, что требуемое распределение — равномерное U[0; 2N -1], где N=64. Современные генераторы выдают именно столько бит.
    • Большой период. Всякая последовательность от ГПСЧ зацикливается из-за ограниченности числа различных внутренних состояний. Это не будет заметно, если её период будет очень велик. Наша цель — величина порядка 263 или выше.
    • Скорость генерации. RDRAND может выдавать десятки миллионов чисел в секунду. Симуляция обычно работает значительно медленнее реального железа. Не будем гнаться за большой скоростью генерации, однако и слишком сложные функции по возможности выбирать не стоит — не хочется создавать bottleneck.
    • Неугадываемость. Этот аспект важен для криптографических применений. Наша модель не используется для таких нужд. Кроме того, криптографически стойкие программные ГПСЧ обычно очень медленны.

    Есть ещё одно требование, специфичное для симуляции.
    • Повторяемость. Состояние симуляции в любой момент её работы может быть сохранено на диск в точку сохранения (англ. checkpoint), перенесено на другую машину и там восстановлено. Кроме того, необходимо поддержать возможность обращения течения времени, и ход всех процессов, в том числе выходящих из ГПСЧ чисел, должен повторяться. Это означает, что симуляция должна хранить значение внутреннего состояния генератора.


    Проблемы с rand()


    Самый первый и вообще никуда не годящийся генератор выглядел примерно так:

    // init seed
    int seed = ...;
    srand(seed);
    
    uint64 bad_rand() {
    	return rand();
    }
    


    Здесь нет даже намёка на повторяемость — хотя seed явно задаётся в начале работы, и последовательность будет всегда одна и та же, при откате симуляции до предыдущего состояния она не будет повторяться, так как состояние генератора в процессе работы нам неподконтрольно. Кроме того, у bad_rand() есть и другие проблемы, аналогичные тем, что описаны далее. Мы не будем больше к нему возвращаться в дальнейшем.
    Затем код для генерации 64 битного случайного числа был переписан так:

    uint64 unix_rand(uint64 *state) {
    	srand(*state);
    	uint32 r1 = rand();
    	srand(r1);
    	uint32 r2 = rand();
    	*state = r2;
    	uint64 result = ((uint64)r2 << 32) | r1;
    	return result;
    }
    


    Поскольку стандартный rand() из Libc возвращает int, который в худшем случае имеет ширину 32 бита, использовались два последовательных вызова и комбинация их в одно 64-битное число. Так как rand() не возвращает значение своего внутреннего состояния, приходилось задавать его каждый раз с помощью srand().
    Этот подход всё ещё был плохим по ряду причин.
    1. Зависимость старшей половины бит от младшей. В качестве seed для старших 32 бит выступают младшие, т.е. части числа связаны функциональной зависимостью, которую можно обнаружить, т.е. показать неслучайность.
    2. RAND_MAX на моей системе был равен 231-1. Т.е. на самом деле rand() выдаёт только 31 бит! А в конечном числе меняются только 62 бита, 31-й и 63-й же всегда нули.
    3. Самый серьёзный недостаток — неопределённость функции rand(). Вообще нельзя сказать, будет ли RAND_MAX одинаковым на всех системах. Нельзя даже утверждать, что реализация rand() будет одинаковой на Windows и Linux, не будет зависеть от разрядности ОС, версии Libc, компилятора или чего-то ещё. Одна и та же симуляция, запущенная на разных хозяйских системах, будет выдавать разные результаты. Кошмар для отладки!


    Новое решение


    Наконец, мы привели код к следующему виду:

    const uint64 a1 = ...;
    const uint64 c1 = ...;
    const uint64 a2 = ...;
    const uint64 c2 = ...;
    
    uint64 two_lcg_rnd(uint64 *state1, uint64 *state2) {
    	uint64 r1 = a1 * *state1 + c1;	
    	uint64 r2 = a2 * *state2 + c2;
    	*state1 = r1;
    	*state2 = r2;
    	
    	uint64 result = (r2 & 0xffffffff00000000ull) | (r1 >> 32);
    	return result;
    }
    


    • Использованы два линейных конгруэнтных генератора (англ. LCG) вида f(x) = a*x + c mod 264. Сильные и слабые стороны этого типа LCG хорошо изучены, а вычисления в целых числах по модулю степени двойки выполняются быстро.
    • Константы a1, a2, c1, c2 выбраны так, чтобы периоды LCG были велики. Интересующиеся легко найдут их значения в Интернете.
    • Для того, чтобы генераторы были независимы, a1 != a2, c1 != c2, а в качестве внутреннего состояния используются две независимые переменные. Но эти предосторожности не гарантирует независимости; требуется эмпирическая проверка.
    • У каждого из возвращаемых LCG 64-битных чисел используются только старшие 32 бита. Младшие разряды LCG имеют значительно меньший период, поэтому они отброшены.


    Использование собственной функции для ГПСЧ избавляет нас от самой трудноуловимой ошибки — недетерминизма симуляции. Но насколько случайным является её выдача?

    Эмпирическая проверка


    Принцип эмпирического анализа Г(П)СЧ — вычисление для входной последовательности статистики, определяющей истинность некоторой гипотезы о характере её поведения. Например, можно проверять равнораспределённость пар (троек, четвёрок...) соседних чисел, отсутствие периодов монотонного роста и спада и т.п. Для истинного ГСЧ ни одна из подобных гипотез не должна быть подтверждена с достаточной уверенностью. Чем больше различных статистик проходит конкретный ГПСЧ, тем выше его качество. Интересующимся сравнением качества ГСЧ из разных популярных программ я рекомендую прочитать [1].

    Существует несколько пакетов для исследования ГСЧ, в том числе Dieharder [2] и NIST SP 800-22 [7]. Я использовал пакет TestU01 [1]. В нём предопределены три группы тестов, различающихся по числу проверяемых в них статистик: SmallCrush, Crush и BigCrush. Каждый из входящих в них подтестов выдаёт число p-value из полуинтервала [0,1). Для прохождения подтеста оно должно быть одновременно далеко как нуля, так и от единицы.

    Я использовал средний по размеру набор Crush, который во всех моих экспериментах исполнялся от получаса до двух часов. Программы я запускал на такой системе:
    ЦПУ: Intel Core(TM) i5-4300U CPU @ 1.90GHz
    uname -a: CYGWIN_NT-6.3 hostname 1.7.31(0.272/5/3) 2014-07-25 11:26 x86_64 Cygwin

    Для второго генератора, основанного на rand(), результаты плачевны: 139 тестов из 144 закончились неудачно:
    Скрытый текст
    ========= Summary results of Crush =========
    
     Version:          TestU01 1.2.3
     Generator:        unix_rand
     Number of statistics:  144
     Total CPU time:   00:46:32.40
     The following tests gave p-values outside [0.001, 0.9990]:
     (eps  means a value < 1.0e-300):
     (eps1 means a value < 1.0e-15):
    
           Test                          p-value
     ----------------------------------------------
      1  SerialOver, t = 2                eps
      2  SerialOver, t = 4                eps
      3  CollisionOver, t = 2             eps
      4  CollisionOver, t = 2             eps
      5  CollisionOver, t = 4             eps
      6  CollisionOver, t = 4             eps
      7  CollisionOver, t = 8             eps
      8  CollisionOver, t = 8             eps
      9  CollisionOver, t = 20            eps
     10  CollisionOver, t = 20            eps
     11  BirthdaySpacings, t = 2          eps
     12  BirthdaySpacings, t = 3          eps
     13  BirthdaySpacings, t = 4          eps
     14  BirthdaySpacings, t = 7          eps
     15  BirthdaySpacings, t = 7          eps
     16  BirthdaySpacings, t = 8          eps
     17  BirthdaySpacings, t = 8          eps
     18  ClosePairs NP, t = 2          3.2e-157
     18  ClosePairs mNP, t = 2         3.2e-157
     18  ClosePairs mNP1, t = 2           eps
     18  ClosePairs mNP2, t = 2           eps
     18  ClosePairs NJumps, t = 2         eps
     19  ClosePairs NP, t = 3          3.2e-157
     19  ClosePairs mNP, t = 3         3.2e-157
     19  ClosePairs mNP1, t = 3           eps
     19  ClosePairs mNP2, t = 3           eps
     19  ClosePairs NJumps, t = 3         eps
     19  ClosePairs mNP2S, t = 3          eps
     20  ClosePairs NP, t = 7           1.8e-79
     20  ClosePairs mNP, t = 7          1.8e-79
     20  ClosePairs mNP1, t = 7           eps
     20  ClosePairs mNP2, t = 7           eps
     20  ClosePairs NJumps, t = 7         eps
     20  ClosePairs mNP2S, t = 7          eps
     21  ClosePairsBitMatch, t = 2      6.9e-65
     22  ClosePairsBitMatch, t = 4     7.5e-143
     23  SimpPoker, d = 16                eps
     24  SimpPoker, d = 16                eps
     25  SimpPoker, d = 64                eps
     26  SimpPoker, d = 64                eps
     27  CouponCollector, d = 4           eps
     28  CouponCollector, d = 4           eps
     29  CouponCollector, d = 16          eps
     30  CouponCollector, d = 16          eps
     31  Gap, r = 0                       eps
     32  Gap, r = 27                      eps
     33  Gap, r = 0                       eps
     34  Gap, r = 22                      eps
     35  Run of U01, r = 0                eps
     36  Run of U01, r = 15               eps
     37  Permutation, r = 0               eps
     38  Permutation, r = 15              eps
     39  CollisionPermut, r = 0           eps
     40  CollisionPermut, r = 15          eps
     41  MaxOft, t = 5                    eps
     41  MaxOft AD, t = 5              3.2e-157
     42  MaxOft, t = 10                   eps
     42  MaxOft AD, t = 10              1.8e-79
     43  MaxOft, t = 20                   eps
     43  MaxOft AD, t = 20              1 - eps1
     44  MaxOft, t = 30                   eps
     44  MaxOft AD, t = 30              1 - eps1
     45  SampleProd, t = 10             1 - eps1
     46  SampleProd, t = 30             1 - eps1
     47  SampleMean                       eps
     48  SampleCorr                     1 - eps1
     49  AppearanceSpacings, r = 0      1 - eps1
     50  AppearanceSpacings, r = 20     1 - eps1
     51  WeightDistrib, r = 0             eps
     52  WeightDistrib, r = 8             eps
     53  WeightDistrib, r = 16            eps
     54  WeightDistrib, r = 24            eps
     55  SumCollector                     eps
     56  MatrixRank, 60 x 60              eps
     57  MatrixRank, 60 x 60              eps
     58  MatrixRank, 300 x 300            eps
     60  MatrixRank, 1200 x 1200          eps
     62  Savir2                           eps
     63  GCD, r = 0                       eps
     64  GCD, r = 10                      eps
     65  RandomWalk1 H (L = 90)           eps
     65  RandomWalk1 M (L = 90)           eps
     65  RandomWalk1 J (L = 90)           eps
     65  RandomWalk1 R (L = 90)           eps
     65  RandomWalk1 C (L = 90)           eps
     66  RandomWalk1 H (L = 90)           eps
     66  RandomWalk1 M (L = 90)           eps
     66  RandomWalk1 J (L = 90)           eps
     66  RandomWalk1 R (L = 90)           eps
     66  RandomWalk1 C (L = 90)           eps
     67  RandomWalk1 H (L = 1000)         eps
     67  RandomWalk1 M (L = 1000)         eps
     67  RandomWalk1 J (L = 1000)         eps
     67  RandomWalk1 R (L = 1000)         eps
     67  RandomWalk1 C (L = 1000)         eps
     68  RandomWalk1 H (L = 1000)         eps
     68  RandomWalk1 M (L = 1000)         eps
     68  RandomWalk1 J (L = 1000)         eps
     68  RandomWalk1 R (L = 1000)         eps
     68  RandomWalk1 C (L = 1000)         eps
     69  RandomWalk1 H (L = 10000)        eps
     69  RandomWalk1 M (L = 10000)        eps
     69  RandomWalk1 J (L = 10000)        eps
     69  RandomWalk1 R (L = 10000)        eps
     69  RandomWalk1 C (L = 10000)        eps
     70  RandomWalk1 H (L = 10000)        eps
     70  RandomWalk1 M (L = 10000)        eps
     70  RandomWalk1 J (L = 10000)        eps
     70  RandomWalk1 R (L = 10000)        eps
     70  RandomWalk1 C (L = 10000)        eps
     71  LinearComp, r = 0              1 - eps1
     71  LinearComp, r = 0              1 - eps1
     73  LempelZiv                      1 - eps1
     74  Fourier3, r = 0                  eps
     75  Fourier3, r = 20                 eps
     76  LongestHeadRun, r = 0            eps
     76  LongestHeadRun, r = 0          1 - eps1
     77  LongestHeadRun, r = 20           eps
     77  LongestHeadRun, r = 20         1 - eps1
     78  PeriodsInStrings, r = 0          eps
     79  PeriodsInStrings, r = 15         eps
     80  HammingWeight2, r = 0            eps
     82  HammingCorr, L = 30              eps
     83  HammingCorr, L = 300             eps
     84  HammingCorr, L = 1200            eps
     85  HammingIndep, L = 30             eps
     86  HammingIndep, L = 30             eps
     87  HammingIndep, L = 300            eps
     88  HammingIndep, L = 300            eps
     89  HammingIndep, L = 1200           eps
     90  HammingIndep, L = 1200           eps
     91  Run of bits, r = 0               eps
     91  Run of bits, r = 0               eps
     92  Run of bits, r = 20              eps
     92  Run of bits, r = 20            1 - eps1
     93  AutoCor, d = 1                 1 - eps1
     94  AutoCor, d = 1                   eps
     95  AutoCor, d = 30                1 - eps1
     96  AutoCor, d = 10                1 - 5.2e-10
     ----------------------------------------------
     All other tests were passed
    




    Для нового генератора, основанного на двух независимых LCG, картина лучше:
    Скрытый текст
    ========= Summary results of Crush =========
    
     Version:          TestU01 1.2.3
     Generator:        two_lcg_rnd
     Number of statistics:  144
     Total CPU time:   00:46:13.21
     The following tests gave p-values outside [0.001, 0.9990]:
     (eps  means a value < 1.0e-300):
     (eps1 means a value < 1.0e-15):
    
           Test                          p-value
     ----------------------------------------------
      1  SerialOver, t = 2                eps
      2  SerialOver, t = 4                eps
      8  CollisionOver, t = 8           1 - 8.0e-13
     13  BirthdaySpacings, t = 4        1.2e-82
     15  BirthdaySpacings, t = 7          eps
     16  BirthdaySpacings, t = 8          eps
     17  BirthdaySpacings, t = 8          eps
     ----------------------------------------------
     All other tests were passed
    



    Провалились лишь 7 тестов из 144. Неплохо, хотя для криптографических нужд я этот ГПСЧ не посоветую использовать. Отмечу, что отдельные «половинки» этого генератора также не прошли те же самые типы подтестов.

    Из любопытства я прогнал TestU01 (самый длинный BigCrush) на последовательности, выдаваемой инструкцией RDRAND на том же ЦПУ:
    Скрытый текст
    ========= Summary results of BigCrush =========
    
     Version:          TestU01 1.2.3
     Generator:        rdrand
     Number of statistics:  160
     Total CPU time:   15:58:06.92
     The following tests gave p-values outside [0.001, 0.9990]:
     (eps  means a value < 1.0e-300):
     (eps1 means a value < 1.0e-15):
    
           Test                          p-value
     ----------------------------------------------
      1  SerialOver, r = 0                eps
      2  SerialOver, r = 22               eps
     76  RandomWalk1 J (L=1000, r=0)     1.7e-4
     ----------------------------------------------
     All other tests were passed
    


    Поиск ответа на вопрос, почему даже на «истинно» случайном генераторе TestU01 выдаёт несколько неудач, оставим для будущих исследователей, хотя у меня есть гипотеза на этот счёт.

    Заключение


    Тема генерации псевдослучайных чисел и проверки их на случайность невероятно захватывающая. Всем заинтересовавшимся я рекомендую почитать, если вы ещё этого не сделали, соответствующую главу из второго тома Д. Кнута [5]. Вопрос использования ГСЧ для нужд симуляции, и не только вычислительных систем, разбирается в [9].

    Литература


    1. Pierre L'Ecuyer and Richard Simard. 2007. TestU01: A C library for empirical testing of random number generators. ACM Trans. Math. Softw. 33, 4, Article 22 (August 2007). DOI=10.1145/1268776.1268777 simul.iro.umontreal.ca/testu01/tu01.html
    2. Robert G. Brown, Dirk Eddelbuettel, David Bauer. Dieharder: A Random Number Test Suite Version 3.31.1 www.phy.duke.edu/~rgb/General/dieharder.php
    3. Intel Corporation. Intel 810 Chipset Design Guide, June 1999. download.intel.com/design/chipsets/designex/29065701.pdf
    4. Intel Digital Random Number Generator (DRNG) Software Implementation Guide — software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide
    5. Дональд Кнут. Искусство программирования. Том 2. Получисленные алгоритмы. Третье издание — 2011 — Вильямс. ISBN 978-5-8459-0081-4,
    6. Cryptography Research, Inc. Evaluation summary: VIA C3 Nehemiah random number generator — 2003 — www.cryptography.com/public/pdf/VIA_rngsum.pdf
    7. National Institute of Standards and Technology. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications — 2010 csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf
    8. Alin Suciu, Tudor Carean. Benchmarking the True Random Number Generator of TPM Chips. arxiv.org/ftp/arxiv/papers/1008/1008.2223.pdf
    9. Handbook of Simulation. Principles, Methodology, Advances, Applications, and Practice / под ред. J. Banks. — John Wiley & Sons, Inc., 1998. — ISBN 0-471-13403-1. — URL: books.google.com/books?id=dMZ1Zj3TBgAC




    Intel
    177,00
    Компания
    Поделиться публикацией

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

      +1
      Проблема с RAND_MAX — мелочи :-) Как «радует» разнообразием используемых алгоритмов для получения «случайных» чисел всеми любимый PHP — отдельная песня! Там начиная от самых тупых LCRNG через Type3 до MersenneTwister. А над ними еще 2 функции стоят. И все это по разному работает на разных платформах (Win, Linux, BSD) и с разными патчами/настройками.
        +1
        Интересно =)
        расскажите подробнее, пожалуйста
          0
          Можно написать простенький PHP-скрипт, который сделает srand(0) и выведет 10 результатов rand(). В идеале, каждый запуск должен выводить одни и те же числа, в статье написано почему. В реальности, на некоторых системах будет так, а на некоторых будут разные результаты. Это — игнорирование srand и зависит от патчей безопасности.
          Относительно систем с повторяющимися результатами: скрипт выдаст разные числа на Linux, BSD и Windows. В никсах обычно используется Glibc-Type3 генератор, в винде — LCRNG из Glibc, да еще и RAND_MAX маленький. В BSD тоже Type3, но свой.
          Это мы рассматривали rand(void), но есть еще rand(min, max), который использует результаты rand(). А еще есть array_rand (если не путаю имя), тоже из rand() берущий данные.
          Особняком стоит MersenneTwister (функции mt_*), но там я еще не разбирался. Вроде, при патчах он заменяет Type3 и LCRNG.
        +4
        Интересная статья, будем надеяться на продолжение. Интересно, что за гипотеза относительно провалившихся тестов TestU01
          0
          Спасибо! Продолжение про ГПСЧ пока не планирую, но от меня будут другие статьи. А ещё мои коллеги черкнули мне, что я забыл про RNG из состава Intel MKL, каюсь, да. Но, с другой стороны, кто лучше напишет про MKL, как не сами его авторы, так что сам жду ответного поста от них.

          Ответ про гипотезу чуть ниже.
          +2
          Изобретать своё конечно полезно, но гораздо проще взять любой современный хэш\алгоритм шифрования и использовать его как сидированный ГПСЧ с гарантированной рендомностью. Или Fortuna если совсем паранойя объяла
            0
            Было бы неплохо помимо минусов прочитать какую нибудь аргументацию
              –2
              Начните с себя и аргументируйте чем предложенное вами лучше.
                0
                Например, чем не устроил LFSR? Использовать порождающий полином 64-ой степени, и на выходе будет получаться относительно качественная генерируемая последовательность при простом коде генератора…
                –1
                Проблема в сидировании.
                  0
                  Точнее, в определении качества сида.

                  Я вот столкнулся на практике, программируя замену window.crypto.getRandomValues(…) для устаревших или запроприетаренных браузеров.

                  Так вот в браузерах (да и вообще много где) нет надежных источников энтропии, кроме пользовательского ввода. И тот — не вполне надежен, есть нюянсы короче.

                  Плодами моих усилий стал небольшой, но полезный скриптик
                    0
                    Хотя, чего я вам рассказываю, судя по вашему профилю, вы и так в курсе )
                      0
                      Проблема в сидировании.

                      Мсье намекает на существование алгоритмов, которые не надо сидировать?)

                      Я так понимаю, для задач «опытов» можно обойтись обычными getTickCount или подобным. Сид всегда гарантированно разный, а тесты всегда будут пройдены (рассматриваем случай использования сида как, например, ключа для шифрования быстрого поточного алгоритма вроде RC4. Он хоть уже и не особо стойкий, но ни чуть не медленней предложенного тут варианта).

                      Ну а для криптографии да, тут другой подход нужен. Собирать энтропию это искусство )
                  +2
                  С того, что не надо изобретать велосипед, если есть существующие DRBG или PRF, удовлетворяющие вашим требованиям.
                  –1
                  > Изобретать своё конечно полезно,
                  Ничего своего тут и не изобретено — алгоритмы давно известные, параметры для них подобраны не нами.

                  > но гораздо проще взять любой современный хэш\алгоритм шифрования
                  Он будет существенно сложнее, чем a*x + c (поправьте, если это не так). Это значит, что придётся или писать нечто более сложное самому, или завязываться на внешние библиотеки типа OpenSSL, внимательно сидеть и думать над их лицензией, над экспортным контролем и т.п.

                  > с гарантированной рендомностью
                  Ничто не гарантированно, как известно. Хочется знать ограничения выбранного решения, а не надеяться на авось.

                  > если совсем паранойя объяла
                  Тут дело не в том. Для нашей ситуации даже последовательность 1, 2,3, 4… подошла бы лучше, чем rand(), потому что она повторяема.

                  0
                  Помню эти таблицы случайных чисел по университету)) Использовали при изучении полного факторного эксперимента.
                    0
                    А Вы, случайно, название книги не помните, с такой табличкой? А то я только эту фотографию страницы нашёл. Хотелось бы для учебных целей и первоисточник узнать.
                      +1
                      «Основы современных алгоритмов»
                    +2
                    Мелькнула мысль, что если ГПСЧ выдает полностью состояние (допустим 32 бита), либо инъективную функцию от состояния, то его можно с большой вероятностью «отличить от рандома» простым общим статистическим тестом — у «правильного» рандома из примерно 2**17 выходов хотя бы два должны совпасть. У описанного ГПСЧ совпасть выходы так быстро не могут, т.к. тогда образуется период и его тоже легко вычислить.

                    Про криптографическую стойкость таких ГПСЧ говорить нет смысла, но это может быть проблемой и для различных экспериментов со «случайными» данными.
                      +1
                      По этой причине в настоящее время генераторы с размером состояния 32 бита (и периодом 2^32) уже неактуальны.

                      > у «правильного» рандома из примерно 2**17 выходов хотя бы два должны совпасть
                      Ваш анализ правильный (и подобный тест наверняка включён в TestU01), но нужно учесть объёмы памяти и времени, необходимый для его проведения, ведь надо хранить все уже сгенерированные числа и сравнивать новые поступающие с каждым из них. Для 32-битного генератора это будет порядка 2^17 * 4 = 0.5 Мбайт, а вот для 64-битного, по аналогии, это будут уже гигабайты. Ну и время будет расти экспоненциально.
                      0
                      хотя у меня есть гипотеза на этот счёт

                      Поделитесь пожалуйста? Мне например кажется, что подобные тесты в вакууме — лажа.
                        0
                        В этом плане наука статистика очень хорошо отражает суть позитивизма в естественнонаучном принципе познания — нельзя доказать гипотезу, но можно попытаться её опровергнуть.

                        В нашем случае можно попытаться огромным числом различных способов найти неслучайность в выходе ГПСЧ и потерпеть неудачу, при этом зная, что это — именно ГПСЧ. Этим мы не докажем случайность последовательности, но и не опровергнем её. Когда, например, изменятся инструменты (новые алгоритмы, больше памяти, быстрее компы), доказательство неслучайности, может быть, и будет найдено, вот тогда можно будет сказать «ага!» и выкинуть конкретный алгоритм ГПСЧ на свалку.

                        Очень многие проблемы возникают как раз из-за непонимания этого основного принципа как статистики, так и строгой науки в целом.

                        Моя гипотеза, почему некоторые тесты из TestU01 стабильно не проходят, связана с особенностями эксперимента и организации кода. А именно, оригинальный фреймворк заточен (или это я только это в нём нашёл) на тестирование 32-битных (а точнее, int) генераторов. Хотя отдельный класс для тестирования 64-битных целых (а точнее long int) там есть, похоже, что он не очень отлажен — у меня падал с ошибками, которые я хоть и исправил, но не отладил до конца (если будут силы, свяжусь с автором и попрошу совета). Однако есть работающий класс для тестирования 64-битных чисел с плавающей запятой, к коим я и привёл выводы своих генераторов (к отрезку от 0.0 до 1.0). В double-ах всего 53 бита мантиссы, т.е. 11 бит исходного числа мы теряем. Вот здесь и лежит слабое место, и возможно, что тесты это «почувствовали».

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое