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

User Tag List

Страница 1 из 4 1234 ПоследняяПоследняя
Показано с 1 по 10 из 32

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

  1. #1
    Veteran Аватар для Oleg N. Cher
    Регистрация
    24.08.2007
    Адрес
    Днепропетровская обл.
    Сообщений
    1,593
    Спасибо Благодарностей отдано 
    2,158
    Спасибо Благодарностей получено 
    130
    Поблагодарили
    96 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

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

    Господа, не поможете ли решить такую задачку. Требуется переписать на асм функции генерации случ. чисел в заданном диапазоне - для байтов и для слов. Сейчас они написаны у меня частично на Си, что конечно не так эффективно.

    Код:
    /*--------------------------------- Cut here ---------------------------------*/
    /* SEED_RND address */
    #define SF_RND$ 0x5C76
    
    unsigned int _Basic_RandBB (void) /* Ripped from Beta Basic */
    {
    __asm
      LD   D,#0
      LD   BC,(#SF_RND$)
      LD   H,C
      LD   L,#0xFD
      LD   A,B
      OR   A
      SBC  HL,BC
      SBC  A,D
      SBC  HL,BC
      SBC  A,D
      LD   E,A
      SBC  HL,DE
      JR   NC,R1$
      INC  HL
    R1$:
      LD  (#SF_RND$),HL
    __endasm;
    } //__Basic_RandBB
    
    /*--------------------------------- Cut here ---------------------------------*/
    unsigned char Basic_RND (unsigned char min, unsigned char max) {
      return _Basic_RandBB()%(max-min+1) + min;
    } //Basic_RND
    
    /*--------------------------------- Cut here ---------------------------------*/
    unsigned int Basic_RNDW (unsigned int min, unsigned int max) {
      return _Basic_RandBB()%(max-min+1) + min;
    } //Basic_RNDW
    Опять же, знаю, что много где в прессе и на форумах приводятся разные генераторы случ. чисел, но вопрос именно про в заданном диапазоне, так что поделитесь, пожалуйста, наработками. А можно смотреть на тему шире, не возражаю если вообще обсудим случайные, а не псевдослучайные числа и методы их получения на Z80.

  2. #1
    С любовью к вам, Yandex.Direct
    Размещение рекламы на форуме способствует его дальнейшему развитию

  3. #2
    Guru Аватар для Sayman
    Регистрация
    16.02.2006
    Адрес
    Новосибирск
    Сообщений
    3,277
    Спасибо Благодарностей отдано 
    17
    Спасибо Благодарностей получено 
    91
    Поблагодарили
    54 сообщений
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    загляни в evo sdk, там есть rand16() на асме писанная.
    0A заповедей:
    I. Не удаляй каталог свой.
    II. Не удаляй до времени ни одного файла.
    III. Не кради файлы.
    IV. Не желай программы ближнего своего.
    V. Почитай BDOS и BIOS как родителей своих ...
    ---
    Sprinter resurrect:
    Telegram
    Discord
    Repo
    Forum

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

    По умолчанию

    Цитата Сообщение от Oleg N. Cher Посмотреть сообщение
    Господа, не поможете ли решить такую задачку. Требуется переписать на асм функции генерации случ. чисел в заданном диапазоне - для байтов и для слов. Сейчас они написаны у меня частично на Си, что конечно не так эффективно.
    Опять же, знаю, что много где в прессе и на форумах приводятся разные генераторы случ. чисел, но вопрос именно про в заданном диапазоне, так что поделитесь, пожалуйста, наработками. А можно смотреть на тему шире, не возражаю если вообще обсудим случайные, а не псевдослучайные числа и методы их получения на Z80.
    Все задачи решает линейный конгруэнтный генератор (Linear congruential generator - см. wikipedia, также советую почитать Lehmer random number generator)
    Его формула СледЧисл = (A * Число + B) MOD N

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

    Для достижения максимальной длины последовательности к A и B предъявляются определенные требования. B нечетное, A нечетное и берется таким что остаток от деления его на 4 равен 1. В статье Wikipedia условия несколько более сложные.
    Этому удовлетворяют например, A=5, B=1. Тогда на ассемблере Z80 код простейшего 8-битного датчика ПСЧ получается:
    Код:
    SEED:  LD  A, #33   ; любое начальное значение
    LD B,A
    ADD A,A
    ADD A,A
    ADD A,B ; это умножение на 5, т.е. A=5
    INC A     ; это B=1
    LD (SEED+1), A
    аналогично можно построить 16-битный датчик ПСЧ, используя регистровую пару.
    Родной RND-генератор BASIC использует A=75 и B=1, N=65535

    Теперь что касается генерации чисел в заданном диапазоне.
    С сохранением статистического распределения приемлемо быстрого решения (на мой личный взгляд) нет, за исключением использования специальных алгоритмов. Самое простое это взять генератор и использовать N старших бит, получая псевдослучайые числа в диапазоне [0...N-1].

    Следует учитывать что линейный конгруэнтный генеретор генерирует псевдослучайные числа, но не биты.
    Поэтому биты в линейном конгруэнтном генераторе неравноценны. Наибольшая длина последовательности отражена в старших битах, поэтому использовать следует именно их, они наиболее "шумящие".
    Alex Raider, Flash inc. 1992-1997 Новосибирск

  5. #4
    Veteran Аватар для Bedazzle
    Регистрация
    02.05.2015
    Адрес
    г. Таллин, Эстония
    Сообщений
    1,485
    Спасибо Благодарностей отдано 
    219
    Спасибо Благодарностей получено 
    149
    Поблагодарили
    115 сообщений
    Mentioned
    9 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Raider Посмотреть сообщение
    Тогда на ассемблере Z80 код простейшего 8-битного датчика ПСЧ получается:
    Пять тысяч значений ложатся так:

  6. #5
    Veteran
    Регистрация
    26.11.2013
    Адрес
    г. Новосибирск
    Сообщений
    1,041
    Спасибо Благодарностей отдано 
    931
    Спасибо Благодарностей получено 
    224
    Поблагодарили
    121 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Можем ли определить, при компиляции, являются ли аргументы константами?

  7. #6
    Veteran Аватар для Oleg N. Cher
    Регистрация
    24.08.2007
    Адрес
    Днепропетровская обл.
    Сообщений
    1,593
    Спасибо Благодарностей отдано 
    2,158
    Спасибо Благодарностей получено 
    130
    Поблагодарили
    96 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    При компиляции - конечно можем. А вот внутри самой процедуры - нет.

    Просто мало смысла зауживать процедуру только для диапазанов-констант. Хотя эффективность для известных значений конечно может быть выше, не спорю. AND 7 вместо MOD 8, например. =) Но такую оптимизацию компилятор сам делает.

  8. #7
    Veteran
    Регистрация
    26.11.2013
    Адрес
    г. Новосибирск
    Сообщений
    1,041
    Спасибо Благодарностей отдано 
    931
    Спасибо Благодарностей получено 
    224
    Поблагодарили
    121 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Компилятор сам делает!? Тогда нет проблем!
    Raider пишет что надо использовать старшие биты, так что ты свой остаток от деления замени на деление. А компилятор уже будет оптимизировать деление на константу, заменяя её сдвигами.

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

    По умолчанию

    Цитата Сообщение от Bedazzle Посмотреть сообщение
    Пять тысяч значений ложатся так:
    1. Это с 8-ю битами (N=255) ?
    2. Что это, как построен график. Шагали по оси абсцисс и отражали по оси ординат полученное ПСЧ?

    Выше это был пример. Для практической реализации надо использовать минимум N=65535
    Код:
    LD HL, (SEED)
    LD D,H
    LD E,L
    ADD HL,HL
    ADD HL,HL
    ADD HL,DE    ; HL=HL*5
    INC HL       ;  + 1
    LD (SEED),HL
    RET
    SEED: DW 0
    Для работы с длинными последовательностями следует брать минимум N=65535. Длина последовательности будет 2^16.
    "качество" ПСЧ-последовательности можно простейшим способом анализировать путем взятия двух соседних отсчетов и отображения их по X,Y.
    Если между X и Y существует корреляция, то точки начнут выстраиваться в какие-либо структуры (чаще полоски) и заполнение экрана будет не равномерным.
    Распределение точек по экрану должно быть шумоподобное (Монте-Карло), т.е. точки должны ставиться равномерно по всей площади экрана.
    В 90х годах у меня была статья по нескольким генераторам ПСЧ которые я нашел в игрушках. Скорее всего это "самоделки" программистов. Все они в той или иной степени проваливали даже описанный выше тест звездного неба.
    Для реальной оценки ПСЧ существуют известные статистические тесты, например спектральный тест.

    Линейный конгруэнтный генератор не идеален, имеет недостатоки (см. статью wikipedia). Однако он простейший и быстрейший, т.е. обладает необходимым балансом качеств. Сейчас существуют современные и чуть более сложные алгоритмы генераторов ПСЧ, см. https://en.wikipedia.org/wiki/List_o...ber_generators
    в библиотеке такой более сложный генератор имеет смысл предлагать опционально.
    Последний раз редактировалось Raider; 11.01.2017 в 12:45.
    Alex Raider, Flash inc. 1992-1997 Новосибирск

  10. #9
    Veteran Аватар для Hacker VBI
    Регистрация
    05.03.2013
    Адрес
    г. Канев, Украина
    Сообщений
    1,596
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    3
    Поблагодарили
    2 сообщений
    Mentioned
    7 Post(s)
    Tagged
    0 Thread(s)

  11. #10
    Veteran Аватар для Bedazzle
    Регистрация
    02.05.2015
    Адрес
    г. Таллин, Эстония
    Сообщений
    1,485
    Спасибо Благодарностей отдано 
    219
    Спасибо Благодарностей получено 
    149
    Поблагодарили
    115 сообщений
    Mentioned
    9 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Raider Посмотреть сообщение
    1. Это с 8-ю битами (N=255) ?
    2. Что это, как построен график. Шагали по оси абсцисс и отражали по оси ординат полученное ПСЧ?
    оба ответа "да".
    Разве что с поправкой, что 8 бит это 256

    Цитата Сообщение от Raider Посмотреть сообщение
    Выше это был пример. Для практической реализации надо использовать минимум N=65535
    График добавлен как предостережение тем, кто мог набежать и невдумчиво использовать вместо серьёзного генератора.

Страница 1 из 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

Ваши права

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