Комментарии 14
https://xkcd.com/221/ нетленное
У меня при прочтении этого возник главный вопрос - "нахрена?" Семейство Xorshift 1) имеет при любом стартовом значении гарантированный цикл 2^N-1, 2) проходит тесты DieHard - это серьёзный результат, 3) легче реализуется на слабом железе (нет умножений). Открыто в 1995-м, то есть к моменту выхода этой игры успело закончить школу и проголосовать:) Зачем пользоваться линейным конгруэнтным генератором образца 1960-х, не понимая его устройство?
(Вообще хотелось бы ещё почитать про Джорджа Марсалью. Главный научный результат в 70 лет - его жизнь заслуживает отдельного описания.)
А вы не путаете? Голый ксоршифт, без пост-обработки, дайхард как раз фейлит на ура. А пост-обработка включает в себя в т.ч. и умножения.
Я имел в виду всё семейство, включая "плюсовые" варианты. Вот специально слазил в википедию, чтобы далеко не ходить, и добуквенно копирую код в её версии:
uint64_t xorshift128p(struct xorshift128p_state *state)
{
uint64_t t = state->x[0];
uint64_t const s = state->x[1];
state->x[0] = s;
t ^= t << 23; // a
t ^= t >> 18; // b -- Again, the shifts and the multipliers are tunable
t ^= s ^ (s >> 5); // c
state->x[1] = t;
return t + s;
}Этот вариант проходит тесты и никакого умножения нет. И для мелкого процессора он дешевле обычных умножений.
3) легче реализуется на слабом железе (нет умножений)
Чтобы получить 32 новых бита от XORSHIFT, нужно сделать сдвиг 32 раза на слабом железе. И умножение 32x32 делается через 32 сложения - ровно то же самое. На сильном умножение - 1 действие, ну может где-то пара лишних тактов.
XORSHIFT реально удобен только в железной реализации, типа FPGA или ASIC - занимает необходимый минимум, чтобы хранить эти 2^N-1 внутренних состояний.
Для линейного просто нужно фильтровать seed, и выбирать хорошие коэффициенты. Тут в обсуждениях у коллеги вашего товарищ правильно сослался на мэтра)
нужно сделать сдвиг 32 раза на слабом железе.
Я бы предположил, что железо с бочкой сдвига сейчас всяко вероятнее, чем без оной. А вот чтобы в сельпо ещё и Dadda multiplier (или аналог) завезли - это несколько более высокий уровень. Вспомним первые ARMы, там как раз такое распределение возможностей было.
Для линейного просто нужно фильтровать seed, и выбирать хорошие коэффициенты.
Не, ну история с 65539 уже давно выкарбована зубилом по зубам всех пострадавших:))
Ну вот пример из того же ARM:
https://developer.arm.com/documentation/dui0646/c/The-Cortex-M7-Instruction-Set/General-data-processing-instructions/ASR--LSL--LSR--ROR--and-RRX
Cortex - это как раз про слабое железо, урезанный до Thumb набор команд, наши ненаглядные микроконтроллеры. Сдвиг только на +-1 есть. Никаких barrel shift нет. При этом умножение уже завезли, и даже деление.
Cortex - это как раз про слабое железо, урезанный до Thumb набор команд, наши ненаглядные микроконтроллеры. Сдвиг только на +-1 есть.
Хм, по вашей же ссылке
Examples
ASR R7, R8, #9 ; Arithmetic shift right by 9 bits.
ROR R4, R5, R6 ; Rotate right by the value in the bottom byte of R6.
Или вы имели в виду, что там сдвиг на бит за такт?
Ну так там и блок умножения будет примерно такой же медленный. (А деление ещё хуже)
Да, это я ошибся по невнимательности, там сдвиг на любое значение, даже в Cortex-M0. Но и умножение в Cortex-M0 тоже есть, пускай и за 2 такта делается.
В качестве "слобого железа" лучше, наверное, посмотреть в сторону 8-битной классики:
8051 - умножение есть, за 2 такта. Сдвиги только на +-1
STM8 - не классика, но то же самое
AVR - умножение не везде есть. Сдвиги только на +-1
Z80 - полный олдскул, умножения нет, сдвиги на +-1
Полноценный сдвиг появляется только в 16-битных 8086, но тут уже и умножение, и деление присутствует.
Ну я тут, конечно, немного "пофантазировал". Раз есть умножение, то и сдвиг на фиксированную константу через него же и делается. Но ведь не наоборот! Нет умножения - нет и "бочки".
И классический LFSR всё равно побитный, или табличный. Тут ускорение есть, вариант неплохой, но за всё приходится платить ценой более прозрачной предсказуемости.
там на самом деле всё интереснее если вы симплексом будете делать на поверхности воды броуновское волнение субгладей так сказать, где волны будут колебаться в определённом соотношении(определенное соотношение будет доменом, но это еще не Фурье)(и этот подход будет пока еще дешевый на рендер в шейдере по всем параметрам) там вполне себе получается вода, и с таким рандомом, который вы показали можно генерировать ландшафт, правда со сглаживанием (это можно посмотреть даже в каком-то туториале даже сегодня, правда туториалу лет 14), где-то рядом тема IEEE float-point еще
Понимаю, что это перевод, но всё равно интересно:
При случайном начальном rand_nsmb в среднем повторит свой вывод спустя 1820529 вызовов.
<...>
1 цикл длиной 1708724
Не могу понять, как это совместимо. Если самый длинный цикл имеет длину - отформатируем для наглядности - 1_708_724, т.е. в лучшем случае повтор вывода будет через столько вызовов, то как в среднем он может быть через 1_820_529, т.е. через большее число вызовов?
Генератор случайных чисел, застрявший на одном значении