Сообщение от
Barmaley_m
Числа 255 и 65535 имеют вид 2N-1, и остаток от деления на них "даром" не дается. Возможно, ты имел в виду 256 и 65536. Но это ошибка в твоем сообщении, а не моем. Зачем в таком случае ты взялся меня с пафосом опровергать?
Это просто нотация
Да, действительно, бывают и ЛКГ по модулю 2
n. Но это можно было просто пояснить, особенно учитывая, что это твое сообщение было причиной возникновения данной ситуации.
Они не "бывают", а все так построены.
По твоей же ссылке в Википедии приводятся примеры ЛКГ с модулем, не равным степени двойки. Один из них используется в glibc. Они что, ненастоящие? Нафантазированные?
Неа, просто нотация: https://github.com/lattera/glibc/blo...lib/random_r.c line 374:
Код:
{
int32_t val = state[0];
val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
state[0] = val;
*result = val;
}
То есть как видишь, все та же нотация. Увидели в коде это число - ну так и прописали.
На практике просто сколько бит, максимум 2^16 ... 2^32
Не исключено, что работа по модулю вида 2
N-1 дает какие-то преимущества, оправдывающие повышение сложности генератора. Иначе никто в здравом уме не стал бы так делать.
Да не, не надо о таком даже думать, число надо подбирать согласно условиям. Взаимно-простые, итдэ.
Практические же реализации берут всегда просто сколько-то бит. Смело надо ориентироваться на это. Т.е. деления нет.
P.S.
Не очень-то хорошие xorshift'ы.
Я поясню, почему я их так не люблю. "Гладко было на бумаге". Когда я ПРАКТИЧЕСКИ экспериментировал с rnd-генераторами основанными на сдвиговых регистрах, вечно вылезала с ними какая-то убогость при анализе их последовательности на практике.
Просто так с наскока xorshift'ы не даются, их надо "уметь готовить". Но будучи "приготовленными" по всем правилам, они до некоторой степени теряют основную прелесть - простоту, вот тут-то LCG их обходит, будучи более простым как танк, железно проверенным десятками лет, и в то же время намного более предсказуемым.
На x86 это две инструкции:
Код:
lea eax, [eax*4 + eax]
inc eax
врочем Haswell и так делает mul за 3c.
Не бухти, Barmaley_m :-)
Сообщение от
hobot
А как такое переписать на МАКРО-11, что за оператор ^= и <<
Можно как-то в виде готовой функции оформить для не программера вроде меня, что бы протестировать и
возможно использовать? (использовать в программах для RT-11 разумеется, не для спектрума!) Очень желательно ПАСКАЛЬ - главное что бы не Си !!!
^=
произвести xor и присвоить, x^= 5 короткая запись x = x ^ 5; в паскале это xor
<<
сдвиг влево на сколько-то бит. в паскале shl
>>
сдвиг вправо на сколько-то бит. в паскале shr
Глядим сюда
Компиляй и запускай здесь: http://rextester.com/l/pascal_online_compiler
Код:
//fpc 3.0.0
program HelloWorld;
Uses
sysutils;
var
x: Cardinal = 1;
function xorshift32: Cardinal;
begin
x := x xor (x shl 13);
x := x xor (x shr 17);
x := x xor (x shl 5);
xorshift32 := x;
end;
begin
writeln(Format('%.8X', [xorshift32]));
writeln(Format('%.8X', [xorshift32]));
writeln(Format('%.8X', [xorshift32]));
end.