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

User Tag List

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

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

Комбинированный просмотр

Предыдущее сообщение Предыдущее сообщение   Следующее сообщение Следующее сообщение
  1. #1
    Master Аватар для Oleg N. Cher
    Регистрация
    24.08.2007
    Адрес
    Днепропетровская обл.
    Сообщений
    754
    Благодарностей: 207
    Mentioned
    0 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
    Адрес
    Новосибирск
    Сообщений
    2,449
    Благодарностей: 218
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

  4. Этот пользователь поблагодарил Sayman за это полезное сообщение:
    Oleg N. Cher (10.01.2017)

  5. #3
    Activist Аватар для Raider
    Регистрация
    24.06.2005
    Адрес
    novosibirsk
    Сообщений
    263
    Благодарностей: 71
    Записей в дневнике
    3
    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 Новосибирск

  6. Эти 3 пользователя(ей) поблагодарили Raider за это полезное сообщение:
    Barmaley_m (12.01.2017), Oleg N. Cher (10.01.2017), Titus (10.01.2017)

  7. #4
    Master Аватар для Bedazzle
    Регистрация
    02.05.2015
    Адрес
    г. Таллин, Эстония
    Сообщений
    532
    Благодарностей: 105
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

  8. Эти 2 пользователя(ей) поблагодарили Bedazzle за это полезное сообщение:
    Oleg N. Cher (10.01.2017), Raider (11.01.2017)

  9. #5
    Activist Аватар для Raider
    Регистрация
    24.06.2005
    Адрес
    novosibirsk
    Сообщений
    263
    Благодарностей: 71
    Записей в дневнике
    3
    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 в 13:45.
    Alex Raider, Flash inc. 1992-1997 Новосибирск

  10. Этот пользователь поблагодарил Raider за это полезное сообщение:
    Oleg N. Cher (11.01.2017)

  11. #6
    Master Аватар для Bedazzle
    Регистрация
    02.05.2015
    Адрес
    г. Таллин, Эстония
    Сообщений
    532
    Благодарностей: 105
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

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

  12. #7
    Master Аватар для Bedazzle
    Регистрация
    02.05.2015
    Адрес
    г. Таллин, Эстония
    Сообщений
    532
    Благодарностей: 105
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Raider Посмотреть сообщение
    "качество" ПСЧ-последовательности можно простейшим способом анализировать путем взятия двух соседних отсчетов и отображения их по X,Y.
    Если между X и Y существует корреляция, то точки начнут выстраиваться в какие-либо структуры (чаще полоски) и заполнение экрана будет не равномерным.
    Да, так и есть.


  13. #8
    Master
    Регистрация
    26.11.2013
    Адрес
    г. Новосибирск
    Сообщений
    533
    Благодарностей: 257
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

  14. #9
    Master
    Регистрация
    26.11.2013
    Адрес
    г. Новосибирск
    Сообщений
    533
    Благодарностей: 257
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

  15. #10
    Master Аватар для Oleg N. Cher
    Регистрация
    24.08.2007
    Адрес
    Днепропетровская обл.
    Сообщений
    754
    Благодарностей: 207
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

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

Страница 1 из 3 123 ПоследняяПоследняя

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

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

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

Похожие темы

  1. генератор случайных чисел на БК
    от litwr в разделе БК-0010/0011
    Ответов: 2
    Последнее: 20.12.2014, 18:20
  2. Генерация синуса
    от Hacker VBI в разделе Программирование
    Ответов: 154
    Последнее: 02.06.2014, 14:54
  3. Ответов: 41
    Последнее: 16.01.2013, 22:38
  4. Генерация лабиринтов
    от TomCaT в разделе Программирование
    Ответов: 90
    Последнее: 26.06.2012, 09:59

Ваши права

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