Создайте генератор случайных чисел, который пройдет тесты Diehard

50

В то время как здесь есть много вопросов о кодовом гольфе, связанных со случайностью, я еще не видел ни одного, который бы на самом деле требовал создания алгоритмического генератора псевдослучайных чисел. Есть один, который просит вас генерировать поток битов, но тесты случайности, предоставленные на этом, были не очень строгими, и это не код-гольф.

В написанной вами программе будет одна вызываемая функция, которая будет возвращать случайное целое число от 0 до 4294967295. Эта функция не должна вызывать какие-либо библиотеки или другие функции, которые также не были написаны как часть программы, особенно вызовы / dev / random или встроенная в язык библиотека rand (). Более конкретно, вы ограничены базовыми операторами языка, на котором вы работаете, такими как арифметика, доступ к массиву и операторы условного управления потоком.

Оценка вашей программы рассчитывается следующим образом:

Score = C / R

Где C - длина кода в символах, а R - количество тестов Diehard, которые ваш генератор прошел (если ваш генератор случайных чисел не прошел хотя бы один тест Diehard, его оценка равна бесконечности, и он дисквалифицирован). Ваш генератор проходит тест Diehard, если генерируемый им файл предоставляет диапазон значений P, которые, по-видимому, распределены равномерно по интервалу [0, 1).

Чтобы вычислить R, используйте генератор случайных чисел с его начальным значением по умолчанию для создания файла двоичных данных размером 16 МБ. Каждый вызов функции возвращает четыре байта; если ваша функция слишком медленная, чтобы возвращать байты, это приведет к компромиссу в достижении низкой оценки из-за сложности тестирования. Затем проведите его через тесты Diehard и проверьте предоставленные значения P. (Не пытайтесь реализовать их самостоятельно; используйте представленные здесь )

Самая низкая оценка выигрывает, конечно.

Джо З.
источник
Разрешен ли код, который требует подключения к Интернету? (не собираюсь обращаться к какой-либо случайной функции онлайн, но, возможно, пинг или значения вызова API)
elssar
«Эта функция не должна вызывать какие-либо библиотеки или другие функции, которые также не были написаны как часть программы». Это включает в себя функции подключения к Интернету. Ваше поколение должно быть чисто алгоритмическим.
Джо З.
Пакет diehard ожидает входные файлы размером 10-11 МБ.
Прим
Ссылка на тесты, кажется, не работает, вот возможная альтернатива.
2012 rcampion
Как это сделать для моего ответа мозгового штурма (см. Ниже)? Я думаю, что код слишком медленный, чтобы быть практичным
Кристофер

Ответы:

6

Mathematica, 32/15 = 2,133

x=3;Mod[x=Mod[x^2,28!-67],2^32]&

Простая реализация BBS .

Двоичный файл, созданный с помощью:

f = %; (* assigns anonymous function declared in the previous expression to f *)
Export["random.bin", Array[f, 2^22], "UnsignedInteger32"];

Сводка результатов:

 1. BIRTHDAY SPACINGS TEST           .684805
 2. OVERLAPPING 5-PERMUTATION TEST   .757608/.455899
 3. BINARY RANK TEST                 .369264/.634256
 4. BINARY RANK TEST                 .838396
 5. THE BITSTREAM TEST                (no summary p-value)    
 6. OPSO, OQSO and DNA                (no summary p-value)
 7. COUNT-THE-1's TEST               .649382/.831761
 8. COUNT-THE-1's TEST                (no summary p-value)
 9. PARKING LOT TEST                 .266079
10. MINIMUM DISTANCE TEST            .493300
11. 3DSPHERES TEST                   .492809
12. SQEEZE                           .701241
13. OVERLAPPING SUMS test            .274531
14. RUNS test                        .074944/.396186/.825835/.742302
15. CRAPS TEST                       .403090/.403088/.277389

Полный random.binздесь.

Полный файл журнала здесь.

2012rcampion
источник
28!-67несколько запредельно. Есть ли меньшее значение, которое поместится в 64-разрядное целое число?
Прим
@primo Как и Python, целые числа Mathematica по умолчанию имеют произвольную точность, поэтому проблем не возникает.
2012 rcampion
Я думал специально о переносимости в C.
Примо
@primo gmplib.org
2012rcampion
21

Perl 28/13 ≈ 2,15

sub r{$s^=~($s^=$s/7215)<<8}

файл журнала здесь

Perl 29/13 ≈ 2,23

sub r{$s^=~($s^=$s<<8)/60757}

файл журнала здесь

Это что-то вроде вариации Xorshift , использующего деление с плавающей точкой вместо правого смещения. Они оба проходят 13 из 15 тестов, не пройдя только тесты 6 и 7.

Я точно не знаю , как долго этот цикл, а потому , что следующий код не прекращается в любой короткий промежуток времени, то, скорее всего , полный 2 32 :

$start = r();
$i++ while $start != r();
print $i;

Perl 39/10 = 3,9

$s=$^T;sub r{~($s=$s*$s%4294969373)||r}

Примечание: если вы ищете PRNG от Blum-Blum-Shub-esque, решение Кейта Рэндалла намного лучше, чем любой из них.

Как и в моем исходном решении ниже, это также реализация Blum Blum Shub, с одним существенным отличием. Я использую модуль, немного больший чем 2 32 ( M = 50971 • 84263 ), и всякий раз, когда встречается значение, которое не является действительным 32-битным целым числом (то есть больше 2 32 ), оно возвращает следующее значение в вращение вместо. По сути, эти значения сокращаются, оставляя остальную часть вращения без помех, что приводит к почти равномерному распределению.

Кажется, это помогло. Помимо прохождения тех же 9 тестов, что и раньше, теперь он также убедительно проходит тест на минимальное расстояние. Пример файла журнала можно найти здесь .


Perl 33/9 ≈ 3,67 (неверно?)

 $s=$^T;sub r{$s=$s*$s%4294951589}

Примечание: это решение может считаться недействительным, поскольку самый верхний 0,00037% диапазона никогда не будет наблюдаться.

Быстрая и грязная реализация Blum Blum Shub . Я требую следующие результаты:

 1. passed - Birthday Spacings
 2. FAILED - Overlapping Permutations
 3. passed - Ranks of 31x31 and 32x32 Matrices
 4. passed - Ranks of 6x8 Matrices
 5. FAILED - Monkey Tests on 20-bit Words
 6. FAILED - Monkey Tests OPSO, OQSO, DNA
 7. FAILED - Count the 1s in a Stream of Bytes
 8. passed - Count the 1s for Specific Bytes
 9. passed - Parking Lot Test
10. FAILED - Minimum Distance Test
11. passed - Random Spheres Test
12. FAILED - The Squeeze Test
13. passed - Overlapping Sums Test
14. passed - Runs Test
15. passed - The Craps Test

Пример файла журнала можно найти здесь , не стесняйтесь оспаривать любой из результатов. Файл для diehard может быть сгенерирован следующим образом:

print pack('N', r()) for 1..4194304

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


подробности

В общем, Blum Blum Shub - ужасный PRNG, но его производительность можно улучшить, выбрав хороший модуль. M Я выбрал это 7027 • 611207 . Оба из этих простых факторов, p и q , имеют модульный остаток 3 (mod 4) , и gcd (φ (p-1), φ (q-1)) = 2 , что является настолько низким, насколько это возможно.

Хотя это единственные критерии, перечисленные на вики-странице, этого недостаточно. Почти все по модулю, которые я попробовал, провалились в каждом тесте. Но есть горстка, которая пройдет некоторые тесты, и тот, который я выбрал, кажется исключительно хорошим по любой причине.

В заключение отметим, что тест 5 сам по себе является довольно хорошим показателем того, насколько хорош PRNG. Если он почти не пройдет 5-й тест, он остальным провалится.


БОНУС: Perl 62/14 ≈ 4.43

$t=$^T;sub r{$t|=(($s=$s/2|$t%2<<31)^($t/=2))<<31for 1..37;$t}

Просто для гиков: это 32-битная версия PRNG, использованная в оригинальном Tetris для NES. Удивительно, но он проходит 14 из 15 тестов!

 1. passed - Birthday Spacings
 2. passed - Overlapping Permutations
 3. passed - Ranks of 31x31 and 32x32 Matrices
 4. passed - Ranks for 6x8 Matrices
 5. passed - Monkey Tests on 20-bit Words
 6. passed - Monkey Tests OPSO, OQSO, DNA
 7. FAILED - Count the 1s in a Stream of Bytes
 8. passed - Count the 1s for Specific Bytes
 9. passed - Parking Lot Test
10. passed - Minimum Distance Test
11. passed - Random Spheres Test
12. passed - The Squeeze Test
13. passed - Overlapping Sums Test
14. passed - Runs Test
15. passed - The Craps Test

Пример файла журнала можно раньше здесь .

По общему признанию, 1..37бит не является точной транскрипцией. В оригинальной версии процедура энтропии обновляется 60 раз в секунду, а затем запрашивается через случайные интервалы, в значительной степени зависящие от пользовательского ввода. Для тех, кто хочет разобрать ROM, процедура энтропии начинается с 0xAB47.

Псевдокод в стиле Python:

carry = entropy_1 & 1
entropy_1 >>= 1
entropy_2 = (entropy_2 >> 1) | (carry << 31)
carry = (entropy_1 & 1) ^ (entropy_2 & 1)
entropy_1 |= carry << 31
Примо
источник
Да, я заметил, что ваш алгоритм «не прошел» тест битового потока, но на самом деле имел несколько значений ниже 0,999999. Тем не менее, ваши тесты кажутся точными.
Джо З.
Однако есть одна проблема, заключающаяся в том, что числа от 4294951589 до 4294967295 не имеют шансов встретиться (хотя я полагаю, что это одна из причин, по которой она провалила некоторые из тестов Diehard).
Джо З.
1
@JoeZeng да, это проблема. Это наиболее очевидно в тесте 5: в первом прогоне пропущено 151 тыс. Слов, а в остальных - только 143 тыс. Пропущенных слов. Одним из решений было бы выбрать модуль, немного больший, чем 2 ^ 32, и позволить значениям, которые слишком велики, чтобы обернуться до нуля, но я не смог найти тот, который работает хорошо. Если я это сделаю, я буду обновлять пост.
Прим
7

Python, 46/15 = 3,0666

v=3
def R():global v;v=v**3%(2**32-5);return v

Использует модульное возведение в степень для генерации случайности. 2 ** 32-5 - наибольшее простое число меньше 2 ^ 32. (То же самое касается невозможности запустить тест № 2.)

Кит Рэндалл
источник
Не могли бы вы вставить файл журнала?
Прим
Войдите сюда: codepad.org/ZWhoGe0t
Кит Рэндалл,
1
Глупая винда. Он конвертировал все вхождения \rи \nв \r\n, что явно искажает результаты. Исправление - написать файл напрямую, используя f = open('file.bin', 'wb')и f.write.
Прим
Этот новый балл подрывает предыдущий балл, так что теперь это принятый ответ.
Джо З.
Этот новый счет был подрезан еще раз, поэтому я изменил принятый ответ.
Джо З.
4

Рубин, 32/15 = 2,1333

Это решение Кейта Рэндалла, реализованное в Ruby.

$v=3;def R;$v=$v**3%(2**32-5)end
YenTheFirst
источник
@JoeZ Это, похоже, новый самый низкий ответ, связанный с новым ответом Mathematica.
Riking
3

C # 144/15 = 9,6

uint a=15,b=26,y;uint q(int n){y=(a*1414549U+876619U)^(b*889453U+344753U);b=a;a=y>>12;return(a%256)<<n;}uint r(){return q(24)|q(16)|q(8)|q(0);}

Это прошло все испытания.

С не слишком большим количеством символов он проходит TestU01.

Результат: http://codepad.org/iny6usjV

    uint a = 15;
    uint b = 26;

    byte prng8()
    {
        uint y = ((a * 1414549U + 876619U) ^ (b * 889453U + 344753U)) >> 12;
        b = a;
        a = y;
        return (byte)y;
    }

    uint prng32()
    {
        return ((uint)prng8() << 24) | ((uint)prng8() << 16) | ((uint)prng8() << 8) | (uint)prng8();
    }
Андрей П.
источник
2

C # - 103/14 = 7,36

double j=999;uint N(){uint i=0,n=0;for(;i++<4;n=n*256+(uint)j%256)for(j/=277;j<100000;j*=j);return n;}

Результаты

Пройдено все, кроме теста №6.
См. Результаты на http://codepad.org/k1NSoyQW

объяснение

C # просто не может конкурировать с Ruby и Python за краткость, как обычно, но мне понравилось пробовать. Конечно, есть и другие значения, которые будут работать так же хорошо (т. Е. Начальное значение для j = 999 и делитель = 277). Я выбрал их после коротких экспериментов.

С оберткой для создания файлов

class R
{
    public static void Main(string[] args)
    {
        var r = new R();
        using (var f = new System.IO.FileStream(".\\out.bin", System.IO.FileMode.Create, System.IO.FileAccess.Write, System.IO.FileShare.Read))
        using (var b = new System.IO.BinaryWriter(f))
        {
            for (long i = 0; i < 12 * 1024 * 1024; i += 4)
            {

                b.Write(r.N());
            }
        }
    }

    double j = 999;

    uint N()
    {
        uint i = 0, n = 0;
        for (; i++ < 4; n = n * 256 + (uint)j % 256)
            for (j /= 277; j < 100000; j *= j) ;
        return n;
    }

}
Ричард II
источник
1

Python, 41/15 = 2,73333

v=0
def R():global v;v=hash(`v`);return v

Любопытное обмана , используя встроенный в хэш - функции, но это не встроенная, так больше обмана , чем при использовании других встроенных команд, как len. С другой стороны, мне больно платить за global v;заявление ...

Проходит все тесты Diehard (у меня была проблема с тестом № 2, это SEGV на моей машине с OSX. На мой взгляд, я предполагаю, что это пройдет).

Вот драйвер для создания файла 16 МБ:

import sys
for i in xrange(1<<22):
  r=R()
  sys.stdout.write('%c%c%c%c'%(r&255, r>>8&255, r>>16&255, r>>24&255))
Кит Рэндалл
источник
«Эта функция не должна вызывать какие-либо библиотеки или другие функции, которые также не были написаны как часть программы, особенно вызовы / dev / random или встроенной библиотеки языка rand ()». Извините, но это дисквалифицирует вашу запись.
Джо З.
Чтобы было ясно, "Лен" также будет дисквалифицировать вашу заявку.
Джо З.
Где вы проводите черту? Является +ли встроенная функция и, следовательно, дисквалифицирована?
Кит Рэндалл
6
Но во многих языках операторы и функции идентичны. Смотрите +и __add__в python, или перегрузку операторов в c ++. Я знаю, что я немного расщепляю волосы, поэтому рассмотрим этот пример. В Python я могу создать карту , как это: {'a':5}? Вы, вероятно, скажете «да», но затем подумайте, что под прикрытием вам hash('a')звонят, когда вы это делаете.
Кит Рэндалл
2
Полагаю, я бы нарисовал линию, когда вам нужно синтаксически ссылаться на функцию таким образом. Если вы можете найти взлом в Python, который позволит вам напрямую получить доступ к адресу карты без синтаксической ссылки на функцию «хэш», я мог бы принять это.
Джо З.
1

С, 38/15 = 2,533

long long x;f(){return(x+=x*x+9)>>32;}

Я не смог заставить тесты Diehard работать на моей машине, но он проходит набор PractRand для вывода до 8 ГБ, поэтому я предполагаю, что он пройдет их все.

user1502040
источник
0

Brain-Flak , 344 / (ожидается)

<>((()()){})<> push the amount of iterations to do for the PRNG
(((((((((((((((((((((((((((((((((((()()()){}()){})){}{}){()()()()({}[()])}{})){}{})){}{})()){}{})()){}{})){}{})){}{}){}())){}{})){}{})()){}{})()){}{})){}{})){}{})()){}{})()){}{}) push M (one of the values for the Blum Blum Shub PRNG
((((((((((((()()()){}){}){})){}{}){()({}[()])}{}){}())){}{})()){}{}) push s see above
<>{({}[()])<>starts the loop
(({({})({}[()])}{}) squares the current number
(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]({}))mods by M
<>}{}<>loop ends

Попробуйте онлайн!

Это работает нормально, но ссылки на несгибаемые тесты не работают :( так что пока мы не получим новые, у меня нет окончательного результата

При этом используется PRNG Blum Blum Shub, поэтому он должен пройти большинство случаев. Используемые числа достаточно велики, в 16 МБ тестовых случаев шаблоны не появятся

Кристофер
источник
если это
Кристофер
1
Я считаю 344. Теорема: ни одна программа Brain-flak не имеет гольф-поля с нечетным числом байтов.
user202729
0

Objective-C, 40/1 = 40

Довольно умный подход, использующий, .hashчтобы немного обмануть здесь, но мне это нравится

for(int v=9;v=@(v).hash;printf("%i",v));
Альберт Реншоу
источник