|
Читатель - читателю - генераторы псевдослучайных последовательностей.
|
ЧИТАТЕЛЬ-ЧИТАТЕЛЮ
ГЕНЕРАТОРЫ ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ © Колотов Сергей, г. Шадринск 1996.
В ZX РЕВЮ 95/6 я с огромным интересом прочитал статью "Быстродействующий генератор псевдослучайных чисел". Получение случайных (точнее псевдослучайных) чисел на компьютере - довольно увлекательная задачка. Примеры её решения неоднократно публиковались и раньше.
Метод, предложенный Сергеем Астровым довольно-таки интересен и поучителен, но с новым алгоритмом появились и новые ограничения в использовании (невозможность получения нулевого значения, периодичность). Напоминаю, по алгоритму в регистре сдвига HL ксорятся биты, отмеченные на схеме, затем регистр сдвигается от младших номеров битов к старшим, а в
нулевой бит записывается результат ксорки.
Н L 
Чтобы "перексорить" эти биты, достаточно "вращать" аккумулятор влево командой RLCA (в сторону возрастания номеров битов), выполняя команду XOR в нужный момент (один раз с регистром L и три раза с регистром H). Неважно, что портятся остальные биты аккумулятора, ведь нас интересует только один. Последней командой RLCA нужный нам бит попадает в флаг переноса и затем командой ADC HL,HL попадет в нулевой бит регистровой пары HL после ее сдвига влево.
Новая процедура занимает всего 25 байт. Ее листинг:
RND 31
HL,(SEED) A, H L
NZ,NOZERO L
A, L H
LD
LD
OR
JR
INC
LD
RLCA XOR
RLCA
RLCA
XOR
RLCA
XOR
RLCA
ADC
LD
RET
DEFW
Внимательно изучив работу программы для тестирования различных процедур RND (ZX-РЕВЮ 95/4, с.49), я предлагаю ввести некоторые коррективы. Так, осмысливать процедуру на предмет полного заполнения экрана "на глазок" - топорный приём. Компьютер сам может и должен за этим проследить! И ещё одно замечание. Для заполнения экрана нужно брать не один только младший байт из SEED, но и не забывать о старшем. Мало ли как он себя ведёт (вдруг не псевдослучайно). Вот новый листинг программы:
|
DIFTST |
RES |
5,(IY+1) |
|
LPDT1 |
LD |
HL,#4000 |
|
|
LD |
B, L |
|
LPDT2 |
PUSH |
HL |
|
|
PUSH |
BC |
|
|
CALL |
RND |
|
|
POP |
BC |
|
|
POP |
HL |
|
|
LD |
A,(SEED) |
|
|
OR |
(HL) |
|
|
LD |
(HL),A |
|
|
INC |
A |
|
|
JR |
Z,GODT1 |
|
|
LD |
B, H |
|
GODT1 |
INC |
HL |
|
|
LD |
A,(SEED+1) |
|
|
OR |
(HL) |
|
|
LD |
(HL),A |
|
|
INC |
A |
|
|
JR |
Z,GODT2 |
|
|
LD |
B, H |
|
GODT2 |
INC |
HL |
|
|
BIT |
5,(IY+1) |
|
|
RET |
NZ |
|
|
LD |
A, H |
|
|
CP |
#58 |
|
|
JR |
C,LPDT2 |
|
|
LD |
A, B |
|
|
OR |
A |
|
|
JR |
NZ,LPDT1 |
|
|
RET |
|
Вообще, хочу заметить, что судить о скорости выполнения RND-процедур на таких тестах можно лишь очень приблизительно. Возможно даже, что большая часть времени уйдет на выполнение самого теста и на прерывания (если тестируемая процедура ну очень маленькая). Такие тесты лучше подходят для изучения разброса случайных чисел, их повторяемости. По этому поводу у меня появились некоторые мыслишки и в результате получился новый SEED TEST, который я вам и предлагаю:
DI
LD
LD
LD
INC
LD
LD
INC
HL,#FDFD A, H
(HL),#C3 HL
DE,MYINT (HL),E HL
FILL
LPST1
LPST2
MYINT
COUNT TSTIME
Вначале процедура настраивается на работу в режиме IM2 - подсчёт числа прерываний за время работы теста. Затем происходит выполнение теста вхолостую - необходимо подсчитать время выполнения самого себя. При этом вместо тестируемой RND-процедуры вызывается подпрограмма по адресу 124. В ПЗУ по этому адресу стоит RET, что успешно и выполняется. После этого тест нормально отрабатывается и вычитает из полученного значения время своей работы. Результат вычислений помещается в регистровую пару BC и, следовательно, его можно узнать из БЕЙСИКа командой PRINT USR ...
|
LD |
(HL),D |
|
INC |
HL |
|
LD |
(HL),A |
|
INC |
L |
|
JR |
NZ,FILL |
|
INC |
H |
|
LD |
(HL),A |
|
INC |
A |
|
LD |
I,A |
|
IM |
2 |
|
LD |
HL, #FFFF |
|
LD |
(COUNT) , HL |
|
EI |
|
|
HALT |
|
|
PUSH |
HL |
|
CALL |
124 |
|
POP |
HL |
|
DEC |
HL |
|
LD |
A, L |
|
OR |
H |
|
JR |
NZ,LPST1 |
|
LD |
HL,(COUNT) |
|
HALT |
|
|
LD |
(TSTIME),HL |
|
LD |
HL,#FFFF |
|
LD |
(COUNT) , HL |
|
HALT |
|
|
PUSH |
HL |
|
CALL |
RND |
|
POP |
HL |
|
DEC |
HL |
|
LD |
A, L |
|
OR |
H |
|
JR |
NZ,LPST2 |
|
DI |
|
|
LD |
A, #3F |
|
LD |
I,A |
|
IM |
1 |
|
LD |
HL,(COUNT) |
|
LD |
BC,(TSTIME) |
|
AND |
A |
|
SBC |
HL, BC |
|
LD |
B, H |
|
LD |
C, L |
|
EI |
|
|
RET |
|
|
PUSH |
HL |
|
LD |
HL,(COUNT) |
|
INC |
HL |
|
LD |
(COUNT) , HL |
|
POP |
HL |
|
EI |
|
|
RET |
|
|
DEFW |
0 |
|
DEFW |
0 |
Мною было проведено исследование скорости работы различных RND-процедур на двух компьютерах. Были получены следующие значения:_
|
Процедуры RND |
КОМПЬ |
ЮТЕРЫ |
|
КВОРУМ-128 |
СПЕКТР |
|
RND: №6,1994 |
425 |
1851 |
|
RND 2: №4,1995 |
223 |
948 |
|
RND 3: №6,1995 |
123 |
550 |
|
RND 31: |
92 |
410 |
|
RND 4: |
82 |
411 |
Объяснить такой разброс для двух компьютеров не могу, выводы же можете делать сами.
Присмотревшись к таблице повнимательнее, Вы спросите: а что за RND_4 присутствует здесь, как ни в чём не бывало? Отвечаю: это самая маленькая на данный момент RND-процедура из написанных мною. Она занимает всего 20 байт (2 байта SEED, я думаю, давно пора перестать считать). В своей работе процедура использует регистр регенерации R и данные из ПЗУ - они хорошо подходят для этой цели. В результате, процедура работает очень быстро и выдаёт довольно-таки случайное распределение чисел. Вот её листинг:
|
LD |
HL,(SEED) |
|
LD |
A, R |
|
XOR |
H |
|
LD |
E, A |
|
AND |
%00111111 |
|
LD |
D, A |
|
LD |
A, (DE) |
|
XOR |
L |
|
LD |
H, A |
|
XOR |
E |
|
RRCA |
|
|
LD |
L, A |
|
LD |
(SEED),HL |
|
RET |
|
Работая на ассемблере долгое время, удивляешься - какое количество тайников и секретов содержит этот простенький с виду процессор Z80. Так, совсем недавно, я обнаружил две очень интересные команды, одна из которых заполняет содержимым флага переноса аккумулятор, а вторая - регистровую пару HL. А ведь эти команды всё время были на виду. Лишь запись их мнемоник была не очень удобочитаема. Итак, это команды: SBC A,A (#9F) и SBC HL,HL (#ED #62). Вот как они работают:
•S если флаг C включен (равен 1), то при выполнении SBC A,A в аккумуляторе будет #FF (аналогично, команда SBC HL,HL занесёт в регистровую пару HL число #FFFF) •f если флаг C выключен (равен 0), то получим A=0 (HL=0). Приведу один интересный пример использования команды SBC A,A: В программах часто можно встретить такую конструкцию: LD A, 0
JR NC,GO1
LD A,...
GO1 ...
Но ведь гораздо проще написать:
SBC A, A AND .
Преимущества налицо.
Также, я хотел бы высказать своё мнение насчёт использования шестнадцатеричной системы счисления. Совсем недавно я считал HEX-систему "страшилкой" и все мои программы писал только в десятичной системе. Если где-нибудь встречались значки H,#, то я ужасно ругался и пересчитывал, пересчитывал, пересчитывал...
Но времена меняются. Долгие копания в чужих программах, работа с дизассемблером, да и что греха таить - ваши публикации, сломили кодерскую душу, и теперь о пользе HEX-системы
25
меня можно не вразумлять. Я уж не говорю о том, что при работе с экраном и TR-DOS использование HEX-системы просто необходимо!
|