Быстродействующий генератор псевдослучайных чисел
(С) Сергей Астров,
г.Чебоксары, 1995.
В этой последовательности" всего 2|4-1-15 чисел в периоде повтора значений.
Но если рассмотреть такую схему:
регистр сдвига ->
Мне удалось реализовать генератор случайных чисел, который удивительно короток. Способ генерации чисел, который я предлагаю читателям, не нов и используется очень широко в генерации "белого шума" (см. П.Хоровиц, У. Хилл "Искусство схемотехники", том 2, М. "Мир" 1993, с.277-279) именно на этом принципе основан генератор .
Для генерации псевдослучайных чисел в электронике используется регистр сдвига с обратной связью:
регистр сдвига
3
исключаю1 2 I 3 I 4
7
[<{1
получим последовательность:
1111 0111 0011 1001 1100 1110
1111 0111 ........
- всего 6 чисел! Что же случилось? Дело в том, что эта схема не является схемой регистра мак^ симальной длины (в отличие от предыдущего).
Теперь после краткой теории перейдем к практике. Для генератора случайных чисел в ZX-Spect-rum используется двухбайтная системная переменная SEED (23670/ 23671). В переменной SEED 16 битов, а для 16-битового регистра не существует схемы максимальной длины, если используется два отвода XOR. В таких случаях следует использовать несколько отводов X0R. Для 16-разрядного регистра используют отводы: 4, 13, 15 и последний - 16:
регистр сдвига ->
I— регистр L —1|— регистр Н —i
|
• |
i |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
'1 |
|
1 |
XOR |
|
|
I |
|
|
|
|
|
|
L |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
< |
|
|
|
|
|
|
|
|
|
Цикл повтора: 65535 чисел. Пожалуй, существует только один недостаток у этой программы - никак нельзя получить нулевое значение.
Теперь сама программа:
1 ORG 50000
2 ENT $
3 RND_3 LD HL,(SEED)
4 LD A,H
5 OR L
Последнюю строку можно изменить :
23 SEED EQU 23670
Длина блока кодов генератора составляет всего 37 байтов.
|
C350: |
2A |
73 |
C3 |
7C |
B5 |
20 |
01 |
2C |
:F1 |
|
C358 : |
CB |
25 |
CB |
14 |
CB |
7C |
28 |
01 |
:5A |
|
C360: |
3F |
CB |
6C |
28 |
01 |
3F |
CB |
65 |
: 31 |
|
C368: |
28 |
01 |
3F |
30 |
02 |
CB |
C5 |
22 |
: 77 |
|
C370: |
73 |
C3 |
C9 |
00 |
00 |
00 |
00 |
00 |
: 32 |
Комментарий ИНЯЮРКОМА.
Аналогичные генераторы уже публиковались на страницах РЕВЮ. Первый из них - ZX-PEBI0-94, N6, стр.5. Более короткий и быстрый (Сергея Колотова) - ZX-PEBI0-95, N4, стр.49, там же приведена тестовая программа, позволяющая сравнить быстродействие и другие качественные характеристики генераторов. Воспользуемся той же программой и для тестирования нового генератора. Получены следующие результаты: время полного заполнения экрана цветом INK - 7 сек., что почти вдвое быстрее, чем у варианта Сергея Колотова. Длина блока кодов тоже короче 37 байтов вместо 45 у предыдущегб варианта. Но вот, неприятность -при работе генератора четко прослеживается периодический характер генерируемых чисел. Сравните са-
|
6 |
|
JR |
NZ,L0 |
|
7 |
|
INC |
L |
|
8 |
L0 |
SLA |
L |
|
9 |
|
RL |
H |
|
10 |
|
BIT |
7 , H |
|
11 |
|
JR |
Z,L1 |
|
12 |
|
CCF |
|
|
13 |
L1 |
BIT |
5 , H |
|
14 |
|
JR |
Z,L2 |
|
15 |
|
CCF |
|
|
16 |
L2 |
BIT |
4 ,L |
|
17 |
|
JR |
Z,L3 |
|
18 |
|
CCF |
|
|
19 |
L3 |
JR |
NC, L4 |
|
20 |
|
SET |
0, L |
|
21 |
L4 |
LD |
(SEED),HL |
|
22 |
|
RET |
|
|
23 |
SEED |
DEFW |
0 |
Видим довольно хорошее случайное распределение, причем, практически одинаковое у обоих предыдущих вариантов.
А так - работа третьего (сегодняшнего) варианта:
Возможно, улучшить работу генератора возможно, изменяя места отводов XOR или применяя другие "перемешивающие" приемы.
Итак, если для Вас на первом месте стоит быстродействие, то можете с успехом использовать этот вариант. Проверка покажет, не приведет ли новый алгоритм к назойливому повторению чисел, выпадающих на игральном кубике и т.д>. Не забудьте и о невозможности получения нулевого значения.
ми. Вот так выглядит фрагмент работы двух предыдущих версий генераторов :
