Просмотр полной версии : Генерация случайных чисел в заданном диапазоне
Oleg N. Cher
10.01.2017, 13:51
Господа, не поможете ли решить такую задачку. Требуется переписать на асм функции генерации случ. чисел в заданном диапазоне - для байтов и для слов. Сейчас они написаны у меня частично на Си, что конечно не так эффективно.
/*--------------------------------- 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.
загляни в evo sdk, там есть rand16() на асме писанная.
Господа, не поможете ли решить такую задачку. Требуется переписать на асм функции генерации случ. чисел в заданном диапазоне - для байтов и для слов. Сейчас они написаны у меня частично на Си, что конечно не так эффективно.
Опять же, знаю, что много где в прессе и на форумах приводятся разные генераторы случ. чисел, но вопрос именно про в заданном диапазоне, так что поделитесь, пожалуйста, наработками. А можно смотреть на тему шире, не возражаю если вообще обсудим случайные, а не псевдослучайные числа и методы их получения на 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].
Следует учитывать что линейный конгруэнтный генеретор генерирует псевдослучайные числа, но не биты.
Поэтому биты в линейном конгруэнтном генераторе неравноценны. Наибольшая длина последовательности отражена в старших битах, поэтому использовать следует именно их, они наиболее "шумящие".
Bedazzle
10.01.2017, 18:09
Тогда на ассемблере Z80 код простейшего 8-битного датчика ПСЧ получается:
Пять тысяч значений ложатся так:
https://i.imgur.com/5eDHdQM.png
Можем ли определить, при компиляции, являются ли аргументы константами?
Oleg N. Cher
11.01.2017, 05:50
При компиляции - конечно можем. А вот внутри самой процедуры - нет.
Просто мало смысла зауживать процедуру только для диапазанов-констант. Хотя эффективность для известных значений конечно может быть выше, не спорю. AND 7 вместо MOD 8, например. =) Но такую оптимизацию компилятор сам делает.
Компилятор сам делает!? Тогда нет проблем!
Raider пишет что надо использовать старшие биты, так что ты свой остаток от деления замени на деление. А компилятор уже будет оптимизировать деление на константу, заменяя её сдвигами.
Пять тысяч значений ложатся так:
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_of_random_number_generators
в библиотеке такой более сложный генератор имеет смысл предлагать опционально.
Hacker VBI
11.01.2017, 12:52
Быстрые генераторы ПСЧ на основе LFSR (http://forum.tslabs.info/viewtopic.php?f=3&t=391&p=10061)
Bedazzle
11.01.2017, 15:41
1. Это с 8-ю битами (N=255) ?
2. Что это, как построен график. Шагали по оси абсцисс и отражали по оси ординат полученное ПСЧ?
оба ответа "да".
Разве что с поправкой, что 8 бит это 256 :)
Выше это был пример. Для практической реализации надо использовать минимум N=65535
График добавлен как предостережение тем, кто мог набежать и невдумчиво использовать вместо серьёзного генератора. :)
Быстрые генераторы ПСЧ на основе LFSR (http://forum.tslabs.info/viewtopic.php?f=3&t=391&p=10061)
Кстати LFSR отличаются тем что генерируют псевдослучайную последовательность именно бит.
Вот еще: https://en.wikipedia.org/wiki/Xorshift
а кинь плиз еще форумов/блогов где advanced кодинг для спектрума/z80 обсуждают? (можно в ЛС)
- - - Добавлено - - -
оба ответа "да".
Разве что с поправкой, что 8 бит это 256 :)
Имелось в виду максимальная битовая репрезентация. MAXUINT для 8-bit
График добавлен как предостережение тем, кто мог набежать и невдумчиво использовать вместо серьёзного генератора. :)
Регистр в 8bit определяет очень короткую длину последовательности, через 256 чисел она зацикливается (если не раньше, бугага, надо вообще-то проверить). Поэтому не надо заполнять такие большие площади/графики такими короткими последовательностями, надо увеличить их длину, т.е. юзать регистровые пары.
Oleg N. Cher, попробуй что-то вроде:
return (_Basic_RandBB()*(max-min+1) ) >> 16 + min;
Oleg N. Cher
11.01.2017, 19:32
Думаешь, умножение и сдвиг будут эффективнее взятия по модулю?
Господа, в итоге, видимо, задача сводится к эффективному вычислению модуля для байтов и слов. Если модуль байтового значения ещё можно как-то лопатить с помощью вычитание-пока-не-будет-заёма+сложение (хотя это оптимизация больше по размеру, чем по скорости), то для слов надо придумать что-то поинтереснее.
Ещё интересно про использование регистра R в генераторах ПСЧ или СЧ. Как можно использовать этот регистр, не теряя равномерность диапазона (не сбиваясь на более частое выпадение одних значений над другими)?
Ещё интересно про использование регистра R в генераторах ПСЧ или СЧ. Как можно использовать этот регистр, не теряя равномерность диапазона (не сбиваясь на более частое выпадение одних значений над другими)?
R это же самый обычный счетчик.
Это работает только если пользователь создает какой-то случайное событие (нажатие клавиши клавиатуры, джойстика) в котором проходит некоторый случайный интервал времени от предыдущего взятия R и по этому событию читается R.
Если полагаться на R в программном коде которому требуется сколько-то псевдослучайных значений (например в цикле) — ничего хорошего заведомо не выйдет.
Barmaley_m
12.01.2017, 01:00
Поддерживаю всё сказанное 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 будет в общем случае дробной, но дробные вычисления с фиксированной точкой в сущности ничем не отличаются от целочисленных.
Думаешь, умножение и сдвиг будут эффективнее взятия по модулю?
Может и эффективнее, если эффективнее оптимизируется, но важнее, что старшие биты более качественно случайны, чем младшие.
Oleg N. Cher
12.01.2017, 09:26
А, вот оно что.
А мог бы кто-нить, не особо углубляясь в теорию, набросать код ПСЧ для задаваемого диапазона? В принципе, меня устроит и генератор в диапазоне 0..255, к которому прикручено циклическое взятие по модулю. Мож где-то готовый есть хороший. А то вижу про 32-битную арифметику, и так ломает всё это кодить на асме. %)
Bedazzle
12.01.2017, 09:35
"качество" ПСЧ-последовательности можно простейшим способом анализировать путем взятия двух соседних отсчетов и отображения их по X,Y.
Если между X и Y существует корреляция, то точки начнут выстраиваться в какие-либо структуры (чаще полоски) и заполнение экрана будет не равномерным.
Да, так и есть.
https://i.imgur.com/4MC1tRt.png
Barmaley_m
13.01.2017, 02:18
Я тут провел небольшое исследование темы и обнаружил, что наука шагнула вперед за последние годы, так что линейный конгруэнтный генератор с его необходимостью деления отходит на второй план.
Современным наиболее широко применяемым, эффективным методом генерации случайных чисел является алгоритм 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 (https://en.wikipedia.org/wiki/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
Я тут провел небольшое исследование темы и обнаружил, что наука шагнула вперед за последние годы, так что линейный конгруэнтный генератор с его необходимостью деления отходит на второй план.
В ЛКГ нет деления, это что-то попутано.
Есть умножение, заменяемое сдвигами. Код был приведен выше.
Ссылка на Xorshift была выше, но его практическая реализация через произвольные сдвиги медленнее чем ЛКГ.
Xorshift это подвид LFSR, ссылка на эффективный LFSR была выше.
«Вихрь Мерсенна» как и другие, скажем, криптостойкие генераторы ПСЧ для для 8-биток с int = 28 и 65536-ю адресами использовать бессмысленно. В компьютере меньше доступной памяти чем период примитивного ПСЧ c 16-битным seed, а в случае "Вихря Мерсенна" как исчерпать хотя бы ничтожную часть его периода?
Наколхозить любой современный криптостойкий генератор, симулируя int64-арифметику и 1000-байтные массивы возможно.
Но в чем смысл этого, бессмысленный и беспощадный?
Barmaley_m
14.01.2017, 01:26
В ЛКГ нет деления, это что-то попутано.
В ЛКГ есть операция взятия остатка от деления, что по сложности то же самое, что деление. Кстати, я обнаружил ошибку в твоих рассуждениях на тему того, что умножение или сложение по модулю 255 или 65535 эквивалентно отбрасыванию старших бит. Это не так. Отбрасывание старших бит дает остаток от деления на 2^N, а надо делить на 2^N-1, что не то же самое.
Так, сохранение младших 8 бит даст остаток от деления на 256, но делить-то надо на 255.
Есть способы получать остаток от деления на 2^N-1 без применения полной процедуры деления. Но для этого нельзя отбрасывать старшие биты просто так. Их надо прибавлять к содержимому младших. Такой подход реализован при вычислении контрольных сумм Флетчера, где используется сложение по модулю 255, или же контрольных сумм TCP/IP, где используется сложение по модулю 65535. Но в твоем коде этот подход не реализован, поэтому код неправильный. Вероятно, твои генераторы не будут давать максимальный период повторения.
Xorshift это подвид LFSR, ссылка на эффективный LFSR была выше.
Не совсем. LFSR дает поток случайных бит, но не чисел. Эти биты еще надо как-то объединять в числа, на практике простые LFSR для получения многобитных чисел не используются. Вместо них используются ЛКГ, GFSR или MT. Ну и вот Xorshift тоже - он генерирует числа, а не просто биты, чем и полезен. В противном случае можно было бы пользоваться LFSR, его реализация проще, в ней используются сдвиги только на 1 бит.
В компьютере меньше доступной памяти чем период примитивного ПСЧ c 16-битным seed, а в случае "Вихря Мерсенна" как исчерпать хотя бы ничтожную часть его периода?
Ты недооцениваешь важность иметь длинный период повторения. Случайные числа не только сохраняют в память, их еще используют для генерации игрового процесса, лабиринтов, вычислений методом Монте-Карло и др. Бывают применения, в которых "потребление" нескольких тысяч случайных чисел - обычное дело. Период 16-битного генератора исчерпается за несколько вызовов процедуры, его использующей. И тогда в игре появятся повторяющиеся лабиринты и прочие гадости, а вычисления методом Монте-Карло дадут неверный результат.
Я думаю, что применительно к Спектруму достаточная длина последовательности генератора должна выбираться из следующих соображений:
1) Время работы компьютера, в течение которого можно сгенерировать полный период последовательности. Оно должно составлять по меньшей мере несколько суток, тогда как 16-битная последовательность может исчерпаться за секунды или минуты.
2) Варианты старта последовательности. Дело в том, что в генераторах ПСЧ последовательность всегда одинаковая, и случайность достигается за счет того, что генерация стартует из разного ее места. Если за один заход требуется, скажем, 1000 случайных чисел - то при 16-битном генераторе будет всего 65 вариантов различных неповторяющихся случайных потоков. Мало.
Думаю, для Спектрума необходимо иметь как минимум 24, а лучше 32 бита состояния генератора ПСЧ.
Alcoholics Anonymous
14.01.2017, 02:43
В ЛКГ есть операция взятия остатка от деления, что по сложности то же самое, что деление. Кстати, я обнаружил ошибку в твоих рассуждениях на тему того, что умножение или сложение по модулю 255 или 65535 эквивалентно отбрасыванию старших бит. Это не так. Отбрасывание старших бит дает остаток от деления на 2^N, а надо делить на 2^N-1, что не то же самое.
Так, сохранение младших 8 бит даст остаток от деления на 256, но делить-то надо на 255.
Да короткая подпрограммой LCG показано не является правильным.
Есть некоторые очень высокого качества генераторы случайных чисел, которые были написаны для z80 в WOS.
Первым из них является 10 ^ 20 период CMWC генератор, который возвращает 8-битовых случайных чисел:
http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_DEVELOPMENT/stdlib/z80/random/asm_random_uniform_cmwc_8.asm?content-type=text%2Fplain
Как вы можете видеть, что это очень быстро и коротким. Ссылка на исходный поток в WOS можно найти в исходном коде.
Тот, который мы используем в качестве генератора по умолчанию для rand() в z88dk является генератором Marsaglia XORshift:
http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_DEVELOPMENT/stdlib/z80/random/asm_random_uniform_xor_32.asm?content-type=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/viewvc/z88dk/z88dk/libsrc/_DEVELOPMENT/stdlib/z80/random/asm_random_uniform_cmwc_8.asm?content-type=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/viewvc/z88dk/z88dk/libsrc/_DEVELOPMENT/stdlib/z80/random/asm_random_uniform_xor_32.asm?content-type=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.
В ЛКГ есть операция взятия остатка от деления, что по сложности то же самое, что деление. Кстати, я обнаружил ошибку в твоих рассуждениях на тему того, что умножение или сложение по модулю 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_congruential_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.
xor b
ld b,a
srl a
как насчет rra? )
Имеем 16-битный xorshift. Если рассматривать его выход как уникальные 16-битные числа, длина уникальной последовательности 16-битных word'ов получается 65535, все хорошо. Но если берем из его 16-бит один байт, то в зависимости от констант a,b,c и в зависимости от того какой байт мы берем, старший или младший - длина последовательности может получиться меньше. Думается это потому что внутри seed-переменной xorshift'а разные биты "вращаются" с разными циклами.
Так что не всё просто, и всегда надо тестировать на практике.
Как я догадываюсь, чтобы получить один байт на выходе, байты xorshift'а надо складывать по xor.
xor b
ld b,a
srl a
как насчет rra? )
Во-во, именно так!
Я вчера с похмела вообще забыл какую-либо оптимизацию провести, как экспериментировал так и шурнул на форум. :-)
Barmaley_m
18.01.2017, 01:03
Это ложно.
Число берется равное 2n (256, 65536) и конечно же берется остаток от деления на него. Что в случае регистров длиной 2n дается даром.
В сообщении №3 ты писал:
Его формула СледЧисл = (A * Число + B) MOD N
выражение (Число * A) MOD N означает остаток от деления, но если умножение и сложение реализуется с возможным переполнением ("заворотом"), то функция MOD N достигается даром. То есть если регистры восьмибитные, то N = 255, если 16-битные то N = 65535 что как раз и отвечает заданным требованиям.
Числа 255 и 65535 имеют вид 2N-1, и остаток от деления на них "даром" не дается. Возможно, ты имел в виду 256 и 65536. Но это ошибка в твоем сообщении, а не моем. Зачем в таком случае ты взялся меня с пафосом опровергать?
Да, действительно, бывают и ЛКГ по модулю 2n. Но это можно было просто пояснить, особенно учитывая, что это твое сообщение было причиной возникновения данной ситуации.
Я пишу о реализации ЛКГ , которые я неоднократно видел в реальном коде своими глазами. Все настоящие ЛКГ (а не то, как это внезапно нафантазировано) выбирают m в формуле mod m равное степени двойки 2m. И имеют при этом максимальный период равный 2m.
По твоей же ссылке в Википедии приводятся примеры ЛКГ с модулем, не равным степени двойки. Один из них используется в glibc. Они что, ненастоящие? Нафантазированные?
Не исключено, что работа по модулю вида 2N-1 дает какие-то преимущества, оправдывающие повышение сложности генератора. Иначе никто в здравом уме не стал бы так делать.
#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-е число ) Как это победить - я не знаю увы.
Числа 255 и 65535 имеют вид 2N-1, и остаток от деления на них "даром" не дается. Возможно, ты имел в виду 256 и 65536. Но это ошибка в твоем сообщении, а не моем. Зачем в таком случае ты взялся меня с пафосом опровергать?
Это просто нотация
Да, действительно, бывают и ЛКГ по модулю 2n. Но это можно было просто пояснить, особенно учитывая, что это твое сообщение было причиной возникновения данной ситуации.
Они не "бывают", а все так построены.
По твоей же ссылке в Википедии приводятся примеры ЛКГ с модулем, не равным степени двойки. Один из них используется в glibc. Они что, ненастоящие? Нафантазированные?
Неа, просто нотация: https://github.com/lattera/glibc/blob/master/stdlib/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 :-)
А как такое переписать на МАКРО-11, что за оператор ^= и <<
Можно как-то в виде готовой функции оформить для не программера вроде меня, что бы протестировать и
возможно использовать? (использовать в программах для RT-11 разумеется, не для спектрума!) Очень желательно ПАСКАЛЬ - главное что бы не Си !!!
^=
произвести xor и присвоить, x^= 5 короткая запись x = x ^ 5; в паскале это xor
<<
сдвиг влево на сколько-то бит. в паскале shl
>>
сдвиг вправо на сколько-то бит. в паскале shr
Глядим сюда (http://wiki.freepascal.org/Pascal_for_C_users)
Компиляй и запускай здесь: 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.
кстати, о птичках. Непонятно, почему JP M,RANDOM3 ?
PROGRAM PITSTOP
from Your Sinclair #20 (August 1987)
If you want to know more about programming, take a Pitstop right here in
our new program section! Each month it'll be bursting with routines from
the top programmers, and seething with all your games and utility
programs.
Yes, it's all true! In this rinky premiere edition of Program Pitstop,
we've got Jon Ritman of Batman and Head Over Heels fame, Dominic
Robinson who wrote Zynaps and Uridium and Tim Follin, musician extra-
ordinaire, who did the music for Agent X and Sentinel. All of them are
here this month sharing their darkest programming secrets, for you to
use free in your own programs! If that isn't enough for you, we've also
got wacky David McCandless and his super Gauntlet Mapper program, plus
an original and useful graphic utility from Khalid Jamil, called Peeker.
Pitstop is going to be the indispensable programmers guide, featuring
the best Spectrum programmers plus yourselves in the biggest pooling of
programming talent since the Spectrum was invented. What we need are
contributions from you. Is there a routine that does something fab that
you used in your last game? Provided it's quite short, you're in with a
chance to be featured in Program Pitstop. If you're a professional
programmer, then please write in with a mugshot and some details. If
you're just a talented amateur, then let the rest of the world see how
brill you can be - who knows, you could find yourself up there with the
big boys in no time!
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
PEEKER
by Khalid Jamil (?)
from Your Sinclair 20 (Aug.1987) - "Program Pitstop"
[files PEEKER.*]
[This was later claimed to have been lifted from a Spanish magazine ]
[ - Microhobby #78 - and to have been written by Francisco Alexandre]
[ - see letter below. JimG]
Now then, have you ever seen graphics in a game that you really liked
and thought, "Hmm, with a little bit of tickling that would be just
right for my new game!" Well, now you can! Khalid Jamil has come up with
a very tidy solution, in the form of Peeker, an amazingly short program
which allows you to look at a game's graphics or sprites to see how
they're made up.
Method
Load Peeker with LOAD "". You'll be presented with a menu screen
containing the graphics window, a small bar containing the start and end
addresses of the program you're looking at, a short box containing the
memory location presently being examined, and a menu box. The menu box
contains the words PEEK, COLOR, POINT, LOAD, and SAVE. To access each of
these options, press '6', then use 'Q' and 'A' to highlight the option,
then finally press '0' (zero) to select it. To escape from an option
press '6' again.
Basic Program
Here's the main program. Type it in and save it to tape as SAVE "PEEKER"
LINE 1. It'll load up the code blocks and auto-run.
PEEK - After loading the game, this option allows you to actually look
at the graphics in memory. Scan forwards and backwards through memory
with 'Q' and 'A'. If it looks crunched or just plain garbage, you can
expand the data sideways to make it more readable with 'O' and 'P'. If
the data seems to be off to one side, like the head of the character is
on one side and the body on the other, you can scroll the data around
with keys '5' and '8'.
COLOR - Inverses the colour of the display window.
POINT - This function points to the location in memory where the program
is stored and how much there is of it. [Toggle between the high and low
locations with 'O' and 'P'; return to the menu with 'A'. JimG]
LOAD - Allows you to load in the main machine code block of the game you
wish to inspect. If the game is too large to be resident in memory at
the same time as Peeker; it won't crash, but will just stop loading.
SAVE - Enables you to save the graphics data.
Hex Loader
[I didn't use the hex loader printed in the mag, so I've not]
[included the comments about it here. JimG]
Hex Dump 1
This is the first bit of code, start address = 23296, and the length =
143. Save as SAVE "PEEK CODE1" CODE 23296,143 after the Basic program on
your tape.
Hex Dump 2
This is the second bit of code [UDGs, actually. JimG], start address =
27936, and the length = 65. Save as SAVE "PEEK CODE2" CODE 27936,65
after the first code block.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
[letter from Your Sinclair 23 (Nov.1987)]
VIVA L'ESPANA
It's my duty with Francisco Alexandre to tell you the truth. The Peeker,
a graphic utility that was published in the last issue of your mag, was
first published in a Spanish magazine - Microhobby, no. 78 - and is by
Francisco Alexandre. Khalid Jamil is telling porkies. Enclosed are three
photocopies of the original listings of the program which was, and still
is, "El Espia".
Sorry about my English, but I think it's better than your Portuguese.
Paulo J Lucas Martins
Viseu, Portugal
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
GAUNTLET MAPPER
by David McCandless
from Your Sinclair 20 (Aug.1987) - "Program Pitstop"
[files GAUNTMAP.*]
Megawow! If you're a Gauntlet fan, then this is the utility for you.
Having slaved along through Gauntlet and it's Deeper Dungeons, it's real
nice to be able to get a map of the dam thing. Half the time spent
playing the game seems to be flogging down dead end passages, only to
turn around and see a Death on your tail! But don't get in a tizzy, 'cos
help is on hand! David McCandless has come up with this wacky little
program which actually maps each level for you and prints it out on a
printer!
Included in the program is a headerless save program, residing at
address 31011. To use this simply RANDOMIZE USR 31011 and it'll save the
Mapper code as a headerless file. There's no "Start Tape And Press Any
Key" message, so the tape has to be running before you press ENTER. (For
the technically minded, its a natty little routine you might want to use
in your own programs. It goes like this: DD 21 B0 77 11 [74 01] 3E FF CD
C2 04 C9, where the [bracketed] figures are the length, lo and hi bytes,
in that order of course.)
Method
To use Mapper, simply connect your Spectrum to a printer, and load
Mapper1 with LOAD "". Stop the tape and load side 1 of your Gauntlet
tape as normal. Once loaded the screen will go blank. Stop the Gauntlet
tape and insert your Mapper tape again. Press play and the headerless
file will load in. Now the game will continue as normal, but you'll
notice some of the character set has been corrupted. Don't worry, this
is normal 'cos the Mapper code occupies this area. Now play the game as
normal but Pressing 'T' will compress and print the current screen to
your printer. Pressing 'R' will return you to the game, but if you
haven't got enough time to play, pressing 'Y' will return you to the
game, but with all the walls turned into exits for a quick getaway.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
STAR TIP 1
by Dominic Robinson
from Your Sinclair #20 (Aug.1987) - "Program Pitstop"
[files STARTIP1.*]
Ever looked at the flashy rainbow
coloured lettering on Hewson games and
thought "Corky! I wish I could do that
in my games!" Well now you can, because
those awfully nice Hewson people have
allowed Dominic Robinson, the
exceedingly talented chap behind the
Spectrum conversion of Uridium, to share
it with you. His programming life at
Hewson began when he worked on the team
that built Pyracurse, and after Uridium
and the game he's just completed,
Zynaps, he looks, at the tender age of
21, to be one of the top Spectrum
programmers of 1987.
The Rainbow Effects Processor is a very
tidy group of routines, used in both
Zynaps and Uridium to produce the
amazing rainbow 3D effects on the title
and hi-score screens. "In its simplest
form, the Rainbow Processor can be used
to increase the Spectrum's normal colour
resolution, giving you a different
colour on each pixel line, in a band
twenty characters wide in the centre of
the screen. With a little more work, the
bars can be animated to produce some
very un-Spectrum like effects. The
Rainbow Processor runs in Interrupt Mode
2, to keep it synchronised with the
generation of the TV picture, so that
different attribute values are fetched
for each pixel line."
Method
To use the Rainbow Processor, you must
set up a block of memory containing the
colour for each pixel line of your
display. This block can be 256 bytes
long, although at most 192 will be used
at one time, and it must not cross a
page boundary. Starting at a block at an
address which is a multiple of 256 will
ensure that this condition is met. For
example: 193*256-49408, which is
conveniently placed just above the end
of the code. Next POKE the address of
your data into 49189 and 49190; call the
routine at 49153 to initialise the
interrupts, then POKE 49188 with the
number of pixel lines you want
displayed. This value should be a
multiple of 8 for best results. Any
value outside of the range 1 to 192 will
switch off the rainbow effect until
another value is used. The deeper the
display you use, the less processor time
will be available for Basic or any other
code you have running. For this reason
the rainbow effect can only really be
used for title screens and special
effects.
Hex Dump
Feed this, eight bytes at a time, into
the Hex Loader from Peeker, and save it
as SAVE "democode" CODE 49153,145.
Demo Program
This small Basic program demonstrates
the facilities of the Rainbow Code. Save
it as SAVE "RAINBOW" LINE 2000. When you
run it, it will load and activate the
machine code, upon which the screen will
go black for a couple of minutes while
the demo picture is drawn. So be
patient; the result is stunning.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
STAR TIP 2
by Tim Follin
from Your Sinclair #20 (Aug.1987) - "Program Pitstop"
[files STARTIP2.*]
This amazing three-channel sound routine
is the product of the versatile musical
talent of Tim Follin, the man behind the
tunes on Mastertronic's Agent X, and
Firebird's spectacular Sentinel. If you
thought these were the corkiest sonics
you've heard on any Speccy game, you'll
be thrilled to atoms over this chunk of
machine code music!
Tim is currently working on a brilliant
new routine for 6-channel sound with
chorus bass, 128K snare drum, echo on /
off / delay time, portamento, and full
ADSR! This fabby routine is to appear on
a brand new game called Red 5, by Peter
Gough, so keep a look out for it in the
near future.
Method
The code begins at 40000 and is a mere
1340 bytes long. First CLEAR 39999, then
LOAD "" CODE. To hear the tune, simply
RANDOMIZE USR 40000. Any key breaks.
Note: Tim has asked us to say that
although he doesn't mind you using the
tune in your own programs, he does
retain copyright on it, so it can't be
used for commercial games.
Hex Dump
Type the following hex dump into the hex
loader and save as SAVE "TUNE" CODE
40000,1340. Good luck!
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
STAR TIP 3 (Random Number Generator)
by Jon Ritman
from Your Sinclair #20 (Aug.1987)
[files STARTIP3.*]
If you liked Head Over Heels and Batman, then you'll know that Jon Ritman,
along with his partner Bernie Drummond, knows a thing or two about program-
ming brilliant games. One of the most important things in a good arcade
adventure, or so it seems, is a random number generator.
"This is the 32-bit random number generator routine I used in Batman and
Head Over Heels. The routine is quite fast and returns a reasonable random
number. This version returns with HL holding a 16-bit random number. However,
if you need all 32 bits, simply add the instruction LD DE,(SEED+2) just
before the RET at the end. The 32-bit seed may be changed to any value of
your choice."
So here it is, for all of you assembly junkies, the listing, which can be
located anywhere suitable in memory. For those of you that haven't got an
assembler, there's also a hex dump of the code for you to load in via a
suitable hex loader. For convenience we've assembled it to 30000 (7530 hex),
and in case you're wondering, its length is 45 bytes. [It's actually 46
bytes. JimG]
SEED: DB "Jon!"
RANDOM: LD HL,(SEED+2)
LD D,L
ADD HL,HL
ADD HL,HL
LD C,H
LD HL,(SEED)
LD B,H
RL B
LD E,H
RL E
RL D
ADD HL,BC
LD (SEED),HL
LD HL,(SEED+2)
ADC HL,DE
RES 7,H
LD (SEED+2),HL
JP M,RANDOM3
LD HL,SEED
RANDOM2: INC (HL)
INC HL
JR Z,RANDOM2
RANDOM3: LD HL,(SEED)
RET
30000:2ADD005529294C2A=548
30008:DB0044CB105CCB13=820
30016:CB120922DB002ADD=746
30024:00ED5ACBBC22DD00=973
30032:FA5A7521DB003423=796
30040:28FC2ADB00C90000=754
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
--
Another Fine Product transcribed by:
Jim Grimwood, Weardale, England (http://www.users.globalnet.co.uk/~jimg/)
--
Тут есть пару примеров...
http://zx-pk.ru/threads/9031-etyudy.html?p=577862#post577862
Powered by vBulletin® Version 4.2.5 Copyright © 2026 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot