ZX-Ревю 1996 №4-5 1996 г.

Читатель - читателю - получение случайных чисел.


ПОЛУЧЕНИЕ СЛУЧАЙНЫХ ЧИСЕЛ

© А. Астафьев, г. Новосибирск

При решении многих прикладных задач возникает необходимость получения случайных чисел. С их помощью выполняются решения задач вычислительного анализа, когда получить точное решение трудно, и можно воспользоваться лишь методом приближенных вычислений (Метод Монте-Карло). Случайные числа используются при исследовании устойчивости программ в неожиданных ситуациях. Они, также, требуются во множестве моделирующих, обучающих, игровых и демонстрационных программ, не говоря уж о применении в сфере машинной графики - как видно спектр применения генераторов случайных чисел очень широк.

На первых порах вычислительной техники задачу получения случайных последовательностей чисел пытались решить, используя физические явления: электронный шум, радиоактивный распад и т.д. В иных случаях строили в памяти ЭВМ готовые таблицы случайных чисел. Но все это было неудачным. Таблицы быстро исчерпывались, а физические явления повторить было нельзя. Возникла парадоксальная ситуация - необходимо было получать случайные последовательности, но в то же время, чтобы можно было получать такие же последовательности еще раз!

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

В настоящее время известно множество алгоритмов получения псевдослучайных чисел (ПСЧ). Между собой они различаются способами формирования следующего ПСЧ из предыдущего - и отсюда разными свойствами ПСЧ - последовательностей. Основными параметрами генераторов (или как их еще называют - датчиков) ПСЧ являются следующие:

1. Период повторения последовательности.

2. Равномерность последователь

3. Диапазон чисел (масштаб).

4. Разброс последовательности значений чисел.

Период повторения задаётся обычно как степень двойки, и, как правило, целесообразно выбирать его не больше, чем количество обращений к алгоритму за обозримый (требуемый) промежуток времени. На практике период 2 в 16-й вполне достаточен.

Под равномерностью понимается то, что вероятность возможного числа N-последовательности в ее начале, близка к вероятности появления N в ее конце. Говоря проще, мы можем иметь ПСЧ последовательность из 10000 чисел и в первых 9500 числах никогда не встретить Число 13. Если генерируются числа от 0 до 255, то это довольно плохо.

С масштабом все просто - масштаб можно изменить простейшими математическими преобразованиями.

Разброс значений имеет довольно большое значение - у хорошего генератора ПСЧ он должен быть как можно более хаотичен. Вообще, говоря правильными терминами, хороший генератор имеет равномерный спектр последовательности, и сам спектр желательно иметь похожим на спектр шумового сигнала.

Исследовать спектр получаемой с помощью генератор? ПСЧ - последовательности я предлагаю так: вызвать генератор ПСЧ, и на каждом вызове присваивать сначала X, а затем Y-координате точки значения генератора. Попробуйте такой эксперимент: 10 BORDER 0: INK 7: PAPER 0: CIS 2 0 RANDOMIZE 1 30 LET X-255*RND 4 0 LETY-175*RND 50 PLOT X,Y: GO TO 30

Запустите все это и подождите минут пять. Заметили несовершенство этой программки? Точки норовят выстраиваться вовсе не случайно, а именно вертикальными столбцами. А теперь попробуйте ввести следующую строку: 35 LET Z-RND

и еще раз запустите программу. Заметили разницу? Да, из-за холостого вызова генератора в 35 строке эффект уже другой - нет столбиков из точек. Эти столбики возникают в результате особенности примененного в ПЗУ Спектрума генератора RND - у него хоть и более-менее равномерная последовательность, но вот разброс значений (пункт4) далеко не "шумовой". Это, кстати, стоило бы учитывать. Подобные особенности генераторов ПСЧ весьма критичны в некоторых сферах их применения - скажем, если генератор используется для имитации кубика в игре типа нарды, кости, домино и т.д., то ситуации выпада четверки за тройкой, шестерки за пятеркой и т.д. весьма могут быть предсказуемыми из-за использования плохих датчиков ПСЧ.

Или представьте себе - процедура на ассемблере имитирует звездное небо. Генератор плохой, и вместо неба у вас получаются полоски...

Теперь рассмотрим алгоритм получения ПСЧ в родном спектрумовском ПЗУ. Алгоритм таков, судя по данным из литературы: seed=seed+1 seed=seed+75

seed=seed mod 65536 [65537?]

Bask-переменным значение seed возвращается как seed/65537. Хотя подобные данные следовало бы проверить, я не вполне уверен в точности данного алгоритма изменения seed. Но это не является моей целью, и я оставляю возможность выяснить алгоритм работы ПЗУ-шного датчика ПСЧ читателям. Более интересным фактом является то, что ПЗУ-шный алгоритм работает по хорошо известному алгоритму линейного конгруэнтного генератора. Только в ПЗУ, судя по всему, он несколько изменен по сравнению с оригиналом. Так вот, формула генерации следующего числа для линейного конгруэнтного генератора такова: X(j+1) = (X(j)*A+B) mod R, где

X(j) - текущий элемент ПСЧ-последовательности; A и B - константы; R - константа, задающая период;

а mod b - остаток от целочисленного деления a на b.

Этот генератор имеет максимальный период последовательности R до того, как она начнет повторяться. Период последовательности зависит от констант A и B. Линейный конгруэнтный генератор имеет максимальную длину последовательности ПСЧ тогда и только тогда, когда A mod 4 = 1 и B - нечетное. Это математически доказано.

Теперь попробуем реализовать такой датчик на ассемблере.

RND

MUL MULTS

LD

DE,0

LD

A,77

CALL

MUL

INC

HL

LD

(RND+1),HL

RET

LD

HL, 0

AND

A

RET

Z

RRA

JR

NC,$+3

ADD

HL, DE

SLA

E

RL

D

JP

MULTS

Эта процедура возвращает в HL псевдослучайные числа согласно алгоритму линейного конгруэнтного датчика ПСЧ. Здесь константа А=77, а В=1, чтобы удовлетворить максимальному периоду последовательности, который, кстати, равен длине регистров, и составляет 2Л16=65536 двухбайтных чисел. Операция MOD выполняется автоматически при умножении, так как мы теряем (усекаем) результат, оставляя лишь младшие его разряды, т.е. и выполняем функцию mod. Ради экспериментов можно менять число 77 на какое-либо свое. Важно лишь помнить, что остаток от деления этого числа на 4 (целочисленного деления) должен быть равен 1. Вместо постоянного коэффициента В=1 - это просто INC HL; можно конечно устроить:

LD DE,X

ADD HL,DE

где X следует брать нечетным.

Таким образом, изменются константы, и следя, чтобы они удовлетворяли требованию максимального периода последовательности, можно получать разные псевдослучайные последовательности. Если необходимо получить байт ПСЧ, то лучше всего брать его из старших разрядов - в данном случае из регистра H, так как период повторения кода в старших разрядах больше чем в младших. По этой же причине рекомендую, если необходимо менее 8 разрядов, пользоваться сдвигом вправо, а не усечением командой AND. Замечу, что процедуру умножения можно сделать на 2 байта короче, изменив последний JP на JR и SLA E, RL D на: EX DE,HL

ADD HL, HL

EX DE,HL

но потеряв при этом на каждом цикле умножения целых 5 тактов Z80. Кстати, циклов умножения необходимо 8, и можно вместо проверки множителя на 0 и досрочного выхода из процедуры просто поставить цикл. А можно, переписав процедуру, получить следующее:

MUL LD HL, 0

MULT RR A

JR NC,$+3

ADD HL,DE

EX DE,HL

ADD HL, HL

EX DE,HL

JR NZ,MULT

RET

Однако, вернемся к нашему генератору ПСЧ. Если положить А=5 и B=1, что удовлетворяет условиям получения максимально длинной последовательности, то можно написать линейный конгруэнтный генератор и проще, пожертвовав при этом лучшей равномерностью последовательности:

RND

LD

HL, 0

LD

D, H

LD

E, L

ADD

HL, HL

; HL=HL+2

ADD

HL, HL

; HL=HL+4

ADD

HL, DE

; HL=HL+5

INC

HL

; HL=HL+1

LD

(RND+1),HL

RET

; в HL будет

вое ПСЧ, в DE - старое ПСЧ. Теперь я хочу предложить несколько датчиков ПСЧ. Они хотя и не имеют математически обоснованных алгоритмов своей работы, но работают, тем не менее, неплохо:

RND

LD

HL, 0

LD

A, H

ADD

A, #77

LD

H,A

RLC

L

ADD

A, L

LD

L,A

LD

(RND+1),HL

RET

; в А - готовое ПСЧ.

Можете поэкспериментировать с этим генератором - попробуйте изменять число в 3-й строке, или команду RLC L на RRC L; ADD на SUB и так далее. Кстати, в отличие от предыдущих процедур, здесь нет такого правила, что период повторения кода в старших разрядах больше чем в младших, поэтому запросто можно пользоваться для усечения результата командой AND XX. Период последовательности у этой процедуры около 64000.

Следующая процедура оставляет в трех своих ячейках сразу три ПСЧ:

RND

в А - ПСЧ, HL указывает на SEED.

RET

SEED

ности:

RND

LD

HL, 0

LD

B,23

INRND

LD

A, H

ADD

HL, HL

AND

A

JP

PO,$+4

LD

HL,SEED

LD

A, (HL)

RRCA

RRCA

RRCA

AND

#1F

INC

HL

XOR

(HL)

INC

HL

RRA

RL

(HL)

DEC

HL

RL

(HL)

DEC

HL

RL

(HL)

RET

DEFB

128,255,63

Теперь приведу процедуру, интересную тем, что у нее можно изменять равномерность последователь-

константа глубины.

INC HL

DJNZ INRND

LD (RND+1),HL ; HL содержит ПСЧ.

RET ; А тоже содержит ПСЧ.

Однако, из-за того, что процедура имеет внутренний цикл, работает она сравнительно медленно. И, наконец, приведу процедуру, которую, в отличие от всех предыдущих процедур написал не я сам, а DAVE PERRY, автор известной на SEGA игры Alladin, и знакомый нам на Спекгруме играми Savage, Turtles и т.д. Я нашел эту процедуру в играх Savage, Stainles Steel. Выглядит она так: RND

в А и B SEED останется ПСЧ.

SEED

PUSH

HL

PUSH

HL

LD

DE,(SEED)

LD

H, E

LD

L, #FD

LD

A, D

AND

A

SBC

HL, DE

SBC

A,0

SBC

HL, DE

SBC

A,0

LD

E,A

LD

D,0

SBC

HL, DE

JR

NC,$+3

INC

HL

LD

(SEED),HL

POP

DE

POP

HL

RET

DEFW

0

Стоит, кстати, заметить, что если требуется ПСЧ в районе 0...127, то его с успехом можно считать из регистра R процессора. Правда, такой трюк будет проходить только, если между считываниями ПСЧ из регистра R, основная программа выполняет процедуры с изменяющимися временными задержками или если пользователь внешне заставит программу выполнять какие-либо действия. Если же попробовать использовать регистр R для получения ПСЧ в каком-либо коротком цикле, то особенно надеяться на успех не приходится. Также, можно попробовать использовать, как таблицу готовых ПСЧ, само ПЗУ Спектрума. Этот метод, в сочетании с регистром R, уже эффективнее, и им пользуются. Это можно сделать, например, так: RND

LD

HL, 0

; текущий адрес ПЗУ

INC

HL

LD

A, H

AND

#1F

; не #3F, т.к. в конце ПЗУ

LD

H,A

LD

(RND+1),HL

LD

A, R

XOR

(HL)

; для большей случайности.

RET

Но гораздо эффективней пользоваться другими генераторами ПСЧ - например, линейным конгруэнтным генератором и т.п. Если Вам потребуется небольшое знаковое ПСЧ, то его можно получить, например, так:

CALL RND ; в А имеем ПСЧ

AND 7 ; сделаем его не более 7

SUB 4

RET ; теперь ПСЧ в ранге -4...+3

В общем и целом, данная статья дает возможность использовать эффективные генераторы ПСЧ в самых различных областях программирования. Можно, скажем, защищать (XOR-ить) свои файлы, как я сделал в импортированной мною польской мегадемо LSD ( напомню, что после таких XOR-ок файлы будут очень плохо сжиматься) или использовать генераторы ПСЧ в процедурах вывода звука (шума), и т.д. Напоследок приведу три примера процедур, использующих генератор ПСЧ: Пример 1.

ORG #8000 STARS EI

HALT

CALL RND LD C,A

RE_RND CALL CP JR LD

CALL INC LD LD

RRCA

DJNZ

OR

LD

LD

IN

RRA

JR

RET

RND LD

LD ADD LD RLC ADD LD LD RET

Пример 2.

ORG

NOISEFX DI

SUB

INNER_L LD LD ADD ADD ADD INC JR XOR OUT JR

ZX_HANG EI

RND 192

NC,RE_RND B,A #22B1 A

B,A ■bA, 1

$-1 (HL) (HL),A A, #7F A,(#FE)

C,STARS

HL, 0 A, H A, #77 H,A

L

A, L L,A

(RND+1),HL

#8000 A

D, H

E, L HL, HL HL, HL HL, DE HL

C,INNER_L #1B

(#FE),A INNER_L

INNER

RND

Пример 3.

B_FX

HALT LD

CALL

SRL

LD

INC

LD

CP

JR

JR

LD

LD

ADD

LD

RLC

ADD

LD

LD

RET

ORG EI

HALT

DE,#5800

RND

A

(DE),A DE A, D #5B

C,INNER ZX_HANG HL, 0 A, H A, #77 H,A L

A, L L,A

(RND+1),HL

#8000

LD

HL,(RND+1)

PUSH

HL

LD

DE,210

CALL

RND

AND

7

OUT

(#FE),A

LD

B, 14

DJNZ

$

DEC

DE

LD

A, D

OR

E

JR

NZ,C_OUT

POP

HL

LD

(RND+1),HL

CALL

RND

LD

A, #7F

IN

A,(#FE)

RRA

JR

C,B_FX

RET

LD

HL, 0

LD

A, H

ADD

A, #77

LD

H,A

RLC

L

ADD

A, L

LD

L,A

LD

(RND+1),HL

RET

C_OUT

RND

Процедура NOISE_FX использует внутренний генератор ПСЧ, а остальные - процедуры генераторов из первой. Вы можете по своему вкусу установить цвета, режим прерываний, опрос клавиш и т.д.




СОДЕРЖАНИЕ:


  Оставте Ваш отзыв:

  НИК/ИМЯ
  ПОЧТА (шифруется)
  КОД



Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Мнение - Сага о Ламерах.
Edit off - Ну вот, вроде, небольшой номерок 2 и завершен...
Письмо в LPRINT - Критика газеты LPRINT...
Министроки - стих "Старик".
Предисловие - О новой оболочке газеты.

В этот день...   28 марта