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

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

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

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

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

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

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

Эта процедура возвращает в 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

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

RND

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

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

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

RND

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

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

INC HL

DJNZ INRND

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

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

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

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

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

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

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

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

1. От редакции - вы держите в руках сдвоенный (4+5)-й номер ZX РЕВЮ. Впервые на 6-м году своего существования эти номера выходят так рано.
2. Авторская разработка - Адаптация игр 8-битовых видеоприставок для ZX-Spectrum с видеопроцессором.
3. Авторская разработка - винчестер для ZX spectrum.
4. Новые программы - STalker Stealth monitor. Версия 4.2. (STS v.4.2).
5. Новые программы - Теневой макроассемблер-отладчик ALASM 128/512 v.2.5.
6. TR-DOS для начинающих - продолжение (начало см. ZX РЕВЮ 96/1-2).
7. Читатель - читателю - multicolor - эффекты на бордюре и кое-что еще.
8. Читатель - читателю - получение случайных чисел.
9. Компьтеры, которые мы выбираем - доступ к верхней области памяти.
10. Этюды - о табличном программировании.
11. Этюды - вывод символа в восьмикратном увеличении.
12. Этюды - индикатор амплитуды звука.
13. Этюды - бегущая строка.
14. Этюды - способ вывода изображения на экран.
15. Этюды - эффекты для музыкального сопроцессора.
16. Этюды - процедуры "проявления" экрана.
17. Этюды - процедура-календарь.
18. Этюды - процедура поиска шрифтов и спрайтов.
19. Этюды - оригинальная бегущая строка.
20. Этюды - процедура опроса клавиатуры.
21. Этюды - программа гашения экрана случайным образом.
22. Этюды - загрузка Бейсик-программ без автостарта.
23. Этюды - компрессор символьной информации.
24. Этюды - быстрая печать шаблона 8*8.
25. Форум - установка порта #FD.
26. Форум - жесткая дешифрация порта #1FFD В ПК "Scorpion ZS-256.
27. Форум - доработка STS 3.3.
28. Форум - доработка Tasm 128.
29. Форум - доработка посекторных загрузчиков.
30. Форум - нестандартные магнитофонные загрузчики.
31. Форум - процедура печати 42 символов в строке.
32. Форум - настройка дисководов.
33. Форум - о программе G.A.C.
34. Форум - о вызове подпрограмм TR-DOS.
35. Форум - об управлении КР181ВГ93.
36. Форум - о компьютере "Hobbit".
37. Форум - усовершенствованная версия Advanced Drive FX.
38. Форум - недокументированные операторы LASER BASIC.
39. Форум - о настройке дисководов.
40. Форум - вопросы сегментации экрана.
41. Форум - магнитофонный загрузчик с индикатором.
42. Форум - об игре "LIFE".
43. Форум - проблемы развития ZX Spectrum.
44. Форум-Игры - рассмотрены следующие игры: Venturama, The sceptre, Carrier command, Elite, Sim city, Robin of the wood, Think, Hacker 2, Rampage, Звёздное наследие, "A.T.F.", Colony.
45. Перекресток - рассмотрены следующие адвентюры: He-man, Hampstead, Звёздное наследие, Rebel planet, The famous five, Terrormolinos, Sam spoon, Spiderman, Kentilla, Heavy on the magic, Magnetic moon.
46. Adventure project - анализ частей речи в русскоязычных ADVENTURE.
47. Советы экспертов - описание игры Rock star ate my hamster.
48. Советы экспертов - описание игры Dundees european challenge.
49. Советы экспертов - описание игры Winter games.
50. Советы экспертов - описание игры Carrier comand.
51. Советы экспертов - описание игры The ghostbusters 2.
52. Советы экспертов - описание игры Hacker.
53. Советы экспертов - описание игры Last battle.
54. Советы экспертов - описание игры Captain Fizz.
55. Компьютерная новелла - История в момент творения (по игре MYTH).
56. Компьютерная новелла - Nether Earth.
57. Tricks ZX - коды, пароли, хитрости.
58. Справочная информация - где можно приобрести наши издания.