Важная информация

User Tag List

Страница 3 из 4 ПерваяПервая 1234 ПоследняяПоследняя
Показано с 21 по 30 из 32

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

  1. #21
    Activist Аватар для Raider
    Регистрация
    24.06.2005
    Адрес
    novosibirsk
    Сообщений
    266
    Записей в дневнике
    5
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    1
    Поблагодарили
    1 сообщение
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Barmaley_m Посмотреть сообщение
    Я тут провел небольшое исследование темы и обнаружил, что наука шагнула вперед за последние годы, так что линейный конгруэнтный генератор с его необходимостью деления отходит на второй план.
    В ЛКГ нет деления, это что-то попутано.
    Есть умножение, заменяемое сдвигами. Код был приведен выше.

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

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

    Наколхозить любой современный криптостойкий генератор, симулируя int64-арифметику и 1000-байтные массивы возможно.
    Но в чем смысл этого, бессмысленный и беспощадный?
    Последний раз редактировалось Raider; 13.01.2017 в 19:49.
    Alex Raider, Flash inc. 1992-1997 Новосибирск

  2. #22
    Veteran
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    1,053
    Спасибо Благодарностей отдано 
    218
    Спасибо Благодарностей получено 
    47
    Поблагодарили
    31 сообщений
    Mentioned
    3 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от 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 бита состояния генератора ПСЧ.

  3. #23
    Member
    Регистрация
    21.05.2006
    Адрес
    Canada
    Сообщений
    78
    Спасибо Благодарностей отдано 
    3
    Спасибо Благодарностей получено 
    2
    Поблагодарили
    2 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от 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.
    [свернуть]
    Последний раз редактировалось Alcoholics Anonymous; 14.01.2017 в 02:47.

  4. #24
    Activist Аватар для Raider
    Регистрация
    24.06.2005
    Адрес
    novosibirsk
    Сообщений
    266
    Записей в дневнике
    5
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    1
    Поблагодарили
    1 сообщение
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

    Так, сохранение младших 8 бит даст остаток от деления на 256, но делить-то надо на 255.
    Это ложно.
    Число берется равное 2n (256, 65536) и конечно же берется остаток от деления на него. Что в случае регистров длиной 2n дается даром.

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

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

    Приведенный выше код ЛКГ верен и проверен на практике. Период его повторения равен 2m , где 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.
    Последний раз редактировалось Raider; 14.01.2017 в 10:51.
    Alex Raider, Flash inc. 1992-1997 Новосибирск

  5. #25
    Activist
    Регистрация
    15.01.2005
    Сообщений
    201
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    7
    Поблагодарили
    7 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    xor b
    ld b,a
    srl a

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

  6. #26
    Activist Аватар для Raider
    Регистрация
    24.06.2005
    Адрес
    novosibirsk
    Сообщений
    266
    Записей в дневнике
    5
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    1
    Поблагодарили
    1 сообщение
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

  7. #27
    Activist Аватар для Raider
    Регистрация
    24.06.2005
    Адрес
    novosibirsk
    Сообщений
    266
    Записей в дневнике
    5
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    1
    Поблагодарили
    1 сообщение
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от char Посмотреть сообщение
    xor b
    ld b,a
    srl a

    как насчет rra? )
    Во-во, именно так!
    Я вчера с похмела вообще забыл какую-либо оптимизацию провести, как экспериментировал так и шурнул на форум. :-)
    Alex Raider, Flash inc. 1992-1997 Новосибирск

  8. #28
    Veteran
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    1,053
    Спасибо Благодарностей отдано 
    218
    Спасибо Благодарностей получено 
    47
    Поблагодарили
    31 сообщений
    Mentioned
    3 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Raider Посмотреть сообщение
    Это ложно.
    Число берется равное 2n (256, 65536) и конечно же берется остаток от деления на него. Что в случае регистров длиной 2n дается даром.
    В сообщении №3 ты писал:
    Цитата Сообщение от Raider Посмотреть сообщение
    Его формула СледЧисл = (A * Число + B) MOD N

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

    Да, действительно, бывают и ЛКГ по модулю 2n. Но это можно было просто пояснить, особенно учитывая, что это твое сообщение было причиной возникновения данной ситуации.
    Цитата Сообщение от Raider Посмотреть сообщение
    Я пишу о реализации ЛКГ , которые я неоднократно видел в реальном коде своими глазами. Все настоящие ЛКГ (а не то, как это внезапно нафантазировано) выбирают m в формуле mod m равное степени двойки 2m. И имеют при этом максимальный период равный 2m.
    По твоей же ссылке в Википедии приводятся примеры ЛКГ с модулем, не равным степени двойки. Один из них используется в glibc. Они что, ненастоящие? Нафантазированные?

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

  9. #29
    R.I.P. Аватар для hobot
    Регистрация
    30.08.2011
    Адрес
    Зеленоград
    Сообщений
    7,161
    Спасибо Благодарностей отдано 
    2,979
    Спасибо Благодарностей получено 
    370
    Поблагодарили
    309 сообщений
    Mentioned
    13 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от 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-е число ) Как это победить - я не знаю увы.
    Архив программ для УК-НЦ, ДВК и БК.

    Ищу игру "СТРАНА МОНСТРОВ" [monstr.sav] для ДВК.

  10. #30
    Activist Аватар для Raider
    Регистрация
    24.06.2005
    Адрес
    novosibirsk
    Сообщений
    266
    Записей в дневнике
    5
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    1
    Поблагодарили
    1 сообщение
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

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

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

    Не исключено, что работа по модулю вида 2N-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.
    Последний раз редактировалось Raider; 19.01.2017 в 00:36.
    Alex Raider, Flash inc. 1992-1997 Новосибирск

Страница 3 из 4 ПерваяПервая 1234 ПоследняяПоследняя

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. Ответов: 54
    Последнее: 10.08.2020, 14:28
  2. генератор случайных чисел на БК
    от litwr в разделе БК-0010/0011
    Ответов: 6
    Последнее: 28.09.2018, 14:06
  3. Генерация синуса
    от Hacker VBI в разделе Программирование
    Ответов: 154
    Последнее: 02.06.2014, 15:54
  4. Генерация лабиринтов
    от TomCaT в разделе Программирование
    Ответов: 90
    Последнее: 26.06.2012, 10:59

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •