Генератор случайных чисел (asm x86)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:48, 9 августа 2015.

Мультипликативный конгруэнтный метод генерации последовательности случайных чисел

Мультипликативный конгруэнтный метод задает последовательность неотрицательных целых чисел , получаемых по формуле:

На значения накладываются ограничения:

  • - нечетно;
  • или - обе эти записи означают, что младшая цифра при представлении в восьмеричной системе счисления должна быть равна 3 или 5 (проще говоря, остаток от деления на 8 должен быть равен 3 или 5);

При соблюдении этих ограничений длина периода будет равна

;+-------------------------------------------------------------------------+
;| Программа: rand_mult_cong_l.asm. Генератор линейной (мультипликативной) |
;| конгруэнтной последовательности случайных чисел (c=0)                   |
;+-------------------------------------------------------------------------+				
;| Вход: X0. a. m.                                                         |
;+-------------------------------------------------------------------------+
;| Выход: dl - значение очередного случайного числа.                       |
;+-------------------------------------------------------------------------+
.data
m	db      128
а	db      11
X	db      3	            ; начальное значение
.code
     ;------ первое число в последовательности х=3
cycl:	mov     al.x	            ; вычисляем очередное случайное число Х=(а*Х) mod m
        mul     a	            ; а*х в ah:al
        div     m	            ; в ah случайное число
        mov     x. ah
     ;------ вывод в файл - командная строка rand_mu1t_cong.exe > p.txt
        mov    dl. ah 
        mov    ah. 02 
        int    21h 
        jmp    cycl 
end_cycl:	;...

Если является степенью 2, как в данном случае, то вместо команды DIV можно использовать две команды сдвига.

;+---------------------------------------------------------------------------+
;| Программа: rand_mult_cong_l.asm. Генератор линейной (мультипликативной)   |
;| конгруэнтной последовательности случайных чисел (c=0)                     |
;+---------------------------------------------------------------------------+				
;| Вход: X0. a. m. - в соответствии с указанными ограничениями.              |
;+---------------------------------------------------------------------------+
;| Выход: dl - значение очередного случайного числа.                         |
;+---------------------------------------------------------------------------+
cycl:	
     ;------ вычисляем очередное случайное число Х=(а*Х) mod m
        mov     al.x	            
        mul     а	            ; а*х в ah:al
        shrd    ax. ax. cl
        xor     al. al
        rol     ax. cl              ; в al случайное число
     ;------ вывод в файл - командная строка rand_mu1t_cong.exe > p.txt
             ;...

Полный пример этой программы (rand_mult_cong_2.asm) вы найдете среди файлов, прилагаемых к книге.

Используя эти программы, можно получить последовательность случайных чисел, содержащую 32 значения — это ее период. Чтобы увеличить период, необходимо каким-либо способом сгенерировать значения или , удовлетворяющие приведенным выше ограничениям. Так, значение можно вычислить, используя фрагмент:

.data
divider	db      8
.code
     ;------ вычисляем a исходя из соотношения, а mod 8 - 5
     ;	     одним из способов получить значение а (m>=а)
     ;       удовлетворяем условию а mod 8=5 
m2:	mov     al. а
        xor     ah. ah 
        div     divider
        cmp	ah. 5	            ; остаток равен 5?
        je	m1
        cmp	ah. 3	            ; остаток равен 3?
        je	m1
        inc	a
        jmp	m2

m1:	                            ; теперь a найдено до конца
             ;...

Изменить (увеличить) период можно, корректируя значение , для чего требуется исправить соответствующие команды в программах rand_mult_cong_l.asm и rand_mult_cong_2.asm, ориентированные на определенную разрядность регистров. Существует другая возможность увеличения периода — использование смешанного конгруэнтного метода генерации последовательности случайных чисел.

Смешанный конгруэнтный метод генерации последовательности случайных чисел

Соотношение смешанного конгруэнтного метода выглядит так:

где .

При правильном подборе начальных значений элементов, кроме увеличения периода последовательности случайных чисел, уменьшается корреляция (зависимость) получаемых случайных чисел.

На значения накладываются ограничения:

  • ;
  • , где
  • взаимно просто с (это выполнимо, если — нечетно, а , где
  • и кратно 4.
;+---------------------------------------------------------------------------+
;| Программа: rand_mix_cong_l.asm. Генератор линейной (смешанной)            |
;| конгруэнтной последовательности случайных чисел (c>0)                     |
;+---------------------------------------------------------------------------+				
;| Вход: X0. a. c. m. - в соответствии с указанными ограничениями.           |
;+---------------------------------------------------------------------------+
;| Выход: dl - значение очередного случайного числа.                         |
;+---------------------------------------------------------------------------+
.data
m	db      128	; 128=2^7
а	db      9
x	db      3	; начальное значение
с	dw      3
.code
        mov     cl. 7	; значение степени m = 27 в cl
     ;------вычисляем очередное случайное число Х=(а*Х) mod m.
     ;	    первое число в последовательности х=3
сусl:	mov     al. x
        mul  	a       ; а*х в ah:al
        add     ax. c 
        shrd    ax. ax. cl 
        xor     al. al
        rol     ax. cl	; в al случайное число
     ;------вывод в файл - командная строка rand_mult_cong.exe > p.txt
                ;...
end_cycl:	;...

Величина периода случайной последовательности, получаемой с помощью данной программы, составляет 128. Сегмент кода программы rand_mix_cong_l.asm можно оформить в виде процедуры. Начальное значение можно выбирать двумя способами: задавать константой в программе или генерировать случайным образом. В последнем случае достаточно опереться на такты системного таймера, как в следующей макрокоманде:

;+---------------------------------------------------------------------------+
;| Макрокоманда: rCMOS. Чтение значений CMOS                                 |
;+---------------------------------------------------------------------------+				
;| Вход: al - адрес ячейки, значение которой читаем.                         |
;+---------------------------------------------------------------------------+
;| Выход: al - прочтенное значение.                                          |
;+---------------------------------------------------------------------------+
rCMOS	macro
        out     70h. al 
        xor     al. al
        in      al. 71h	; вводим в регистр AL из порта
                        ; значение ячейки CMOS
endm

Применение — получить значение секунд из CMOS для x_start:

.code
       mov      al. 0h
       rCMOS
       mov      x.al    ; x=x_start
       ;...

Таким способом можно получить начальное значение из диапазона 0-59. Для получения большего по величине начального значения подходит величина размером 32 бита из области данных BIOS по адресу 0040:006с. Здесь содержится счетчик прерываний от таймера. Извлечь это значение можно при помощи следующего программного фрагмента:

       push     ds
       push     word ptr 40h 
       pop      ds
       mov      eax. dword ptr ds:006ch 
       pop      ds

Заменяя команду MOV командой MOV AX, word ptr ds:006ch или MOV AL, byte ptr ds:006ch, можно использовать младшие 8 или 16 битов значения из этой области BIOS. Команда MOV AL, byte ptr ds:006ch позволяет случайным образом загрузить в регистр AL значение из диапазона 0-0ffh.

При работе под Windows в качестве начального можно использовать значения из счетчика меток реального времени TSC [39].

Попытки создать программный датчик случайных чисел без опоры на какие-либо теоретические выкладки обречены на провал. Рассмотрим еще несколько способов генерации случайных чисел.

Аддитивный генератор случайных чисел

Генератор, формирующий очередное случайное число в соответствии с отношением

называется аддитивным.

D трехтомнике Кнута [5] обсуждаются подобные генераторы и рекомендован следующий вариант этой формулы:

Здесь — произвольные числа, среди которых есть и нечетные. При этих условиях длина периода последовательности равна .

Для генерации первых 55 случайных чисел можно использовать один из рассмотренных выше генераторов. Возьмем датчик линейной (смешанной) конгруэнтной последовательности случайных чисел ().

;+-----------------------------------------------------------------------------+
;| Программа; rand_add.asm. Аддитивный генератор случайных чисел.              |
;+-----------------------------------------------------------------------------+				
;| Вход; Х0. а. с. m.                                                          |
;| случайная последовательность длиной 55 значений, получаемая с помощью       |
;| программы генерации высокослучайных двоичных наборов (rand_mix_cong l.asm). |
;| N = 700 - количество элементов в последовательности + 1.                    |
;| L=7 - значение степени m=2^7                                                |
;+-----------------------------------------------------------------------------+
;| Выход: dl - Значение очередного случайного числа.                                            |
;+-----------------------------------------------------------------------------+
.data
        N = 700	                    ; число элементов в последовательности + 1
        L = 7	                    ; значение степени m=2^7
m       db       128	            ; 128 = 2^7
mm      dw       256	            ; 256 = 2^8
а	db       9
с	dw       3
x	db       3. N dup (Offh)   ; массив значений x (начальное значение
                                    ; равно 3) длиной N + 1
.code
        ;------ далее фрагменты из rard_mix_cong_l.asm
        xor      si. si
        mov      ecx, 54	    ; счетчик цикла для формирования
                                    ; начальной последовательности 
        mov      al. x	            ; первое число в последовательности (х=3)
        ;------вычисляем очередное случайное число Х=(а*Х) mod m
cycl:	mul      a	            ; a*x в ah:al
        add      ax. с
        shrd     ax. ax. L          ; L - значение степени m=2^7 
        xor      al. al
        rol      ax. L	            ; в al случайное число
        ;------ вывод в массив х и файл - командная строка
        ;       rand_mult_cong.exe > p.txt
        inc      si
        mov      x[si]. al
        mov      dl. al
        mov      ah. 02
        int      21h
        loop     cycl
        ;------ далее продолжаем формирование случайной последовательности.
        ;       но уже аддитивным методом 
        mov      ecx. N - 55 
cycl2:	inc      si
        xor      dx. dx 
        mov      al. x[si-24] 
        mov      dl. x[si-55] 
        add      ax. dx 
        xor      dx. dx 
        div      mm 
        mov      x[si]. dl
        mov      ah. 02 
        int      21h 
        loop     cycl2

exit:
        ;...

Судя пo результатам, этот метод достаточно хорош. В частности, он неплох тем, что позволяет задавать длину последовательности без оглядки на значение .

Следующий рассматриваемый нами датчик можно использовать в программах на языке ассемблера для получения случайной последовательности 0 и 1.