Генерация случайных чисел в заданном диапазоне

Цитата:

---

Сообщение от Barmaley_m

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

---

В ЛКГ нет деления, это что-то попутано.
Есть умножение, заменяемое сдвигами. Код был приведен выше.

Ссылка на Xorshift была выше, но его практическая реализация через произвольные сдвиги медленнее чем ЛКГ.
Xorshift это подвид LFSR, ссылка на эффективный LFSR была выше.

«Вихрь Мерсенна» как и другие, скажем, криптостойкие генераторы ПСЧ для для 8-биток с int = 2⁸ и 65536-ю адресами использовать бессмысленно. В компьютере меньше доступной памяти чем период примитивного ПСЧ c 16-битным seed, а в случае "Вихря Мерсенна" как исчерпать хотя бы ничтожную часть его периода?

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

Цитата:

---

Сообщение от Raider

В ЛКГ нет деления, это что-то попутано.

---

В ЛКГ есть операция взятия остатка от деления, что по сложности то же самое, что деление. Кстати, я обнаружил ошибку в твоих рассуждениях на тему того, что умножение или сложение по модулю 255 или 65535 эквивалентно отбрасыванию старших бит. Это не так. Отбрасывание старших бит дает остаток от деления на 2^N, а надо делить на 2^N-1, что не то же самое.

Так, сохранение младших 8 бит даст остаток от деления на 256, но делить-то надо на 255.

Есть способы получать остаток от деления на 2^N-1 без применения полной процедуры деления. Но для этого нельзя отбрасывать старшие биты просто так. Их надо прибавлять к содержимому младших. Такой подход реализован при вычислении контрольных сумм Флетчера, где используется сложение по модулю 255, или же контрольных сумм TCP/IP, где используется сложение по модулю 65535. Но в твоем коде этот подход не реализован, поэтому код неправильный. Вероятно, твои генераторы не будут давать максимальный период повторения.

Цитата:

---

Сообщение от Raider

Xorshift это подвид LFSR, ссылка на эффективный LFSR была выше.

---

Не совсем. LFSR дает поток случайных бит, но не чисел. Эти биты еще надо как-то объединять в числа, на практике простые LFSR для получения многобитных чисел не используются. Вместо них используются ЛКГ, GFSR или MT. Ну и вот Xorshift тоже - он генерирует числа, а не просто биты, чем и полезен. В противном случае можно было бы пользоваться LFSR, его реализация проще, в ней используются сдвиги только на 1 бит.

Цитата:

---

Сообщение от Raider

В компьютере меньше доступной памяти чем период примитивного ПСЧ c 16-битным seed, а в случае "Вихря Мерсенна" как исчерпать хотя бы ничтожную часть его периода?

---

Ты недооцениваешь важность иметь длинный период повторения. Случайные числа не только сохраняют в память, их еще используют для генерации игрового процесса, лабиринтов, вычислений методом Монте-Карло и др. Бывают применения, в которых "потребление" нескольких тысяч случайных чисел - обычное дело. Период 16-битного генератора исчерпается за несколько вызовов процедуры, его использующей. И тогда в игре появятся повторяющиеся лабиринты и прочие гадости, а вычисления методом Монте-Карло дадут неверный результат.

Я думаю, что применительно к Спектруму достаточная длина последовательности генератора должна выбираться из следующих соображений:
1) Время работы компьютера, в течение которого можно сгенерировать полный период последовательности. Оно должно составлять по меньшей мере несколько суток, тогда как 16-битная последовательность может исчерпаться за секунды или минуты.
2) Варианты старта последовательности. Дело в том, что в генераторах ПСЧ последовательность всегда одинаковая, и случайность достигается за счет того, что генерация стартует из разного ее места. Если за один заход требуется, скажем, 1000 случайных чисел - то при 16-битном генераторе будет всего 65 вариантов различных неповторяющихся случайных потоков. Мало.

Думаю, для Спектрума необходимо иметь как минимум 24, а лучше 32 бита состояния генератора ПСЧ.

Цитата:

---

Сообщение от Barmaley_m

В ЛКГ есть операция взятия остатка от деления, что по сложности то же самое, что деление. Кстати, я обнаружил ошибку в твоих рассуждениях на тему того, что умножение или сложение по модулю 255 или 65535 эквивалентно отбрасыванию старших бит. Это не так. Отбрасывание старших бит дает остаток от деления на 2^N, а надо делить на 2^N-1, что не то же самое.

Так, сохранение младших 8 бит даст остаток от деления на 256, но делить-то надо на 255.

---

Да короткая подпрограммой LCG показано не является правильным.

Есть некоторые очень высокого качества генераторы случайных чисел, которые были написаны для z80 в WOS.

Первым из них является 10 ^ 20 период CMWC генератор, который возвращает 8-битовых случайных чисел:
http://z88dk.cvs.sourceforge.net/vie...e=text%2Fplain

Как вы можете видеть, что это очень быстро и коротким. Ссылка на исходный поток в WOS можно найти в исходном коде.


Тот, который мы используем в качестве генератора по умолчанию для rand() в z88dk является генератором Marsaglia XORshift:
http://z88dk.cvs.sourceforge.net/vie...e=text%2Fplain

32 бита состояния используется и конкретный (L, R, L) тройной выбирают для своей простоты реализации. Опять же, код достаточно быстро и коротким. Ссылка на документ с описанием генераторов XOR Marsaglia будет дан.


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

Скрытый текст

Yes the short LCG subroutine shown is not correct.

There are some very high quality random number generators that have been written for the z80 at WOS.

The first is a 10^20 period CMWC generator that returns 8-bit random numbers:
http://z88dk.cvs.sourceforge.net/vie...e=text%2Fplain

As you can see it is fast and short. A link to the original thread at WOS can be found in the source code.

The one we use as default generator for rand() in z88dk is a Marsaglia XOR shift generator:
http://z88dk.cvs.sourceforge.net/vie...e=text%2Fplain

32-bits of state is used and the particular (L,R,L) triple is selected for its ease of implementation. Again, the code is fairly fast and short. A link to Marsaglia's paper describing XOR generators is given.


The period is very important especially when you are trying to generate random numbers from a range smaller than what the generator produces. You will see a lot of patterns emerge if the period is small or the generator is weak.

[свернуть]

Цитата:

---

Сообщение от Barmaley_m

В ЛКГ есть операция взятия остатка от деления, что по сложности то же самое, что деление. Кстати, я обнаружил ошибку в твоих рассуждениях на тему того, что умножение или сложение по модулю 255 или 65535 эквивалентно отбрасыванию старших бит. Это не так. Отбрасывание старших бит дает остаток от деления на 2^N, а надо делить на 2^N-1, что не то же самое.

Так, сохранение младших 8 бит даст остаток от деления на 256, но делить-то надо на 255.

---

Это ложно.
Число берется равное 2ⁿ (256, 65536) и конечно же берется остаток от деления на него. Что в случае регистров длиной 2ⁿ дается даром.

Цитата:

---

Есть способы получать остаток от деления на 2^N-1 без применения полной процедуры деления. Но для этого нельзя отбрасывать старшие биты просто так. Их надо прибавлять к содержимому младших. Такой подход реализован при вычислении контрольных сумм Флетчера, где используется сложение по модулю 255, или же контрольных сумм TCP/IP, где используется сложение по модулю 65535. Но в твоем коде этот подход не реализован, поэтому код неправильный. Вероятно, твои генераторы не будут давать максимальный период повторения.

---

Я пишу о реализации ЛКГ , которые я неоднократно видел в реальном коде своими глазами. Все настоящие ЛКГ (а не то, как это внезапно нафантазировано) выбирают m в формуле mod m равное степени двойки 2^m. И имеют при этом максимальный период равный 2^m.

Предложу заглянуть в https://en.wikipedia.org/wiki/Linear...tial_generator - с таблицей из ПРАКТИЧЕСКИХ уже существующих много лет реализаций.
А также предложу ознакомиться с реальным кодом этих реализаций.

Приведенный выше код ЛКГ верен и проверен на практике. Период его повторения равен 2^m , где m = 8 или 16.
При этом он остается самым быстрым и простым.

Код:

---

xorshift8:       
        ld a,1
        ld b,a
        add a,a
        xor b
        ld b,a
        srl a
        xor b
        ld b,a
        add a,a
        add a,a
        xor b
        ld (xorshift8+1),a
        ret

---

- проверен на практике, период равен 255.

xor b
ld b,a
srl a

как насчет rra? )

Имеем 16-битный xorshift. Если рассматривать его выход как уникальные 16-битные числа, длина уникальной последовательности 16-битных word'ов получается 65535, все хорошо. Но если берем из его 16-бит один байт, то в зависимости от констант a,b,c и в зависимости от того какой байт мы берем, старший или младший - длина последовательности может получиться меньше. Думается это потому что внутри seed-переменной xorshift'а разные биты "вращаются" с разными циклами.
Так что не всё просто, и всегда надо тестировать на практике.
Как я догадываюсь, чтобы получить один байт на выходе, байты xorshift'а надо складывать по xor.

Цитата:

---

Сообщение от char

xor b
ld b,a
srl a

как насчет rra? )

---

Во-во, именно так!
Я вчера с похмела вообще забыл какую-либо оптимизацию провести, как экспериментировал так и шурнул на форум. :-)

Цитата:

---

Сообщение от Raider

Это ложно.
Число берется равное 2ⁿ (256, 65536) и конечно же берется остаток от деления на него. Что в случае регистров длиной 2ⁿ дается даром.

---

В сообщении №3 ты писал:

Цитата:

---

Сообщение от Raider

Его формула СледЧисл = (A * Число + B) MOD N

выражение (Число * A) MOD N означает остаток от деления, но если умножение и сложение реализуется с возможным переполнением ("заворотом"), то функция MOD N достигается даром. То есть если регистры восьмибитные, то N = 255, если 16-битные то N = 65535 что как раз и отвечает заданным требованиям.

---

Числа 255 и 65535 имеют вид 2^N-1, и остаток от деления на них "даром" не дается. Возможно, ты имел в виду 256 и 65536. Но это ошибка в твоем сообщении, а не моем. Зачем в таком случае ты взялся меня с пафосом опровергать?

Да, действительно, бывают и ЛКГ по модулю 2ⁿ. Но это можно было просто пояснить, особенно учитывая, что это твое сообщение было причиной возникновения данной ситуации.

Цитата:

---

Сообщение от Raider

Я пишу о реализации ЛКГ , которые я неоднократно видел в реальном коде своими глазами. Все настоящие ЛКГ (а не то, как это внезапно нафантазировано) выбирают m в формуле mod m равное степени двойки 2^m. И имеют при этом максимальный период равный 2^m.

---

По твоей же ссылке в Википедии приводятся примеры ЛКГ с модулем, не равным степени двойки. Один из них используется в glibc. Они что, ненастоящие? Нафантазированные?

Не исключено, что работа по модулю вида 2^N-1 дает какие-то преимущества, оправдывающие повышение сложности генератора. Иначе никто в здравом уме не стал бы так делать.

Цитата:

---

Сообщение от Barmaley_m

#include <stdint.h> /* The state word must be initialized to non-zero */ uint32_t xorshift32(uint32_t state[static 1]) { uint32_t x = state[0]; x ^= x << 13; x ^= x >> 17; x ^= x << 5; state[0] = x; return x; }

---

А как такое переписать на МАКРО-11, что за оператор ^= и <<
Можно как-то в виде готовой функции оформить для не программера вроде меня, что бы протестировать и
возможно использовать? (использовать в программах для RT-11 разумеется, не для спектрума!) Очень желательно ПАСКАЛЬ - главное что бы не Си !!!

Спасибо.

- - - Добавлено - - -

у меня есть старенькая функция генерации - у неё одна проблема 1-е число ) Как это победить - я не знаю увы.

Цитата:

---

Сообщение от Barmaley_m

Числа 255 и 65535 имеют вид 2^N-1, и остаток от деления на них "даром" не дается. Возможно, ты имел в виду 256 и 65536. Но это ошибка в твоем сообщении, а не моем. Зачем в таком случае ты взялся меня с пафосом опровергать?

---

Это просто нотация

Цитата:

---

Да, действительно, бывают и ЛКГ по модулю 2ⁿ. Но это можно было просто пояснить, особенно учитывая, что это твое сообщение было причиной возникновения данной ситуации.

---

Они не "бывают", а все так построены.

Цитата:

---

По твоей же ссылке в Википедии приводятся примеры ЛКГ с модулем, не равным степени двойки. Один из них используется в 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.

---