Что может быть лучше для PCG.SE, чем реализовать PCG, лучший генератор случайных чисел ? Эта новая статья претендует на то, чтобы представить быстрый, трудно предсказуемый, небольшой, статистически оптимальный генератор случайных чисел.

Его минимальная реализация C составляет всего около девяти строк:

// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

^{(с сайта http://www.pcg-random.org/download.html )}

Вопрос: вы можете сделать лучше?

правила

Напишите программу или определите функцию, которая реализует PCG для 32-разрядных целых чисел без знака. Это довольно широко: вы можете распечатать бесконечную последовательность, определить pcg32_random_rфункцию и соответствующую структуру и т. Д.

Вы должны быть в состоянии заполнить ваш генератор случайных чисел эквивалентно следующей функции C:

// pcg32_srandom(initstate, initseq)
// pcg32_srandom_r(rng, initstate, initseq):
//     Seed the rng.  Specified in two parts, state initializer and a
//     sequence selection constant (a.k.a. stream id)

void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq)
{
    rng->state = 0U;
    rng->inc = (initseq << 1u) | 1u;
    pcg32_random_r(rng);
    rng->state += initstate;
    pcg32_random_r(rng);
}

^{(с: pcg_basic.c:37)}

Вызов генератора случайных чисел без его заполнения - это неопределенное поведение.

Чтобы легко проверить ваше представление, убедитесь, что при посеве с помощью initstate = 42и initseq = 52, вывод 2380307335:

$ tail -n 8 pcg.c 
int main()
{
    pcg32_random_t pcg;
    pcg32_srandom_r(&pcg, 42u, 52u);

    printf("%u\n", pcg32_random_r(&pcg));
    return 0;
}
$ gcc pcg.c
$ ./a.out 
2380307335

счет

Стандартный зачет. Измеряется в байтах. Самый низкий - лучший. В случае ничьей побеждает более раннее представление. Стандартные лазейкиПрименяются .

Пример решения

Компилируется под gcc -W -Wallчисто (версия 4.8.2).

Сравните вашу заявку с этим, чтобы убедиться, что вы получаете ту же последовательность.

#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq)
{
    rng->state = 0U;
    rng->inc = (initseq << 1u) | 1u;
    pcg32_random_r(rng);
    rng->state += initstate;
    pcg32_random_r(rng);
}

int main()
{
    size_t i;
    pcg32_random_t pcg;
    pcg32_srandom_r(&pcg, 42u, 52u);

    for (i = 0; i < 16; i++)
    {
        printf("%u\n", pcg32_random_r(&pcg));
    }
    return 0;
}

Последовательность:

2380307335
948027835
187788573
3952545547
2315139320
3279422313
2401519167
2248674523
3148099331
3383824018
2720691756
2668542805
2457340157
3945009091
1614694131
4292140870

CJam, 109 107 104 98 91 байт

При этом используются некоторые символы вне диапазона ASCII, но все они находятся в расширенном ASCII, поэтому я считаю каждый символ байтом (а не UTF-8).

{[2*0:A)|:B{AA"XQô-L-"256b*B1|+GG#%:A;__Im>^27m>_@59m>_@\m>@@~)31&m<|4G#%}:R~@A+:AR];}:S;

Это в основном точный порт кода C.

Функция seed - это блок, который хранится в S, а функция random - это блок, который хранится в R. Sожидает initstateи initseqв стеке и семян PRNG. Rничего не ожидает в стеке и оставляет на нем следующее случайное число.

Поскольку вызова Rперед вызовом Sявляется неопределенным поведением, я на самом деле определяющим R в S , так пока вы не используете блок семян,R это просто пустая строка и бесполезно.

stateХранится в переменной Aи incсохраняется вB .

Объяснение:

"The seed block S:";
[       "Remember start of an array. This is to clear the stack at the end.";
2*      "Multiply initseq by two, which is like a left-shift by one bit.";
0:A     "Store a 0 in A.";
)|:B    "Increment to get 1, bitwise or, store in B.";
{...}:R "Store this block in R. This is the random function.";
~       "Evaluate the block.";
@A+:A   "Pull up initstate, add to A and store in A.";
R       "Evaluate R again.";
];      "Wrap everything since [ in an array and discard it.";

"The random block R:";
AA            "Push two A's, one of them to remember oldstate.";
"XQô-L-"256b* "Push that string and interpret the character codes as base-256 digits.
               Then multiply A by this.";
B1|+          "Take bitwise or of 1 and inc, add to previous result.";
GG#%:A;       "Take modulo 16^16 (== 2^64). Store in A. Pop.";
__            "Make two copies of old state.";
Im>^          "Right-shift by 18, bitwise xor.";
27m>_         "Right-shift by 27. Duplicate.";
@59m>         "Pull up remaining oldstate. Right-shift by 59.";
_@\m>         "Duplicate, pull up xorshifted, swap order, right-shift.";
@@            "Pull up other pair of xorshifted and rot.";
~)            "Bitwise negation, increment. This is is like multiplying by -1.";
31&           "Bitwise and with 31. This is the reason I can actually use a negative value
               in the previous step.";
m<|           "Left-shift, bitwise or.";
4G#%          "Take modulo 4^16 (== 2^32).";

А вот эквивалент испытательного жгута в ОП:

42 52 S
{RN}16*

который печатает одинаковые цифры.

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

С, 195

Я подумал, что кто-то должен опубликовать более компактную реализацию C, даже если у нее нет шансов на победу. Третья строка содержит две функции: r()(эквивалентно pcg32_random_r()) и s()(эквивалентно pcg32_srandom_r()). Последняя строка - это main()функция, которая исключается из числа символов.

#define U unsigned
#define L long
U r(U L*g){U L o=*g;*g=o*0x5851F42D4C957F2D+(g[1]|1);U x=(o>>18^o)>>27;U t=o>>59;return x>>t|x<<(-t&31);}s(U L*g,U L i,U L q){*g++=0;*g--=q+q+1;r(g);*g+=i;r(g);}
main(){U i=16;U L g[2];s(g,42,52);for(;i;i--)printf("%u\n",r(g));}

Хотя компилятор будет жаловаться, это должно работать правильно на 64-битной машине. На 32-битной машине вам придется добавить еще 5 байт изменения #define L longв #define L long long( как в этом ideone демо ).

Юлия, 218 199 191 байт

Переименование типов данных и несколько других хитростей помогли мне сократить длину еще на 19 байтов. Главным образом, опуская два :: Int64 типа присваивания.

type R{T} s::T;c::T end
R(s,c)=new(s,c);u=uint32
a(t,q)=(r.s=0x0;r.c=2q|1;b(r);r.s+=t;b(r))
b(r)=(o=uint64(r.s);r.s=o*0x5851f42d4c957f2d+r.c;x=u((o>>>18$o)>>>27);p=u(o>>>59);x>>>p|(x<<-p&31))

Пояснения к именам (с соответствующими именами в негольфированной версии ниже):

# R     : function Rng
# a     : function pcg32srandomr
# b     : function pcg32randomr
# type R: type Rng
# r.s   : rng.state
# r.c   : rng.inc
# o     : oldstate
# x     : xorshifted
# t     : initstate
# q     : initseq
# p     : rot
# r     : rng
# u     : uint32

Инициализируйте seed с состоянием 42 и последовательностью 52. Из-за меньшей программы вам необходимо точно указывать тип данных во время инициализации (сохранено 14 байтов кода или около того). Вы можете опустить явное назначение типов в 64-битных системах:

r=R(42,52) #on 64-bit systems or r=R(42::Int64,52::Int64) on 32 bit systems
a(r.s,r.c)

Произведите первый набор случайных чисел:

b(r)

Результат:

julia> include("pcg32golfed.jl")
Checking sequence...
result round 1: 2380307335
target round 1: 2380307335   pass
result round 2: 948027835
target round 2: 948027835   pass
result round 3: 187788573
target round 3: 187788573   pass
             .
             .
             .

Я был действительно удивлен, что даже моя версия Джулии без заглядывания ниже так намного меньше (543 байта), чем пример решения в C (958 байтов).

Неуправляемая версия, 543 байта

type Rng{T}
    state::T
    inc::T
end

function Rng(state,inc)
    new(state,inc)
end

function pcg32srandomr(initstate::Int64,initseq::Int64)
    rng.state =uint32(0)
    rng.inc   =(initseq<<1|1)
    pcg32randomr(rng)
    rng.state+=initstate
    pcg32randomr(rng)
end

function pcg32randomr(rng)
    oldstate  =uint64(rng.state)
    rng.state =oldstate*uint64(6364136223846793005)+rng.inc
    xorshifted=uint32(((oldstate>>>18)$oldstate)>>>27)
    rot       =uint32(oldstate>>>59)
    (xorshifted>>>rot) | (xorshifted<<((-rot)&31))
end

Вы инициализируете начальное число (начальное состояние = 42, начальная последовательность = 52) с помощью:

rng=Rng(42,52)
pcg32srandomr(rng.state,rng.inc)

Затем вы можете создать случайные числа с:

pcg32randomr(rng)

Вот результат тестового скрипта:

julia> include("pcg32test.jl")
Test PCG
Initialize seed...
Checking sequence...
result round 1: 2380307335
target round 1: 2380307335   pass
result round 2: 948027835
target round 2: 948027835   pass
result round 3: 187788573
target round 3: 187788573   pass
             .
             .
             .
result round 14: 3945009091
target round 14: 3945009091   pass
result round 15: 1614694131
target round 15: 1614694131   pass
result round 16: 4292140870
target round 16: 4292140870   pass

Поскольку я ужасный программист, мне потребовался почти день, чтобы заставить его работать. Последний раз, когда я пытался написать что-то на C (на самом деле C ++), было почти 18 лет назад, но многие google-fu наконец помогли мне создать рабочую версию Julia. Я должен сказать, что я многому научился всего за несколько дней на Codegolf. Теперь я могу начать работать над версией Piet. Это будет большая работа, но я действительно, очень хочу (хороший) генератор случайных чисел для Пита;)