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

User Tag List

Страница 2 из 4 ПерваяПервая 1234 ПоследняяПоследняя
Показано с 11 по 20 из 32

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

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

    По умолчанию

    Кстати LFSR отличаются тем что генерируют псевдослучайную последовательность именно бит.
    Вот еще: https://en.wikipedia.org/wiki/Xorshift

    а кинь плиз еще форумов/блогов где advanced кодинг для спектрума/z80 обсуждают? (можно в ЛС)

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

    Цитата Сообщение от Bedazzle Посмотреть сообщение
    оба ответа "да".
    Разве что с поправкой, что 8 бит это 256
    Имелось в виду максимальная битовая репрезентация. MAXUINT для 8-bit

    График добавлен как предостережение тем, кто мог набежать и невдумчиво использовать вместо серьёзного генератора.
    Регистр в 8bit определяет очень короткую длину последовательности, через 256 чисел она зацикливается (если не раньше, бугага, надо вообще-то проверить). Поэтому не надо заполнять такие большие площади/графики такими короткими последовательностями, надо увеличить их длину, т.е. юзать регистровые пары.
    Alex Raider, Flash inc. 1992-1997 Новосибирск

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

    По умолчанию

    Oleg N. Cher, попробуй что-то вроде:
    Код:
    return (_Basic_RandBB()*(max-min+1) ) >> 16 + min;

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

    По умолчанию

    Думаешь, умножение и сдвиг будут эффективнее взятия по модулю?

    Господа, в итоге, видимо, задача сводится к эффективному вычислению модуля для байтов и слов. Если модуль байтового значения ещё можно как-то лопатить с помощью вычитание-пока-не-будет-заёма+сложение (хотя это оптимизация больше по размеру, чем по скорости), то для слов надо придумать что-то поинтереснее.

    Ещё интересно про использование регистра R в генераторах ПСЧ или СЧ. Как можно использовать этот регистр, не теряя равномерность диапазона (не сбиваясь на более частое выпадение одних значений над другими)?

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

    По умолчанию

    Цитата Сообщение от Oleg N. Cher Посмотреть сообщение
    Ещё интересно про использование регистра R в генераторах ПСЧ или СЧ. Как можно использовать этот регистр, не теряя равномерность диапазона (не сбиваясь на более частое выпадение одних значений над другими)?
    R это же самый обычный счетчик.
    Это работает только если пользователь создает какой-то случайное событие (нажатие клавиши клавиатуры, джойстика) в котором проходит некоторый случайный интервал времени от предыдущего взятия R и по этому событию читается R.

    Если полагаться на R в программном коде которому требуется сколько-то псевдослучайных значений (например в цикле) — ничего хорошего заведомо не выйдет.
    Последний раз редактировалось Raider; 11.01.2017 в 21:38.
    Alex Raider, Flash inc. 1992-1997 Новосибирск

  5. #15
    Master
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    880
    Благодарностей: 470
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Поддерживаю всё сказанное Raider. В качестве быстрого генератора случайных чисел лучше всего подойдет именно линейный конгруэнтный генератор. В книге "Numerical Recipes" я видел специально подобранные значения констант, которые позволяют несколько упростить вычисление. "Стандартный" генератор использует формулу:

    S := (a*S + c) mod m

    где S - состояние генератора, которое также возвращается в виде случайного числа после каждой итерации; a, c, m - константы.

    то упрощенный генератор позволяет исключить сложение:

    S := (a*S) mod m

    это требует тщательного подбора констант, в книге приведены значения a=7^5=16807; m=2^31-1 = 2147483647

    Для этого требуется 32-битная арифметика, но авторы книги категорически предостерегают от использования генераторов ПСЧ с 16-битным состоянием из-за слишком малого периода повторения.

    Линейный конгруэнтный генератор дает числа в диапазоне от 0 до m-1. Чтобы получить другой диапазон, необходимо провести дополнительное умножение на константу. Так, если 0<=x<m, то 0<x*(n/m)<n. Константа n/m будет в общем случае дробной, но дробные вычисления с фиксированной точкой в сущности ничем не отличаются от целочисленных.

  6. Эти 2 пользователя(ей) поблагодарили Barmaley_m за это полезное сообщение:
    Hacker VBI (12.01.2017), Raider (12.01.2017)

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

    По умолчанию

    Цитата Сообщение от Oleg N. Cher Посмотреть сообщение
    Думаешь, умножение и сдвиг будут эффективнее взятия по модулю?
    Может и эффективнее, если эффективнее оптимизируется, но важнее, что старшие биты более качественно случайны, чем младшие.

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

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

    По умолчанию

    А, вот оно что.

    А мог бы кто-нить, не особо углубляясь в теорию, набросать код ПСЧ для задаваемого диапазона? В принципе, меня устроит и генератор в диапазоне 0..255, к которому прикручено циклическое взятие по модулю. Мож где-то готовый есть хороший. А то вижу про 32-битную арифметику, и так ломает всё это кодить на асме. %)

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

    По умолчанию

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


  11. #19
    Veteran Аватар для drbars
    Регистрация
    02.03.2005
    Адрес
    Новосибирск
    Сообщений
    1,523
    Благодарностей: 645
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Точно

    Нажмите на изображение для увеличения. 

Название:	sshot000001.png 
Просмотров:	50 
Размер:	6.8 Кб 
ID:	59398

    Нажмите на изображение для увеличения. 

Название:	sshot000000.jpg 
Просмотров:	54 
Размер:	19.9 Кб 
ID:	59397

  12. #20
    Master
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    880
    Благодарностей: 470
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

    Современным наиболее широко применяемым, эффективным методом генерации случайных чисел является алгоритм Mersenne Twister. Если стандартные реализации ориентированы на сверхдлинный период повторения, то от ребят из Хиросимы существует реализация, ориентированная на малость потребляемых ресурсов. Она может подойти для Спектрума. Ее период повторения - 2^128-1, что намного лучше, чем практически реализуемые на Спектруме линейные конгруэнтные генераторы.

    Вот ссылка на проект: https://github.com/MersenneTwister-Lab/TinyMT

    Основные вычисления производятся в файле tinymt32.h, функции "tinymt32_next_state" и "tinymt32_temper". Всё остальное - вспомогательный код. Вот текст этих функций вместе с объявлением структуры состояния генератора:

    Код:
    struct TINYMT32_T {
        uint32_t status[4];
        uint32_t mat1;
        uint32_t mat2;
        uint32_t tmat;
    };
    
    inline static void tinymt32_next_state(tinymt32_t * random) {
        uint32_t x;
        uint32_t y;
    
        y = random->status[3];
        x = (random->status[0] & TINYMT32_MASK)
    	^ random->status[1]
    	^ random->status[2];
        x ^= (x << TINYMT32_SH0);
        y ^= (y >> TINYMT32_SH0) ^ x;
        random->status[0] = random->status[1];
        random->status[1] = random->status[2];
        random->status[2] = x ^ (y << TINYMT32_SH1);
        random->status[3] = y;
        random->status[1] ^= -((int32_t)(y & 1)) & random->mat1;
        random->status[2] ^= -((int32_t)(y & 1)) & random->mat2;
    }
    
    inline static uint32_t tinymt32_temper(tinymt32_t * random) {
        uint32_t t0, t1;
        t0 = random->status[3];
    #if defined(LINEARITY_CHECK)
        t1 = random->status[0]
    	^ (random->status[2] >> TINYMT32_SH8);
    #else
        t1 = random->status[0]
    	+ (random->status[2] >> TINYMT32_SH8);
    #endif
        t0 ^= t1;
        t0 ^= -((int32_t)(t1 & 1)) & random->tmat;
        return t0;
    }
    Copyright (c) 2011, 2013 Mutsuo Saito, Makoto Matsumoto,
    Hiroshima University and The University of Tokyo.
    All rights reserved.
    
    Redistribution and use in source and binary forms, with or without
    modification, are permitted provided that the following conditions are
    met:
    
        * Redistributions of source code must retain the above copyright
          notice, this list of conditions and the following disclaimer.
        * Redistributions in binary form must reproduce the above
          copyright notice, this list of conditions and the following
          disclaimer in the documentation and/or other materials provided
          with the distribution.
        * Neither the name of the Hiroshima University nor the names of
          its contributors may be used to endorse or promote products
          derived from this software without specific prior written
          permission.
    
    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    Обратите внимание, что не используются операции умножения и деления, а только сдвиги и логические операции. Так что есть хороший шанс, что все это быстро заработает на Z80.

    Лицензия - BSD

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

    Нашел еще один, еще более быстрый, простой и качественный генератор - Xorshift.

    Код вообще элементарный:
    Код:
    #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;
    }
    Никаких умножений и делений, только сдвиги и ксор. Период повторения - 2^32-1.

    Сгенерировал 10000 чисел - вроде выглядят случайно, последовательность не повторяется, спектр белый. Так что скорее всего метод работает. Но выглядит до ужаса просто!

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

    Навскидку код для Z80 (не тестировал)
    Код:
    ; The RNG state (32 bits), must be initialized to nonzero
    state:    db 1
                db 1
                db 1
                db 1
    ; Based on the current state of the RNG, updates the state to the next RNG. The result is saved into the state variable
    ; And also returned in DE:HL registers.
    rand:    ld hl,(state)
               ld de,(state+2)
               ld b,13
               call shl
               cal xorstate
               ld b,17
               call shr
               call xorstate
               ld b,5
               call shl
               jr xorstate
    
    ; Shift left a 32-bit number in DE:HL by B bits
    shl:    sla l
            rl h
            rl e
            rl d
            djnz shl
            ret
    
    ; Shift right an unsigned 32-bit number in DE:HL by B bits
    shr:    srl d
            rr e
            rr h
            rr l
            djnz shr
            ret
    
    ; Xors the current state (4 bytes) with DE:HL, returns result in both DE:HL and the state
    xorstate:
            ld bc,(state)
            ld a,l
            xor c
            ld l,a
            ld a,h
            xor b
            ld h,a
            ld (state),hl
            ld bc,(state+2)
            ld a,e
            xor c
            ld e,a
            ld a,d
            xor b
            ld d,a
            ld (state+2),de
            ret

  13. Эти 5 пользователя(ей) поблагодарили Barmaley_m за это полезное сообщение:
    creator (13.01.2017), hobot (18.01.2017), Oleg N. Cher (13.01.2017), SaNchez (14.01.2017), Titus (13.01.2017)

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

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

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

Эту тему просматривают: 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

Ваши права

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