Программирование целочисленных арифметических операций
Всякое математическое доказательство, за которым мы можем следить, выразимо конечным числом символов. Эти символы, правда, могут быть связаны с понятием бесконечности, но связь эта такова, что ее можно установить за конечное число шагов. Так, когда в случае математической индукции мы доказываем теорему, зависящую от параметра n, мы доказываем ее сначала для n=0 и затем устанавливаем, что случай, когда параметр имеет значение n+1, вытекает из случая, когда параметр имеет значение n. Тем самым мы убеждаемся в правильности теоремы для всех положительных значений параметра n. Более того, число правил действия в нашем дедуктивном механизме должно быть конечным, даже если оно кажется неограниченным из-за ссылки на понятие бесконечности. Ведь и само понятие бесконечности выразимо в конечных терминах. |
В уроке 8 «Арифметические команды» учебника было приведено достаточно подробное (с соответствующими рассуждениями и примерами) описание возможностей микропроцессора по выполнению арифметических операций над целочисленными данными. Также было отмечено, что при выполнении этих операций возникают характерные ситуации, обнаружение и обработка которых возлагается на программиста. Именно этому вопросу мы и уделим внимание в данном материале. Вначале вспомним основные моменты.
Микропроцессор Intel имеет средства для обработки целочисленных арифметических данных двух форматов: двоичного и двоично-десятичного (BCD). Данные в двоичном формате рассматриваются как числа со знаком и без знака. При этом необходимо заметить, что не существует отдельного формата для чисел со знаком и без знака. Один и тот же двоичный код может рассматриваться как значение со знаком и без знака. Все зависит от того, как трактуется старший бит операнда. Для чисел без знака он является старшим значащим битом операнда. Для чисел со знаком смысл старшего значащего бита операнда меняется: его нулевое значение соответствует положительному числу, единичное — отрицательному. Остальные разряды операнда — значащие. Но здесь есть один нюанс, смысл которого в том, что остальные разряды не являются модулем числа. Для положительного числа они действительно являются абсолютной величиной числа,
а вот для отрицательного числа они представляют так называемый дополнительный код числа. Идея дополнительного кода состоит в том, что микропроцессору совсем необязательно иметь отдельные устройства для сложения и вычитания. Достаточно только одного — сумматора.
Есть всего лишь две команды в системе команд микропроцессора, которые воспринимают старший бит операнда как знаковый, — это команды IMUL и IDIV. В остальных случаях забота о правильной трактовке старшего бита ложится на программное обеспечение. Программирующий на ассемблере должен сам предусматривать особенности обработки знаковых битов.
Другая характерная ситуация при выполнении арифметических действий — переполнение и антипереполнение. Их причина — ограниченность разрядной сетки операнда. При выполнении операции сложения или умножения возможен выход результата за пределы разрядной сетки. Если результат больше максимально представимого значения для операнда данной размерности, то говорят о ситуации переполнения. Иначе, если результат меньше минимально представимого числа, то говорят о ситуации антипереполнения. При этом результат также верен, но при его соответствующей трактовке. Все эти рассуждения приведены в уроке 8 «Арифметические команды» учебника, и повторять мы их не будем. Сосредоточимся на практическом аспекте этого вопроса. Ситуация переполнения может иметь место при вычислениях, в которых заранее не известен размер операндов.
Двоичные числа
Прежде чем программировать,
запишите программу в псевдокодах.
Д. Ван Тассел
Сложение двоичных чисел
Сложение чисел размером 1 байт без учета знака
---------------------------------------------------------------------
:add_unsign - процедура сложения чисел размером 1 байт без учета_1 знака
;Вход: sumnand_1и summand_2 - слагаемые.
:Выход: sum_b или sum_w - значение суммы с учетом переполнения.
---------------------------------------------------------------------
.data
summand_1db ? значения в summand_1и summand_2
summandj? db ? :нужно внести
sum_w label word
sum_b db 0
carry db 0
.code
add_unsign proc
mov al ,summand_2
add al ,summand_1mov sumji.al
jnc end_p :проверка на переполнение
adc carry,0
end_p: ret
add_unsign endp
Программа учитывает возможное переполнение результата. Сложение двоичных чисел большей размерности (2/4 байта) выполняется аналогично. Для этого необходимо заменить директивы DB на DW/DD и регистр AL на АХ/ЕАХ.
Сложение чисел размером N байт без учета знака
:add_unsign_N - процедура сложения чисел размером N байт без учета знака
:Вход: summand_1 и summand_2 - слагаемые. N - длина в байтах.
:Выход: summand_1или carry+summandj. - значение суммы с учетом переполнения.
.data
summand_1db ? ;первое слагаемое
N=$-surranand_1;длина в байтах значений summand_1и summand_2
carry db 0 :перенос сложения последних байтов
summand_2 db ? :второе слагаемое
.code
add_unsign_N proc
mov cl. N
хог si.si cycl: mov al ,summand_2[si]
adc summand_l[si].al
inc si
loop cycl
jnc end_p ;проверка на переполнение
adc carry. 0
end_p: ret
add_unsign_N endp
Программа учитывает возможное переполнение результата. Сегмент данных может быть задан, например, так:
.data
summand_1db 0.34.56.78.250 ; первое слагаемое
N=$-summand_1:длина в байтах значений summand_1и summand_2
carry db 0 ;перенос сложения последних байт
summand_2 db 0.43.65.230.250 : второе слагаемое
Далее при рассмотрении программы деления многобайтных двоичных чисел нам понадобится макрокоманда сложения без учета знака чисел размером N байт (порядок следования байтов не соответствует порядку следования байтов на процессорах Intel, то есть старший байт находится по младшему адресу). Приведем ее.
Сложение без учета знака чисел размером N байт (макрокоманда)
.data
:summand_ldb ? :первое слагаемое
;N=$-summand_1,:длина в байтах значений summand_1и summand_2
;carry db 0 :перенос сложения последних байтов
;summand_2db ? ; второе слагаемое
.code
.старший байт по младшему адресу
add_unsign_N macro carry.summand_l.summand_2.N
local cycl.end_p
:add_unsign_N carry,summand_1,sunmand_2.N - макрокоманда сложения без учета знака чисел :размером N байт
:Вход: summand_1l и summanct_2 - слагаемые. N - длина в байтах.
;Порядок следования байтов - старший байт по младшему адресу (не Intel).
;Выход: summand_1или carry+summand_1- значение суммы с учетом переполнения.
mov cl.N
mov si.N-1 cycl: moval,summand_2[si]
adc summand_l[si].al
dec si
loop cycl
jnc end_p
adc carry.0
end_p: пор
endm
Сложение чисел размером 1 байт с учетом знака
---------------------------------------------------------------------
;add_sign - процедура сложения чисел размером 1 байт с учетом знака
:Вход: summand_1и summandj? - слагаемые.
:Выход: sum_b или sum_w - значение суммы в зависимости от наличия расширения знака.
---------------------------------------------------------------------
.data
sum_w label word
summandl db ? :значения в summand_1и summand_2 нужно внести
carry db 0 ; расширение знака
summand_2 db ?
.code
add_sign proc
mov al ,summand_2
add summand_l.a1
jc @@cfl_ofl
jo @<acfO_ofl
:cf=0 of=0 -> результат верный :cf"l of=0 -> результат верный r_true: jmp end__p результат -> summand_1@icfl_ofl: jno
@@cfl_of0 :cf=1 of=1 -> результат неверный
mov carry.0ffh расширение знака д.б. -1, результат ->sum_w
jmp end_p
:cf=1 of=0 -> результат верный
@@cfl_of0: jmp r_true результат -> summand_1:cf=0 of=1 -> результат неверный
@@cf0_ofl: mov carry.0 .-расширение знака д.б. =0. результат ->sum_w
jmp end_p end_p: ret add_sign endp
Программа учитывает возможное переполнение результата и перенос в старшие разряды. Для этого отслеживаются условия, задаваемые флагами, и выполняются действия:
CF=0F=0 — результат правильный и является положительным числом; CF=1 0F=0 — результат правильный и является отрицательным числом; CF=0F=1 — результат неправильный и является положительным числом, хотя правильный результат должен быть отрицательным (для корректировки необходимо увеличить размер результата в два раза и заполнить это расширение нулевым значением); CF=0 0F=1 — результат неправильный и является отрицательным числом, хотя правильный результат должен быть положительным (для корректировки необходимо увеличить размер результата в два раза и произвести расширение знака).Сложение чисел со знаком большей размерности (2/4 байта) выполняется аналогично, для этого необходимо внести изменения в соответствующие фрагменты программы. В частности, необходимо заменить директивы DB на DW/DD и регистр AL на АХ/ЕАХ.
Сложение с учетом знака чисел размером N байт
---------------------------------------------------------------------
:add_sign_N - процедура сложения с учетом знака чисел размером N байт
-.Вход: summand_1и summand_2 - слагаемые. N - длина в байтах.
:Выход: summand_1или carry+summand_1- значение суммы с учетом переполнения.
---------------------------------------------------------------------
.data
summand_1db ? :первое слагаемое
N=$-summand_1:длина в байтах значений summand_1и summand_2
carry db 0 расширение знака
summand_2 db ? :второе слагаемое
.code
add_sign_N proc
mov cx.N
mov si .0-1 cycl: incsi
mov al ,summand_2[si]
adc summand_l[si].al
loop cycl
jc @@cfl_ofl
jo @(acfO_ofl
:cf=0 of=0 -> результат верный :cf=1 of=0 -> результат верный r_true:jmp end_p результат -> summand_1@@cfl_ofl:
jno?@cfl_of0 :cf=1 of-1 -> результат неверный
mov carry.0ffh расширение знака д.б. =1. результат ->sum_w
jmp end_p @@cfl_of0: :Cf»l of=0 -> результат верный
jmp r_true результат -> summand_1@0cf0_ofl: :cf=0 of=1 -> результат неверный
mov carry.0расширение знака д.б. =0. результат ->sum_w
jmp end_p end_p: ret add_sign_N endp
Сегмент данных может быть задан, например, так:
.data
summand_1db 32,126,-120 ;первое слагаемое
N=$-summand_1;длина в байтах значений summand_1и sumniand_2
carry db 0 расширение знака
summand_2 db 126,125,-120 ;второе слагаемое
Программа учитывает возможное переполнение результата. Обратите внимание на порядок задания значений слагаемого. Если слагаемое положительное, то проблем нет. Отрицательное слагаемое размером N байт для своего задания требует некоторых допущений. Старший байт отрицательного слагаемого задается со знаком и в процессе трансляции будет преобразован в значение, являющееся двоичным дополнением исходного значения. Остальные байты в своем исходном виде должны быть частью доbxя. Поэтому для работы с числами со знаком удобно иметь программу, которая бы выполняла вычисление значения модуля отрицательного числа и, наоборот, по значению модуля вычисляла его дополнение.
Вычисление дополнения числа размером N байт
---------------------------------------------------------------------
: calc_complement - процедура вычисления дополнения числа размером N байт
;Вход: bx - адрес операнда в памяти; сх - длина операнда.
;Порядок следования байт - младший байт по младшему адресу. ;
Выход: bx - адрес результата в памяти
---------------------------------------------------------------------
.code calc_complement proc
хог si,si
neg byte ptr [bx] дополнение первого байта
cmp byte ptr [bx],0 ;нулевой операнд - особый случай
jne short $+3
stc установить cf, так как есть перенос
dec ex
jcxz @@ml ;для однобайтного операнда
@@cycl: iпс si
not byte ptr [bx][si]
adc byte ptr [bx][si],0
loop @@cycl
@@ml: ret calc_complement endp
Для значений размерностью 1/2/4 байта дополнение можно получать с помощью одной команды NEG:
neg operand
Для значений N байт необходимо реализовывать алгоритм. Дополнение первого байта необходимо вычислять с учетом того, что он может быть нулевым. Попытка получить его дополнение с помощью команды NEG обречена на провал. Флаг CF в этом случае также должен устанавливаться программно. Подумайте, почему?
Вычисление модуля числа размером N байт
---------------------------------------------------------------------
:calc_abs - процедура вычисления модуля числа размером N байт
:Вход: bx - адрес операнда в памяти; сх - длина операнда.
;Порядок следования байтов - младший байт по младшему адресу.
:Выход: bx - адрес результата в памяти.
---------------------------------------------------------------------
.code
calc_abs proc определим знак операнда
mov si.cx
dec si
test byte ptr [bx][si],80h проверяем знак операнда
jz @@exit ;число положительное
call calc_complement @@exit:ret
calc_abs endp
Вычитание двоичных чисел
Вычитание чисел размером 1 байт без учета знака
---------------------------------------------------------------------
;sub_unsign - процедура вычитания чисел размером 1 байт без учета знака
;Вход: minuend и deduction - уменьшаемое и вычитаемое.
:Выход: minuend - результат вычитания
.---------------------------------------------------------------------
.data значения в minuend и deduction нужно задать
minuend db ? уменьшаемое
deduction db ? ;вычитаемое
.code
sub_unsign proc
mov al .deduction
subminuend.al :оценить результат на случай уменьшаемое < вычитаемого
jnc end_p ; нет заема обрабатываем ситуацию заема из старшего разряда - получаем модуль (если нужно)
neg minuend end_p: ret sub_unsign endp
Программа учитывает возможное соотношение: уменьшаемое<вычитаемого. Вычитание чисел большей размерности (2/4 байта) выполняется аналогично. Необходимо заменить директивы DB на DW/DD и регистр AL на АХ/ЕАХ.
Вычитание чисел размером N байт без учета знака
---------------------------------------------------------------------
:sub_unsign_N -.процедура вычитания чисел размером N байт без учета знака
:Вход: minuend и deduction - уменьшаемое и вычитаемое, N - длина в байтах.
;Выход: minuend - значение разности.
---------------------------------------------------------------------
.data значения в minuend и deduction нужно внести
minuenddb ? уменьшаемое
N=$-minuend ;длина в байтах значений minuend и deduction '.
deduction db ? :вычитаемое
.code
sub_unsign_N proc
mov cl.N
xor si,si cycl: moval ,deduction[si]
sbbminuend[si].al
jnc @@ml
negminuendtsi] @@ml: inc si
loop cycl
ret sub_uns1gn_N endp
Программа учитывает возможный заем из старших разрядов. Длина уменьшаемого должна быть не меньше длины вычитаемого, недостающие разряды вычитаемого должны быть нулевыми. В любом случае, результат — абсолютное значение.
Сегмент данных может быть задан, например, так:
.data
N equ5 ;длина в байтах значений minuend и deduction
minuenddb 30.43.65.230,250 уменьшаемое
deduction db 45.34.65.78.250 ;вычитаемое
Вычитание чисел размером 1 байт с учетом знака
---------------------------------------------------------------------
;sub_sign - процедура вычитания чисел размером 1 байт с учетом знака
;Вход: minuend и deduction - уменьшаемое и вычитаемое.
:Выход: minuend - значение разности.
---------------------------------------------------------------------
.data значения в minuend и deduction нужно внести
N equ 2 :длина в байтах результата в ситуации расширения знака для получения его модуля
minuend db ? -.уменьшаемое
carry db 0 расширение знака
deduction db ? :вычитаемое
.code
sub_sign proc
mov al .deduction
subminuend.al ;оценить результат:
jnc no_carry :нет заема обрабатываем ситуацию заема из старшего разряда - получаем модуль (если нужно)
neg minuend
jmp end_p
no_carry: jns no_sign обрабатываем ситуацию получения отрицательного результата - получаем модуль (если нужно)
neg minuend
jmp end_p
no_sign: jno no_overflow обрабатываем ситуацию переполнения - получаем модуль (если нужно).
расширить результат знаком - получаем модуль (если нужно):
mov carry.0ffh
call calc abs no_overflow:
endjr ret sub_sign endp
Программа учитывает возможный заем из старших разрядов. Вычитание чисел большей размерности (2/4 байта) выполняется аналогично. Необходимо заменить директивы DB на DW/DD и регистр AL на АХ/ЕАХ. Подробности зависимости состояния флагов от результата см. в уроке 8 «Арифметические команды» учебника.
Вычитание чисел размером N байт с учетом знака
---------------------------------------------------------------------
:sub_sign_N - процедура вычитания чисел размером Н байт с учетом знака
;Вход: minuend и deduction - уменьшаемое и вычитаемое. N - длина в байтах.
:Выход: minuend - значение разности.
---------------------------------------------------------------------
.data :значения в minuend и deduction нужно внести
minuenddb ? уменьшаемое
lenjninuend=$-minuend ;длина в байтах уменьшаемого и вычитаемого
carry db 0 расширение знака
deduction db ? ;вычитаемое
.code
sub_sign_N proc
mov cx.lenjninuend
mov si.O @@ml: mov al,deduction[si]
sbb minuend[si].al
inc si
loop @@ml оценить результат:
jnc no_carry :нет заема
обрабатываем ситуацию заема из старшего разряда - получаем модуль (если нужно) N=1en_minuend+1
mov carry.0ffh
call calc_abs
jmp end_p no_carry: jns no_sign Обрабатываем ситуацию получения отрицательного результата -
:получаем модуль (если нужно) N=1en_minuend
call calc_abs
jmp end_p
no_sign: jno no_overflow
обрабатываем ситуацию переполнения - получаем модуль (если нужно) расширить результат знаком - получаем модуль (если нужно): N=1en_minuend+1
mov carry,0ffh
call catc_abs no_overflow: end_p: ret sub_sign_N endp
Описанная процедура вычисляет модуль разности и учитывает возможный заем из старших разрядов. Если вычисления модуля разности не требуется, то закомментируйте строки, содержащие команду CALL calc_abs. Подробности зависимости состояния флагов от результата см. в уроке 8 «Арифметические команды» учебника.
Сегмент данных может быть задан, например, так:
.data :значения в minuend и deduction нужно внести
minuend db 25h,0f4h,0eh уменьшаемое
len_minuend=$-minuend ;длина в сайтах уменьшаемого и вычитаемого
carry db 0 ;расширение знака
deduction db 5h,0f4h,0fh :вычитаемое
Далее при рассмотрении программы деления многобайтных двоичных чисел нам понадобится макрокоманда вычитания с учетом знака чисел размером N байт (порядок следования байт не соответствует порядку следования байтов на процессорах Intel, то есть старший байт находится по младшему адресу). Приведем ее.
Вычитание с учетом знака чисел размером N байт (макрокоманда)
sub_sign_N macro minuend.deduction.N
local cycl.ml
---------------------------------------------------------------------
;sub_sign_N minuend.deduction.N - макрокоманда вычитания
;c учетом знака чисел размером N байт
:Вход: minuend и deduction - уменьшаемое и вычитаемое. N - длина в байтах.
:Порядок следования байт - старший байт по младшему адресу (не Intel).
:Выход: minuend - значение разности.
---------------------------------------------------------------------
push si
mov cl,N
mov si.N-1 cycl: moval .deduction[si]
sbbminuend[si],al : jnc ml
: neg minuend[si] ml: dec si
loop cycl
pop si
endm
Умножение двоичных чисел
В отличие от сложения и вычитания операция умножения реализуется двумя типами команд — учитывающими и не учитывающими знаки операндов.
Умножение чисел размером 1 байт без учета знака
---------------------------------------------------------------------
:mul_unsign.asm - программа умножения чисел размером 1 байт без учета знака. ;Вход: multiplier], и multiplied - множители размером 1 байт. ;Выход: product - значение произведения.
---------------------------------------------------------------------
.data
:значения в multiplier], и multiplied нужно внести
product label word
productj label byte
multiplier! db ? :множитель 1 (младшая часть произведения)
product_h db 0 ;старшая часть произведения
multiplied db ? ;множитель 2
.code
mul_unsign proc
mov al .multiplierl
mul multiplier2 :оценить результат:
jnc по_саггу ;нет переполнения - на no_carry обрабатываем ситуацию переполнения
mov product_h.ah :старшая часть результата no_carry: mov product_l.al ;младшая часть результата
ret
mul_unsign endp main:
call mul_unsign
end main
Здесь все достаточно просто и реализуется средствами самого процессора. Проблема состоит лишь в правильном определении размера результата. Произведение чисел большей размерности (2/4 байта) выполняется аналогично. Необходимо заменить директивы DB на DW/DD, регистр AL на АХ/ЕАХ, регистр АН на DX/EDX.
Умножение чисел размером N и М байт без учета знака
Для умножения чисел размером N и М байт, существует несколько стандартных алгоритмов, описанных в литературе. В этом разделе мы рассмотрим только один из них. В его основе лежит алгоритм умножения неотрицательных целых чисел, предложенный Кнутом.
Умножение N-байтного числа на число размером М байт
ПРОГРАММА mul_unsign_NM
---------------------------------------------------------------------
//mul_unsign_NM - программа на псевдоязыке умножения N-байтного числа
//на число размером М байт
//(порядок - старший байт по младшему адресу (не Intel))
//Вход: U и V - множители размерностью N и М байт соответственно
: Ь=256 - размерность машинного слова.
//Выход: W - произведение размерностью N+M байт.
---------------------------------------------------------------------
ПЕРЕМЕННЫЕ
INT_BYTE u[n]; v[n]; w[n+m]: k=0: INT_WORD b=256: temp_word НАЧ_ПРОГ
ДЛЯ j:=M-l ДО 0 //J изменяется в диапазоне М-1..0
НАЧ_БЛОК_1
//проверка на равенство нулю очередного элемента множителя (не обязательно) ЕСЛИ v[j]==0 TO ПЕРЕЙТИ_НА тб
k:=0: i:=n-l ll\ изменяется в диапазоне N-1..0
ДЛЯ 1:=N-1 ДО О НАЧ_БЛ0К_2
//перемножаем очередные элементы множителей temp_word:=u[i]*v[j]+w[i+j+l]+k
w[i+j+l]:=temp_word MOD b //остаток от деления temp_word\b -> w[i+j+l] k:=temp_word\b //целая часть частного temp_word\b -> k
К0Н_БЛ0К_2 w[j]:=k шб:
КОН БЛОК_1 КОН_ПРОГ
:inul_unsign_NM.asm - программа на ассемблере умножения N-байтного числа на число :размером М байт (порядок - старший байт по младшему адресу (не Intel)).
.data :значения в U и V нужно внести
U db ? ;U-un.i«.UiU() - множитель_1 размерностью N байт
1-S-U :i=N
V db ? ; V"Vm.i_ViV(| - множитель_2 размерностью М байт
j=$-V :j=M
len_product=$-U
;w - результат умножения, длина N+M
W db len_product dup (0) ;1en_product=N+M
k db 0 :перенос 0 < k < 255
b dw lOOh : размер машинного слова
.code
mul_unsign_NM proc
mov bx.j-1 :ml
mov ex, j ;ДЛЯ j:=M-l ДО 0 //J изменяется в диапазоне М-1..0
m2: :НАЧ_БЛОК_1
push ex сложенные циклы
emp v[bx],0 :ЕСЛИ v[j]—0 TO ПЕРЕЙТИ_НА m6
je m6 ;m3
movsi.i-1 :i-0..n-l ;k:=0; 1:41-1 //i изменяется в диапазоне N-1.,0
mov cx.i
movk.O :ДЛЯ i:-N-l ДО О НАЧ_БЛ0К_2 m4: ://перемножаем очередные элементы множителей
mov al,u[s1] :temp_word:-u[i]*v[j]+w[i+j+l]+k
mul byte ptr v[bx]
xor dx.dx
mov dl ,w[bx+si+l]
add ax.dx
xor dx.dx
mov dl , k
add ax.dx :t=(ax) - временная переменная
:w[i+j+l]:=temp_word MOD b //остаток от деления temp_word\b -> w[i+j+l] :k:=temp_word\b //целая часть частного temp_word\b -> k
push dx
xor dx.dx
div b
mov ah.dl
popdx
mov k.al
mov w[bx+si+l].ah :m5 .
dec si
loop m4 ;КОН_БЛ0К_2
moval.k ;w[j]:=k
mov w[bx].al m6: dec bx
pop ex
loop m2 ;КОН_БЛОК_1
ret ;КОН_ПРОГ mul_unsign_NM endp main:
call mul_unsign_NM end main
В отличие от обычного умножения «в столбик» в данном алгоритме сложение частичных произведений выполняется параллельно умножению. Программа производит умножение значений в порядке — старший байт по младшему адресу. Это неестественно для микропроцессоров Intel, поэтому программу необходимо соответствующим образом изменить. Текст измененной процедуры mul_ unsign_NM_I приведен на дискете.
Процедуру умножения чисел без учета знака mul_unsign_NM удобно представить в виде макрокоманды mul_unsign_NM_r u,i ,v, j,w. Это без излишних усложнений сделает ее вызов более универсальным. При последующем рассмотрении программы деления многобайтных двоичных чисел она будет использована нами с большой пользой. Текст макрокоманды приведен на дискете. На дискете также имеется вариант этой макрокоманды mul_unsign_NM u,i ,v, j.WHa случай естественного для микропроцессоров Intel расположения операндов — младший байт по младшему адресу.
Умножение чисел размером 1 байт с учетом знака
;mul_sign.asm - программа умножения чисел размером 1 байт с учетом знака ;Вход: multiplier], и multiplied - множители со знаком размерностью 1 байт. ;Выход: product - значение произведения.
.data значения в multiplier], и multiplied нужно внести
product label word
productj label byte
multiplierl db ? ;множитель 1 (младшая часть произведения)
product_h db 0 :старшая часть произведения
multiplied db ? :множитель 2
.code
mul_sign proc
mov al.multiplierl
imul multiplied :оценить результат:
jnc no_carry :нет переполнения - на no_carry обрабатываем ситуацию переполнения
mov productji.ah :старшая часть результата, знак результата - старший бит product_h no_carry: mov productj,al :младшая часть результата, productji - расширение знвка
ret
mul_sign endp. main:
call mul_sign end main
Аналогично умножению без знака здесь также все достаточно просто и реализуется средствами самого процессора. Проблема та же — правильное определение размера результата. Произведение чисел большей размерности (2/4 байта) выполняется аналогично. Необходимо заменить директивы DB на DW/DD, регистр AL на АХ/ЕАХ, регистр АН на DX/EDX. Более того, в отличие от команды MUL команда IMLJL допускает более гибкое расположение операндов.
Умножение чисел размером N и М байт с учетом знака
Как уже не раз отмечалось, система команд микропроцессора содержит два типа команд умножения — с учетом знаков операнда (IMUL) и без него (MUL). При умножении операндов размером 1/2/4 байта учет знака производится автоматически — по состоянию старших (знаковых) битов. Если умножаются числа размером в большее количество байтов, то для получения правильного результата необходимо учитывать знаковые разряды только старших байтов. В основе программы, реализующей алгоритм умножения чисел размером N и М байт с учетом знака, лежит рассмотренная выше процедура умножения чисел произвольной размерности без учета знака.
Умножение N-байтного числа на число размером М байт с учетом знака
ПРОГРАММА mul_sign_NM
//---------------------------------------------------------
//mul_sign_NM - программа на псевдоязыке умножения N-байтного числа
//на число размером М байт
//(порядок - старший байт по младшему адресу (не Intel)) //
Вход: U и V - множители со знаком размерностью N и М байт соответственно;
//Ь=256 - размерность машинного слова. //Выход: W - модуль (дополнение) произведения размерностью N+M байт.
//---------------------------------------------------------
ПЕРЕМЕННЫЕ
INTJ3YTE u[n]; //множитель 1 размерностью N байт
INT_BYTE v[n]; //:множитель 2 размерностью М байт
INT_BYTE w[n+m]: k=0://перенос 0 < k < 255
INT_BYTE sign=0: //информация о знаке
INT_WORD b=256: temp_word //b - размер машинного слова
НАЧ_ПРОГ
//определим знак результата
ЕСЛИ БИТ_7_БАЙТА((и[0] AND 80h) XOR v[0])==1 TO sign:=1
//результат будет отрицательным //получим модули сомножителей: u:-|u| v:-]v|
w:=mul_unsign_NM() //в этой точке - модуль результата //восстанавливаем знак результата ЕСЛИ sign==0 TO ПЕРЕЙТИ_НА Шт
//для отрицательного результата вычислить дополнение значения w длиной i+j w:=calc_complement_r() //в этой точке - двоичное дополнение результата @йп: КОН_ПРОГ
:mul_sign_NM.asm - программа на ассемблере умножения N-байтного числа :на число размером М байт
;(порядок - старший байт по младшему адресу (не Intel))
.data ;значения в U и V нужно внести
;Помните. что задание отрицательных многобайтных значений в ;сегменте данных должно производиться в дополнительном коде ;(и в порядке байтов - старший байт по младшему адресу)!
U db ? :множитель 1 размерностью N байт
i-$-U
V db ? ;множитель 2 размерностью М байт
J-$-V
len_product=$-U
W db len_product dup (0) результат длиной N+M байт
k db 0 ;перенос О < k < 255
b dw lOOh ;размер машинного слова
sign db 0 информация о знаке
.code
;включить описание процедур calc_complement_r. calc_abs_r. :mul_unsign_NM
mul_sign_NM ргос ;НАЧ_ПРОГ юпределим знак результата
хог ах.ах ; ЕСЛИ БИТ_7_БАЙТА((и[0] AND 80h) XOR v[0])==1 TO sign:=1
mov al.u
and al.80h
xor al.v
bt ax,7
jnc $+7
mov sign.l результат будет отрицательным
lea bx.v ;получим модули сомножителей: u:~|u|; v:=|v|
mov ex.j
call calc_abs_r
1 ea bx, u
mov ex.i
call calc_abs_r ;теперь умножаем
call mul_unsign_NM ;w:=inul_unsign_NM() ;в этой точке - модуль результата ;восстанавливаем знак результата
хог si. si
emp sign.0 :ЕСЛИ sign==0 ТО ПЕРЕЙТИ_НА №т
je @@m ://для отрицательного результата вычислить дополнение значения w длиной i+j
mov ex,i+j ;w:=calc_complement_r(); w[0]:=0-w[0]
lea bx.w
call calc_complement_r ;в этой точке - двоичное дополнение результата @@m: ret ;КОН_ПРОГ
mul_sign_NM endp main:
call mul_sign_NM end main
Процедура mul_sign_NM выполняет умножение с учетом знака исходных значений в порядке байтов — старший байт по младшему адресу. Если вы используете отрицательные значения операндов, тс для правильной работы тестовой программы в сегменте данных их необходимо задать в дополнительном коде.
В данной программе используются две новые процедуры — calc_complement_r и calc_abs_r, вычисляющие соответственно дополнение и модуль числа размером N байт. Подобные процедуры уже были разработаны и введены нами для значений, порядок следования байт которых характерен для микропроцессоров Intel. Чтобы различать эти две пары процедур, процедуры для вычисления дополнения и модуля числа размером байт с порядком следования байтов, отличным от Intel, мы назвали реверсивными.
Вычисление дополнения числа размером N байт (реверсивное)
:calc_complement_r - процедура на ассемблере вычисления дополнения числа размером N байт
:(старший байт по младшему адресу).
;Вход: регистр ВХ - адрес операнда в памяти: регистр СХ - длина операнда. ;Выход: регистр ВХ - адрес дополнения операнда в памяти.
ca1c_complement_r ргос
dec ex
mov si.ex
neg byte ptr [bx][si] дополнение первого байта
cmp byte ptr [bx][si].O :operand=0 - особый случай
jne short $+3
stc установить cf, так как есть перенос
jcxz @@exit_cycl :для однозначного числа
@@cycl:dec si
not byte ptr [bx][si]
adc byte ptr [bx][si],0
loop @@cycl @@exit_cycl: ret calc_complement_r endp
Для значений размерностью 1/2/4 байта дополнение можно получать с помощью одной команды NEG:
neg operand
Дополнение значений N байт вычисляет алгоритм, реализованный в процедуре calc_complement_r. Обратите внимание, что первый байт может быть нулевым, поэтому алгоритм учитывает это обстоятельство. Попытка получить его дополнение с помощью команды NE6 обречена на провал. Флаг CF в этом случае также должен устанавливаться программно. Подумайте, почему?
Вычисление модуля числа размером N байт (реверсивное)
calc_abs_r - процедура на ассемблере вычисления модуля числа размером N байт
:(старший байт по младшему адресу).
:Вход: регистр ВХ - адрес операнда в памяти: регистр СХ - длина операнда. :Выход: регистр ВХ - адрес модуля операнда в памяти.
.code
calc_abs_r proc определим знак операнда
test byte ptr [bx],80h ;проверяем знак operand
jz @@exit :число положительное
call calc_complement_r @@exit: ret calc_abs_r endp
Для вычислений над операндами, порядок следования байтов которых характерен для микропроцессоров Intel, нам придется разработать еще один вариант процедуры умножения значений размерностью в произвольное количество байтов. Псевдокод и соответствующая ему программа на ассемблере mul_sign_NM_I приведены на дискете.
Деление двоичных чисел
Аналогично операции умножения деление реализуется двумя типами команд — учитывающими и не учитывающими знаки операндов. Эти команды накладывают ощутимые ограничения на размерность (а соответственно и на диапазон значений) операндов. Поэтому мы рассмотрим вначале пример стандартного применения команд, после чего займемся реализацией алгоритмов деления чисел произвольной размерности.
Деление без учета знака значения размером 2 байта на значение размером 1 байт
:div_unsign.asm - программа на ассемблере деления без учета знака значения
размером 2 байта на значение размером 1 байт.
:Вход: и - делимое: v - делитель.
;Выход: w - частное, г - остаток.
.data :значения в и и v нужно внести
u dw ? :делимое
v db ? :делитель
w db 0
г db 0
.code
div_unsign proc
mov ax.u
div v сформировать результат:
mov r.ah :остаток
mov w.al :частное
ret
divjjnsign endp , main:
call div_unsign end ma in
Деление чисел большей размерности (4/8 байтов) выполняется аналогично. Необходимо заменить директивы DB на DW/DD, регистр АХ на EAX/EDX: ЕАХ, регистр AL на АХ/ЕАХ, регистр АН на DX/EDX.
Деление с учетом знака значения размером 2 байта на значение размером 1 байт
:div_sign.asm - программа на ассемблере деления с учетом знака значения
;размером 2 байта на значение размером 1 байт.
:Вход: и - делимое; v - делитель.
:Выход: w - частное, г - остаток.
.data значения в и и v нужно внести
и dw ? ;делимое
v db ? ;делитель
w db О
г db О
.code
div_sign proc
mov ax.u
idiv v сформировать результат:
mov г,ah :остаток
mov w.al ;частное
:если нужно получить модуль - уберите знаки комментария : mov cx.l ;длина операнда ; lea bx.w : call calc_abs ;или ; neg w
ret
div_sign endp main:
call div_sign
end main
Деление чисел большей размерности (4/8 байтов) выполняется аналогично. Необходимо заменить директивы DB на DW/DD, регистр АХ на EAX/EDX:EAX, регистр AL на АХ/ЕАХ, регистр АН на DX/EDX.
Деление N-разрядного беззнакового целого на одноразрядное число размером 1 байт
:div_uns1gn_N_1.asm - программа на ассемблере деления без учета знака значения
:размером N байт на значение размером 1 байт.
;Порядок следования байтов - старший байт по младшему адресу (не Intel) :Вход: и - делимое; v - делитель. :Выход: w - частное, г - остаток.
.data значения в и и v нужно внести
u db ? ;делимое
N=$-u :длина в байтах значения и
v db ? :делитель
w db N dup (0)
г dw 0 :остаток
.code
div_unsign_N_lproc
mov г.О
хог si.si ;j»0
mov cx.N
хог dx.dx
хог bx.bx @@ml: movax.256 основание с.с.
mul г результат в dx:ax
mov bl ,u[si]
add ax.bx
div v сформировать результат:
mov w[si].al :частное
shr ax.8
mov г.ах юстаток в г
inc si
1oop @@ml
ret
d i v_uns i gn_N_lendp main:
call div_unsign_N_l
end main
Сегмент данных может быть задан, например, так:
.data значения в и и v нужно внести
u db 5.6.7 :делимое
N=$-u :длина в байтах значения и
v db 15 ;делитель
w db N dup (0)
г dw 0 :остаток
В программе div_unsign_N_l.asm порядок следования байтов делимого неестествен для микропроцессора Intel. Поэтому на дискете приведен вариант программы div_unsign_N_l_I.asm, в котором эта проблема устранена.
Далее при рассмотрении программы деления многобайтных двоичных чисел нам понадобится макрокоманда divunsignN деления N-разрядного беззнакового целого на одноразрядное число размером 1 байт (порядок следования байтов не характерен для процессоров Intel, то есть старший байт находится по младшему адресу). Текст макрокоманды приведен на дискете.
Деление (N+М)-разрядного беззнакового целого на число размером М байт
ПРОГРАММА div_unsign_NM
;----------------------------------------------------------
;div_unsign_NM.asm - программа на ассемблере деления (N+M)-разрядного беззнакового целого на число размером N байт
;(порядок - старший байт по младшему адресу (не Intel))
;Вход: U и V - u=um+n-1..+u1u0 - делимое; v=vn-1…v1v0-
;делитель, m - длина делимого;n - длина делителя; b=256 -
;основание системы счисления.
;Выход: q=qmqm-1…q1q0 - частное, r=rn-1…r1r0 - остаток.
;Ограничения: vn-1№0 OR 0ffh; N>1.
;----------------------------------------------------------
masm
model small,c
.data
;значения в u и v нужно внести
u0 db 0 ;дополнительный старший байт делимого для нормализации
u db 1fh,0c3h,12h,0ffh ;делимое
m=$-u ;длина в байтах значения u
v0 db 0 ;для компенсирующего сложения 0vn-1…v1v0
v db 3fh,50h ;делитель
n=$-v ;длина в байтах значения v
mm=m-n
w db m+1 dup (0) ;для промежуточных вычислений
q db mm dup (0) ;частное
qq dw 0 ;частичное частное ;qq db 0
rr dw 0 ;частичный остаток
r db n dup (0) ;остаток
d db 0
temp dw 0
temp_r db n dup (0)
borrow db 0 ;факт заема на шаге D4
k db 0 ;перенос 0 Ј k < 255
b dw 100h ;размер машинного слова
carry db 0
.stack 256
.486
.code
calc_complement_r proc
dec cx
mov si,cx
neg byte ptr [bx][si] ;дополнение первого байта
cmp byte ptr [bx][si],0 ;operand=0 - особый случай
jne short $+3
stc ;установить cf, так как есть перенос
jcxz @@exit_cycl ;для однозначного числа
@@cycl: dec si
not byte ptr [bx][si]
adc byte ptr [bx][si],0
loop @@cycl
@@exit_cycl: ret
calc_complement_r endp
mul_unsign_NM macro u,i,v,j,w
local m2,m4,m6
push si
;очистим w
push ds
pop es
xor al,al
lea di,w
mov cx,i+j
rep stosb
;m1
mov bx,j-1 ;j=0..m-1
mov cx,j
m2:
push cx ;вложенные циклы
cmp v[bx],0
je m6
;m3
mov si,i-1 ;i=0..n-1
mov cx,i
mov k,0
m4:
mov al,u[si]
mul byte ptr v[bx]
xor dx,dx
mov dl,w[bx+si+1]
add ax,dx
xor dx,dx
mov dl,k
add ax,dx ;t=(ax) ? временная переменная
push dx
xor dx,dx
div b ;t mod b
mov ah,dl
pop dx
mov k,al
mov w[bx+si+1],ah
;m5
dec si
loop m4
mov al,k
mov w[bx],al
m6:
dec bx
pop cx
loop m2
pop si
endm
sub_sign_N macro minuend,deduction,N
local cycl,m1
;старший байт по младшему адресу
push si
mov cl,N
mov si,N-1
cycl: mov al,deduction[si]
sbb minuend[si],al
; jnc m1
; neg minuend[si]
m1: dec si
loop cycl
pop si
endm
add_unsign_N macro carry,summand_1,summand_2,N
local cycl,end_p
mov cl,N
mov si,N-1
cycl: mov al,summand_2[si]
adc summand_1[si],al
dec si
loop cycl
jnc end_p
adc carry,0
end_p: nop
endm
div_sign_N macro u,N,v,w,r
local m1
;старший байт по младшему адресу
mov r,0
lea si,u ;j=0
xor di,di ;j=0
mov cx,N
xor dx,dx
xor bx,bx
m1: mov ax,256 ;основание с.с.
mul word ptr r ;результат в dx:ax
mov bl,[si]
add ax,bx
div v
;сформировать результат:
mov w[di],al ;частное
mov r,ah ;остаток в r
inc si
inc di
loop m1
;если нужно - получим модуль (уберите знаки комментария)
; mov cx,N ;длина операнда
; lea bx,w
; call calc_abs_r
endm
div_unsign_NM proc
;НАЧ_ПРОГ
;//шаг 1 - нормализация:
;D1 - нормализация
;d:=b/(v[n-1]+1)
xor ax,ax
mov dl,v
inc dl ;vn-1+1
mov ax,b
div dl
mov d,al ;d=b/(v1+1)
;u[n+m…0]:=u[n+m-1…0]*d
mul_unsign_NM u,m,d,1,w
cld
push ds
pop es
lea si,w
lea di,u0
mov cx,m+1
rep movsb
;v[n-1…0]:=v[n-1…0]*d
mul_unsign_NM v,n,d,1,w
cld
push ds
pop es
lea si,w+1
lea di,v
mov cx,n
rep movsb
;//шаг 2 - начальная установка j:
;mm:=m-n; j:=mm
;D2:
mov si,0 ;n=0 (? n=n+m)
;D3:
@@m7:
;//шаг 3 - вычислить частичное частное qq :
;qq:=(u[j+n]*b+u[j+n-1]) / v[n-1]
;rr:=(u[j+n]*b+u[j+n-1]) MOD v[n-1]
@@m1: xor ax,ax
mov al,u0[si]
mul b
shl eax,16
shrd eax,edx,16 ;результат умножения в eax
xor edx,edx
mov dl,u0[si+1]
add eax,edx
shld edx,eax,16 ;восстановили пару dx:ax для деления
xor bx,bx
mov bl,v ;v->bx
div bx
mov qq,ax
mov rr,dx
@@m2:
;проверим выполнение неравенства:
;ДЕЛАТЬ ПОКА tf
;НАЧ_БЛОК_1
;ЕСЛИ qq==b OR qq*v[n-2] > b*rr+ u[j+n-1] ТО
;НАЧ_БЛОК_2
;qq:=qq-1
;rr:=rr+v[n-1]
;ЕСЛИ rrіb ТО tf:=FALSE
;КОН_БЛОК_2
;ИНАЧЕ tf:=FALSE
;КОН_БЛОК_1
@@m4:
mov ax,qq
cmp ax,b ;qq<>b
je @@m9 ;на qq=qq-1
;qq*vn-2>b*rr+uj+n-2
mul v+1 ;qq*vn-2
mov temp,ax ;temp=vn-2*qq
xor ax,ax
mov ax,b
mul rr
xor dx,dx
mov dl,u0[si+2]
add ax,dx
cmp temp,ax ;qq*vn-2 > b*rr+uj+n-2
jna @@m8
@@m9:
dec qq
xor ax,ax
mov al,v
add rr,ax
jmp @@m4
@@m8:
@@m3:
;D4
;//шаг 4 - умножить и вычесть:
;u[j+n…j]:=u[j+n…j]-qq*v[n-1…0]
mul_unsign_NM v,n,qq,1,w
mov bx,si
push si
sub_sign_N u0[bx],w,<n+1> ;v<->w
;ЕСЛИ u[j+n…j]<0 ТО ;запоминаем факт заема, получаем дополнение
;НАЧ_БЛОК_3
;borrow:=1
;u[j+n…j]:=calc_complement_r(u[j+n…j])
;КОН_БЛОК_3
jnc @@m5 ;переход, если нет заема (результат положительный)
mov borrow,1 ;запоминаем факт заема, получаем дополнение
pop si
lea bx,u0[si]
mov cx,n+1
call calc_complement_r
;D5
;//шаг 5 - проверка остатка:
;q[j]:=qq
@@m5: mov ax,qq
mov q[si],al
;ЕСЛИ borrow<>1 ТО
cmp borrow,1 ;был заем на шаге D4 ??
jne @@m6
;НАЧ_БЛОК_4
;//шаг 6 - компенсирующее сложение:
;q[j]:= q[j]-1
;u[j+n…j]:=u[j+n…j]+v[n-1…0]
;КОН_БЛОК_4
;D6 - компенсирующее сложение
mov borrow,0 ;сбросим факт заема
dec q[si]
mov bx,si
push si
add_unsign_N carry,u0[bx],v0,<n+1> ;перенос не нужен
;D7
;//шаг 7 - цикл по j:
;j:=j-1
@@m6: pop si
inc si
;ЕСЛИ jі0 ТО ПЕРЕЙТИ_НА @@m7
cmp si,mm
jle @@m7
;D8 - денормализация
;//шаг 8 - денормализация:
;//вычислим остаток:
;r[n-1…0]:=u[n-1…0]/d
mov bx,si
div_sign_N u0[bx],N,d,r,temp_r
ret
;//q[m…0] - частное, r[n-1…0] ? астаток
;КОН_ПРОГ
div_unsign_NM endp
main:
mov dx,@data
mov ds,dx
call div_unsign_NM
mov ax,4c00h
int 21h
end main
Программа не работает, если первый байт делителя равен 0f fh. Сам алгоритм не изменяется, а проблема устраняется просто — необходимо лишь в нужных местах программы поменять разрядность операндов.
Порядок следования байтов делимого неестествен для микропроцессора Intel. Программу деления многобайтных двоичных чисел с порядком следования байтов «младший байт по младшему адресу» оставляем вам в качестве упражнения.
Двоично-десятичные числа (BCD-числа)
Работай постоянно, не почитай работу для себя бедствием
или бременем и не желай себе за это похвалы и участия.
Общее благо - вот чего ты должен желать.
Марк Аврелий
Понятие о BCD-числах и элементарных действиях с ними приведены в уроке 8 «Арифметические команды» учебника. В отличие от действий с двоичными числами работа с BCD-числами в микропроцессоре реализована косвенно. В его системе команд нет инструкций, которые непосредственно выполняют основные арифметические действия над BCD-числами в том виде, как это делается для двоичных операндов. Тем более нет средств, которые каким-то образом учитывали бы знак. Все это должен делать сам программист. Ниже приведены макрокоманды, которые выполняют базовые арифметические операции над BCD-числами различной разрядности.
Неупакованные BCD-числа
Перед тем как приступать к работе с BCD-числами, необходимо договориться о том, как будут представляться BCD-числа в оперативной памяти — старший разряд BCD-числа по старшему адресу или старший разряд BCD-числа по младшему адресу. Изменить фрагмент программы для поддержки того или иного способа представления чисел не представляет особого труда. Поэтому для однозначности рассуждений выберем естественный для микропроцессоров Intel порядок следования байтов — младший байт по младшему адресу.
Сложение неупакованных BCD-чисел (макрокоманда)
add_bcdmacro summand_i.1en_l,summand_2.1 en_2,sum local ml.m2.m3
:add_bcd summand_1.1en_l,summand_2.1en_2.sum - макрокоманда
:сложения неупакованных BCD-чисел размером 1еп_1 и len_2
:байт и помещение результата в sum.
:Вход: summand_i и summand_2 - адреса младших байтов
хлагаемых; 1еп_1 и 1еп__2 - длины слагаемых в байтах.
;Выход: sum - адрес младшего байта поля суммы. Желательно.
:чтобы это поле имело длину на единицу больше, чем длина
:самого длинного слагаемого.
;Порядок следования байт - младший байт по младшему адресу (Intel).
push si
push bx
mov ax.len_l
cmp ax.len_2
jna m2
mov cx,len_l ;длина большего для сложения (см. ниже)
push ex
mov cx,len_2 ;длина меньшего для сложения (см. ниже)
push ex
mov cx.ax
lea bx.summand_l :адрес большего источника для сложения
lea si,summand_2 :адрес меньшего источника для movsb
jmp m3
т2: mov сх.1еп_2 :длина большего для сложения (см. ниже)
push ex
mov cx.len_l ;длина меньшего для сложения (см. ниже)
push ex
mov cx.len_2
lea bx.summand_2 ;адрес большего источника для сложения
lea si.summand_l :адрес меньшего источника для movsb m3: заполняем sum нулями - длина определена выше:
eld
хог al.al
lea di. sum rep stosb ;пересылка меньшего (по длине) BCD-числа в sum:
eld
push ds
pop es
lea di. sum :адрес источника см. выше
pop сх ;длина была определена выше и соотв. меньшему ВСО-числу rep movsb
pop сх ;дикл по большему
хог si,si
ml: mov al.[bx][si]
adc al, sum[si]
aaa
mov sum[si].al
inc si
loop ml
adc sum[si].O
pop bx
pop si
endm
Макрокоманда обрабатывает байты, исходя из предположения, что младший байт слагаемых находится по младшему адресу. Слагаемые необязательно имеют одинаковую длину, но сумма должна иметь размер поля на единицу больше, чем длина самого длинного слагаемого. В начале процесса сложения в поле результата помещается меньшее (по длине) слагаемое.
Нам понадобится и другой вариант этой команды — addbedr, который обрабатывает операнды с порядком следования байтов — старший байт по младшему адресу.
Вычитание неупакованных BCD-чисел (макрокоманда)
sub_bcdmacro minuend.lenjn. deduction.len_d. difference local temp.ml.m2.exit_m
:sub_bcd minuend".len_m.deduction,len_d.difference -макрокоманда вычитания неупакованных BCD-чисел размером ;len_m и len_d байт и помещение результата в difference. ;Вход: minuend и deduction - адреса младших байтов уменьшаемого и вычитаемого: len_m и len_d - длины уменьшаемого и вычитаемого в байтах.
;Выход: difference - адрес младшего байта поля разности. :Длина поля difference должна быть не меньше длины :уменьшаемого.
;Порядок следования байт - младший байт по младшему адресу (Intel).
push si
.¦копируем уменьшаемое в difference:
push ds
pop es
eld
lea si.minuend
lea di.difference
mov cx.lenjn
push ex rep movsb
jmp ml ;копируем вычитаемое во врем, область temp:
temp db len_m dup (0)
ml: lea si .deduction
lea di,cs:temp
mov cx.len_d
push cs
pop es rep movsb
xor si.si
pop ex
m2: mov al,minuend[si]
sbb al,cs:temp[si]
aas
mov difference[si].al
inc si
1oop m2
jc m3 :на обработку заема из старшего разряда
jmp exit_m m3: пор exitjn:
pop si
end
Макрокоманда учитывает возможный заем из старших разрядов.
В дальнейшем нам понадобится и другой вариант этой команды — sub_bcd_r, который обрабатывает операнды с порядком следования байтов — старший байт по младшему адресу. Он приведен на дискете.
Умножение неупакованных BCD-чисел (макрокоманда)
.data
k db 0 :перенос 0 < к < 255
b dw 10 ;основание системы счисления
.code
mul_bcdmacro u.i.v.j.w *
local m2.m4.m6
:mul_bcd u.i.v.j.w - макрокоманда умножения неупакованных
:BCD-чисел u и v размером i и j байт и помещение результата
:в w.
;Вход: и - адрес первого множителя; i - длина u: v - адрес
;второго множителя: j - длина v: w - адрес области
:размерностью i+j байт, куда необходимо поместить
:произведение: Ь=256 - размерность машинного слова.
:Выход: w - произведение размерностью i+j байт.
:Порядок следования байтов - младший байт по младшему адресу
:(Intel).
:сохраним регистры
push si
:очистим w
eld
push ds
pop es
xor al.al
lea di ,w
mov ex,i+j
rep stosb
xor bx.bx ;j=0..m-l
mov CX.j
m2: push ex : вложенные циклы
CiTlp v[bx].O '
je тб
:m3
xor si,si :1=0..n-1
mov cx.i
mov k.O
m4: mov al,u[si]
mul v[bx]
xor dx.dx
mov dl.w[bx+si]
add ax.dx
xor dx.dx
mov dl ,k
add ax.dx ;t-(ax) -- временная переменная
:корректируем результат - (ап)-цифра переноса: ;(а1)=результат
aam
mov k.ah
mov w[bx+si].al
:m5
inc si
loop m4
mov al.k
mov w[bx+si],al
m6: inc bx
pop ex
loop m2
pop si
endm
Нам понадобится и другой вариант этой команды — mul_bcd_r, который обрабатывает операнды с порядком следования байтов — старший байт по младшему адресу.
Деление N-разрядного беззнакового целого BCD-числа на одноразрядное BCD-число размером 1 байт (макрокоманда)
div_bcd_l_r macro u.N.v.w.r local ml
:div_bcd_l_r u.N.v.w.r - деление N-разрядного беззнакового целого BCD-числа
;на одноразрядное BCD-число размером 1 байт. :Вход: и - делимое; N - длина делимого, v - делитель. :Выход: w - частное, г - остаток. :Порядок следования байтов - старший байт по младшему адресу (не Intel) (!).
mov г.О
lea si.u ;j=0
хог di.di :j=0
mov cx.N
xor dx.dx
xor bx.bx
ml: mov ah,г
mov al.[si]
aaJ
div v сформировать результат:
mov w[di].al ;частное
mov r.ah .-остаток в г
inc si
inc di
loop ml
:если нужно - получим модуль (уберите знаки комментария)
: mov cx.N ;длина операнда
: lea bx.w
; call calc_abs_r
endm
Деление неупакованных BCD-чисел
:div_bcd_NM_r.asm - деление неупакованных BCD-чисел и и v размером n+m и п байт.
;Вход: и-и^гиз-.и,^,, - делимое: v=v1v2...vn - делитель. Ь=25б - основание системы счисления.
;Выход: q™q1q2-.qm - частное. r=rir2...rn - остаток,
:Порядок следования байт - старший байт по младшему адресу (не Intel) (!).
.data значения в и и v нужно внести
uO db 0 дополнительный байт для нормализации
u db 1,0.3.5,9,4,6 :делимое
m=$-u :длина в байтах значения и
vO db 0 :для сложения OvjV2..vn
v do 5.9.1 :делитель
n=$-v :длина в байтах значения v
ГПП1=П1-П
w db m+1 ctup (0) :для промежуточных вычислений q db mm dup (0) :частное qq db 0
г db n dup (0) :остаток
b dw 10 юснование системы счисления
d db 0
temp dw 0
temp_r db n dup (0)
borrow db 0 :факт заема на шаге D4
k db 0 ;перенос 0 =< k < 255
carry db 0
.code
:вставить описание макрокоманд calc_complement_r. mul_bcd_r. sub_bcd_r. add_bcd_r. :div_bcd_l_r
div_bcd_NM_r proc ;D1 - нормализация
xor ax.ax
mov dl.v
inc dl :vl+l
mov ax.b
div dl
mov d.al :d=b/(v1+l)
mul_bcd_r u.m.d.l.w
eld
push ds
pop es
lea si.w
lea di.uO
mov cx.m+1 rep movsb
mul_bcd_r v.n.d.l.w
eld
push ds
pop es
lea si.w+1
lea di.v
mov ex,n rep movsb :D2:
mov si.O ;n=0 :D3: @@m7: moval.uO[si]
emp v,al
jne @@ml
mov qq.9 :qq=b-l
jmp @@m2
(<t@ml: xor ax,ax
mov al.uO[si]
mul b
xor dx.dx
mov dl,uO[si+l]
add ax.dx
mov bl.v ;v->bx divbl
mov qq.al
@@m2: :проверим выполнение неравенства:
@@m4: mul v+1
mov temp. ax: taiip=v2*qq
xor ax.ax
mov al ,uO[si]
mul b
xor edx.edx
mov dl.uO[si+l] add dx.ax
mov al.qq
mul v :eax=qq*vl
sub dx,ax
xchg dx.ax
mul b
xor bx.bx
mov bl.uO[si+2]
add ax.bx
cmp temp,ax
jna (a@m3
dec qq
mov al.qq
jmp @@m4
@@m3: : D4
mul_bcd_r v.n.qq.l.w
mov bx.si
push si
sub_bcd_r uO[bx].<n+l>.w,<n+l>,uO[bx] ;v<->w
jnc @@m5 :переход, если нет заема (результат положительный)
mov borrow.1 ;запоминаем факт заема, получаем дополнение
pop si ;D5
@@m5: moval.qq
mov q[si].al
cmp borrow.1 :был заем на шаге D4 ??
jne @@m6 :D6 - компенсирующее сложение
mov borrow.0 :сбросин факт заема
dec q[si]
mov bx.si
push si
add_bcd_r uO[bx].<n+l>.vO,<n+l>,uO ;перенос не нужен :D7
@@m6: pop si
inc si
cmp si.mm
jle @@m7 :D8 - денормализация
mov bx.si
div_bcd_l_r uO[bx],N,d.r.temp_r
ret
div_bcd_NM_r endp *
main:
call div_bcd_NM_r end main
Упакованные BCD-числа
В отличие от неупакованных BCD-чисел, разработчики команд микропроцессора Intel весьма сдержанно отнеслись к проблеме обработки упакованных BCD-чисел. Существуют только две команды — DAA и DAS, которые поддерживают процесс сложения и вычитания упакованных BCD-чисел. Умножение и деление этих чисел не поддерживается вовсе. По этой причине при необходимости выполнения арифметических вычислений с упакованными BCD-числами есть смысл предварительно преобразовывать их в неупакованное представление, выполнять необходимые действия, результат которых конвертировать (если нужно) обратно в упакованный вид. Так как действия по преобразованию не являются основными в процессе вычислений, то желательно, чтобы они были максимально быстрыми. Можно предложить много вариантов подобного преобразования. Рассмотрим один из них.
Преобразование упакованного BCD-числа размером N байт в неупакованное BCD-число (макрокоманда)
BCD_PACK_TO_UNPACK macro PACK.N. UNPACK local cycl
;BCD_PACK_TO_UNPACK PACK,N.UNPACK - макрокоманда преобразования упакованного
BCD-числа размером N байт в неупакованное BCD-число размером N*2 байт ;Порядок следования байтов - младший байт по младшему адресу
:(Intel).
сохраняем регистры ...
push ds
pop es
mov ecx.N
eld ;порядок обработки BCD-цифр - начиная с младшей
lea edi.UNPACK
lea esi.PACK cycl: xorax.ax
lodsb ;загрузить очередные 2 упакованные BCD-цифры из PACK в al
гог ах.4
гог ah.4
stosw
loop cycl восстанавливаем регистры ...
endm
Преобразование неупакованного BCD-числа размером N байт в упакованное BCD-число (макрокоманда)
ВС D_U N РАС К_ТО_РАСК macro UNPACK.N,PACK local cycl
:BCD_UNPACK_TO_PACK UNPACK,N.PACK - макрокоманда преобразования неупакованного
iBCD-числа"размером N байт в упакованное BCD-число. ;Порядок следования байтов - младший байт по младшему адресу ;(Intel).
сохраняем регистры ... push ds
pop es
mov ecx.N
:определяем N/2 (размерность PACK) - если нечетное, юкругляем в большую сторону
shr ecx.l ;делим на 2
bt есх.О
jc $+4
setc Ы
inc есх добавляем 1 для округления в больщую сторону предыдущие три команды можно заменить одной: adcecx.O :теперь в есх правильное значение сч. цикла в соответствии с размерностью UNPACK
eld шорядок обработки BCD-цифр - начиная с младшей
lea edi.PACK
lea esi.UNPACK cycl: xorax.ax загрузить очередные 2 неупакованные BCD-цифры из UNPACK в ах
lodsw
rol ah,4
rol ax,4
stosb
loop cycl
emp . 0
jne $+7
and byte ptr [edi-1].OfOh восстанавливаем регистры ...
endm
Генерация последовательности случайных чисел
Знание некоторых принципов нередко
возмещает незнание
некоторых фактов.
Гельвецкий
Важный класс вычислительных алгоритмов, востребованных на практике, — алгоритмы генерации последовательности случайных величин. По определению, последовательностью случайных чисел является последовательно формируемый массив значений, в котором каждый очередной элемент получен вне всякой связи с другими его элементами и появление этого элемента возможно с вероятностью, подчиненной некоторому закону распределения. К примеру, если появление любого числа в этой последовательности равновероятно, то говорят о равномерном законе распределения случайных чисел.
На практике в большинстве случаев применяются программные методы получения случайных чисел. На самом дел'е случайные последовательности, получаемые по некоторому алгоритму, являются псевдослучайными. Это происходит из-за того, что связь между значениями в последовательности, получаемой программным путем, обычно все-таки существует. Данное обстоятельство приводит к тому, что на каком-то этапе генерируемая последовательность чисел начинает повторяться — «входит в период». Рассмотрим несколько наиболее известных
и пригодных для практического использования программных методов генерации псевдослучайных величин (все же, понимая смысл выражения, будем по привычке и для удобства называть их случайными).
Конгруэнтный метод генерации последовательности случайных чисел
Конгруэнтный метод генерации последовательности случайных чисел получил широкое распространение. Он описан во многих источниках, но конкретных рекомендаций по его использованию на платформе Intel автор не встретил. Попытаемся устранить этот недостаток.
В основе этого метода генерации последовательности случайных чисел лежит понятие конгруэнтности. По определению, два числа А и В конгруэнтны (сравнимы) по модулю М в случае, если существует число К, при котором А-В=КМ, то есть если разность А-В делится на М, и числа А и В дают одинаковые остатки от деления на М. Например, числа 85 и 5 конгруэнтны по модулю 10, так как при делении на 10 дают остаток 5 (при К=1). В соответствии с этим методом каждое число в этой последовательности получается исходя из следующего соотношения:
Хn+1=(аХn+с) mod m, где n > 0. (1)
При задании начального значения Хо, констант а и с данное соотношение однозначно определяет последовательность целых чисел X,, составленную из остатков от деления на m предыдущих членов последовательности, в соответствии с соотношением (1). Величина этих чисел не будет превышать значение т. Если каждое число этой последовательности разделить на т, то получится последовательность случайных чисел из интервала 0.1.1'. Но не спешите подставлять в это соотношение какие-либо значения. Основная трудность при использовании этого метода — подбор компонентов формулы. В зависимости от значения с различают два вида конгруэнтного метода — мультипликативный (с=0) и смешанный (с не равно 0).
Для простоты изложения будем генерировать небольшие по величине случайные числа. Это дает возможность легко отслеживать особенности работы рассматриваемых алгоритмов с использованием стандартной возможности перенаправления ввода-вывода. Для этого необходимо, чтобы текст программы содержал строки:
movdl .ah
mov ah.02
int 21h
Запуск программы производиться командной строкой вида:
prog.exe > p.txt
При этом создается файл p.txt, в который и выводятся результаты работы программы. Если не использовать этой возможности, то вывод будет производиться на экран, что не очень удобно для последующего анализа получающейся последовательности случайных чисел. Более подробно о возможностях работы с файлами и экраном читайте материал в главах 5 и 7, посвященных работе с файлами и консолью из программ на языке ассемблера.
Большинство представленных ниже программ функционируют в бесконечном цикле, с тем, чтобы можно было изучать периодичность последовательности, создаваемой по тому или иному методу генерации случайных чисел. Поэтому для окончания работы программы ее необходимо завершить принудительно (при работе в Windows для этого можно просто закрыть окно DOS). В результате работы программы будет создан файл p.txt, который можно открыть в любом редакторе, допускающем просмотр файлов в шестнадцатеричном виде (например, встроенном редакторе файлового менеджера Windows Commander).
Для увеличения диапазона необходимо внести соответствующие, не принципиальные с точки зрения алгоритма, изменения в тексты программ.
Мультипликативный конгруэнтный метод генерации последовательности случайных чисел
Мультипликативный конгруэнтный метод задает последовательность неотрицательных целых чисел Xj (Xj<m), получаемых по формуле:
Хn+1=аХn(mod m). (2)
На значения накладываются ограничения:
Хо — нечетно; а=52р+1 (р=0, 1, 2, ...) или a=2m+3 (m=3, 4, 5, ...) — обе эти записи означают, что младшая цифра а при представлении а в восьмеричной системе счисления должна быть равна 3 или 5 (проще говоря, остаток от деления а/8 должен быть равен 3 или 5); m=2 (1>4).При соблюдении этих ограничений, длина периода будет равна m/4.
:randjnult_cong_l.asm - датчик линейной (мультипликативной) :конгруэнтной последовательности случайных чисел (с=0).
:Вход: Хо. a, m - в соответствии с указанными выше ограничениями. .-Выход: dl - значение очередного случайного числа.
.data
in db 128
a db 11
х db 3 начальное значение
.code
;первое число в последовательности х-3
cycl: moval.x вычисляем очередное случайное число Х=(а*Х) mod in
mul а :а*х в ah:al
divm ;в ah случайное число
mov x.ah ;вывод в файл - командная строка rand_mu1t_cong.exe > p.txt
mov dl .ah
mov ah.02
nit г»
jmp cyc1
end cycl:
Если m является степенью 2, как в данном случае, то вместо команды DIV мож-, но использовать две команды сдвига.
;----------------------------------------------------------
;rand_mult_cong_2.asm - датчик линейной (мультипликативной) конгруэнтной последовательности
;случайных чисел (c=0).
;Вход: X0, a, m - в соответствие с указанными выше ограничениями.
;Выход: dl - значение очередного случайного числа.
;----------------------------------------------------------
masm
model small
.486
.data
m db 128 ;128=27
a db 11
x db 3 ;начальное значение
.stack 256
.486
.code
main:
mov dx,@data
mov ds,dx
xor dx,dx
mov cl,7 ;значение степени m=27 в cl
;первое число в последовательности x=3
cycl:
;вычисляем очередное случайное число X=(a*X) mod m
mov al,x
mul a ;a*x в ah:al
shrd ax,ax,cl
xor al,al
rol ax,cl ;в al случайное число
;вывод в файл - командная строка rand_mult_cong.exe > p.txt
mov x,al
mov dl,al
mov ah,02
int 21h
jmp cycl
end_cycl:
mov ax,4c00h
int 21h
end main
Используя эти программы, можно получить последовательность случайных чисел, содержащую 32 значения — это ее период. Чтобы увеличить период, необходимо каким-либо способом сгенерировать значения а или х, удовлетворяющие приведенным выше ограничениям. Так, значение а можно вычислить, используя фрагмент:
.data
:.........
divider db 8
.code
вычисляем а исходя из соотношения:
:а mod 8=5
:одним из способов получить значение а (т > а)
удовлетворяем условию a mod 8 = 5
m2: mov al .a
xor ah,ah
div divider
cmp ah,5 :остаток 5?
je ml
cmp ah,3 :остаток 3?
je ml
inc a
jmp m2 ml: ;теперь а найдено до конца
Изменить (увеличить) период можно, корректируя значение т, для чего необходимо будет исправить соответствующие команды в программах rand_mult_ cong_l.asm и rand_mult_cong_2.asm, ориентированные на определенную разрядность регистров. Существует другая возможность увеличения периода — использование смешанного конгруэ}1т)юго метода генерации последовательности случайных чисел.
Смешанный конгруэнтный метод генерации последовательности случайных чисел
Соотношение смешанного конгруэнтного метода выглядит так: Xn+1=(aXn+c) mod m, где n > 0.
При правильном подборе начальных значений элементов кроме увеличения периода последовательности случайных чисел уменьшается корреляция (зависимость) получаемых случайных чисел.
На значения накладываются ограничения:
Х0>0; а=21+1, где 1>=2; с>0 взаимно просто с m (это выполнимо, если с — нечетно, а т=2р, где (р>=2) m=2р (р>=2) и т кратно 4. :rand_mix_cong_l.asm - датчик линейной (смешанной)
:конгруэнтной последовательности случайных чисел (с>0).
:Вход: Хо. а. с. m - в соответствии с указанными выше
ограничениями.
:Выход: dl - значение очередного случайного числа.
.data
m db 128 ; 128=27
a db 9
х db 3 начальное значение
с dw 3
.code
mov cl.7 :значение степени m=27 в cl ;первое число в последовательности х=3 cycl: вычисляем очередное случайное число Х=(а*Х) mod m
mov al.x
mul a :a*x в ah:al
add ax,с
shrd ax.ax.cl
xor al.al
rol ax.cl :b al случайное число :вывод в файл - командная строка rand_mult_cong.exe > p.txt
end_cycl:
Величина периода случайной последовательности, получаемой с помощью данной программы, составляет 128 значений. Сегмент кода программы rand_mix_ cong_1.asm можно оформить в виде процедуры. Начальное значение Хо можно выбирать двумя способами: задавать константой в программе или генерировать случайным образом. В последнем случае можно использовать такты системного таймера, как в следующей макрокоманде:
rCMOS macro
макрокоманда чтения значений CMOS
:на входе: al адрес ячейки, значение которой читаем
:на входе-выходе: al - прочтенное значение
out 70h,al
хог ах,ах :вводим в регистр AL из порта значение ячейки cmos
in al.71h
endm .code
:получить значение секунд из CMOS для x_start mov al.00 rCMOS mov x.al :x=x_start
Таким способом можно получить начальное значение из диапазона 0..59. Для получения большего по величине начального значения можно использовать величину размером 32 бита из области данных BIOS по адресу 0040:006с. Здесь содержится счетчик прерываний от таймера. Извлечь это значение можно, используя следующий программный фрагмент:
push ds
push 40h
pop ds
mov eax.dword ptr ds:006ch
popds
Заменяя команду MOV командами MOV AX,word ptr ds:006ch или MOV AL, byte ptr ds:006ch, можно использовать младшие 8 или 16 бит значения из этой области BIOS. Команда MOV AL, byte ptr ds:006ch позволяет случайным образом получить в регистре AL значение из диапазона 00.. f fh.
Попытки создать программный датчик случайных чисел без опоры на какую-либо теорию обречены на провал. Рассмотрим еще несколько способов генерации случайных чисел.
Аддитивный генератор случайных чисел
Генератор, формирующий очередное случайное число в соответствии с отношением (3), называется аддитивным:
Xn+1=(Xn+Xn-k) mod m. (3)
В трехтомнике Кнута [5] обсуждаются подобные генераторы и рекомендован следующий вариант формулы (3):
Xn+1=(Xn-24+Xn-55) mod m.(4)
Здесь n > 55, m=21, Хо, ..., Х54 — произвольные числа, среди которых есть и нечетные. При этих условиях длина периода последовательности равна 21-1 (255-1).
Для генерации первых 55 случайных чисел можно использовать один из рассмотренных выше генераторов. Возьмем датчик линейной (смешанной) конгруэнтной последовательности случайных чисел (с > 0).
;rand_add.asm - аддитивный генератор случайных чисел.
:Вход: :Х0. а. с. m ;
случайная последовательность длиной 55 значений, получаемая с помощью
программы генерации высокослучайных двоичных наборов (см. rand_mix_cong_1.asm); :N=700 - количество элементов в последовательности + 1; :L=7 - значение степени т=27. ¦.Выход: dl - значение очередного случайного числа.
.data
N=700 количество элементов в последовательности + 1
L=7 :L - значение степени т=2
т db 128 ;128=27
mm dw 256 ; 256=28
a db 9
с dw 3
;массив значений х (начальное значение х=3) длиной N+1
х db 3, N dup (Offh)
;.........
.code
:далее фрагменты из rand_mix_cong_l.asm.
хог si,si
mov ecx.54 :счетчик цикла для формирования начальной последовательности
:первое число в последовательности х=3
mov al ,x
cycl: вычисляем очередное случайное число Х=(а*Х) mod m
mul a ;а*х в ah:al
add ax.с
shrd ax.ax.L:L - значение степени т=27
хог al.al
rol ax.L ;в al случайное число
:вывод в массив х и файл - командная строка rand_mult_cong.exe > p.txt
i nc si
mov x[si].al
mov dl.al
mov ah. 02
int 21h
loop cycl
:далее продолжаем формирование случайной последовательности, но уже аддитивным методом
mov ecx,N-55
cycl 2: incsi
хог dx.dx
mov al.x[si-24]
mov dl.x[si-55]
add ax.dx
хог dx.dx
div mm
mov x[si].dl
mov ah.02
int 21h
loop eye 12
exit:
Судя по результатам, этот метод достаточно хорош. В частности, он неплох тем, что позволяет задавать длину последовательности без оглядки на значение т.
Следующий рассматриваемый нами датчик можно использовать в программах на языке ассемблера для получения случайной последовательности 0 и 1.
Программа генерации высокослучайных двоичных наборов
Для процесса генерации требуются два значения одинаковой размерности — Y и С. Значение Y будет первым в последовательности случайных чисел. Значение С играет роль маски, в соответствии с которой впоследствии будет производиться операция «исключающее ИЛИ». Генерация очередного случайного числа происходит в два этапа. На первом этапе значение Y сдвигается влево на один разряд. При этом нас интересует содержимое выдвинутого бита. Его значением устанавливается флаг eflags.cf. На втором этапе, если cf=1, то корректируем значение Y= =Y XOR С и сохраняем Y; в противном случае сохраняем сдвинутое значение в качестве очередного числа последовательности.
:rand_bin_1.asm - программа генерации высокослучайных двоичных наборов
:(сокращенный вариант).
:Вход: у. с - в соответствии с указанными выше ограничениями.
:Выход: dl - значение очередного случайного числа.
.data
Y db 35h : Obh
С db 33h :03h
. code
cycl: shl Y.I
jnc ml
mov al ,Y
xor al ,C
mov Y.al ml: :вывод на экран (в файл - командная строка rand_bih.exe > p.txt)
jmp cycl end_cycl:
Содержимое файла, в который перенаправлен вывод программы, показывает, что период последовательности достаточно удовлетворительный (при удачном подборе Y и С). Для того чтобы получить случайную последовательность 0 и 1, необходимо на каждой итерации выделять младший или старший бит очередного значения. Доработаем программу rand_bin_1.asm, чтобы продемонстрировать этот прием.
:rand_bin_2.asm - программа генерации высокослучайных двоичных наборов (полный вариант).
:Вход: у. с - в соответствии с указанными выше ограничениями.
;Выход: dl - значение очередного случайного числа.
.data
Y db 35h :0bh
С db 33h ;03h
.code
: получаем очередное значение Y
push ds
push 40h
pop ds
mov eax.dword ptr ds:006ch
pop ds
mov Y.al
xor dl.dl
mov ecx,8 Нормируем случайные 8-ми битовые наборы в регистре DL cyct: shl Y.I
jnc ml
mov a 1. Y
xor al.C
mov Y.al
jmp $+5 ;на shrd
ml: mov al ,Y
shr al.l
rcl dl.l
loop cycl
:вывод на экран (в файл - командная строка rand_bin.exe > p.txt) очередного значения
exit:
Этот датчик хорош, когда его используют для получения одиночных случайных значений, а не всей последовательности сразу. Поэтому в этой программе отсутствует цикл, характерный для предыдущих программных датчиков, и ее удобно оформить в виде процедуры или макрокоманды.
В заключение данной темы — высказывание Джорджа Марсальи, которое приводит Кнут : «Генератор случайных чисел во многом подобен сексу: когда он хорош — это прекрасно, когда он плох, все равно приятно». Возможно, экспериментируя с примерами данного раздела, вы испытали подобное чувство.
Оценка качества последовательности производится по определенным критериям, подробное рассмотрение которых не является предметом данной книги, но все же требует упоминания. В большинстве случаев для быстрой оценки качества работы генератора случайной последовательности достаточно использовать следующие критерии.
Длина периода и длина апериодичности. Под длиной периода понимается длина максимальной, не содержащей самой себя, числовой цепочки в последовательности случайных чисел. Длина апериодичности — длина подинтервала последовательности случайных чисел, в пределах которого не встречаются одинаковые значения.
Равномерность последовательности псевдослучайных чисел. Этот критерий означает вероятность попадания значений, генерируемых датчиком случайных чисел, в каждый из m подинтервалов, на которые можно разбить весь интервал значений, генерируемых данным датчиком случайных чисел.
Стохастичность последовательности псевдослучайных чисел. Этот критерий означает определение вероятности появления единиц (нулей) в определенных п разрядах генерируемых датчиком случайных чисел.
Независимость элементов псевдослучайной последовательности. Этот критерий определяет степень корреляции (зависимости) двух случайных величин в сгенерированной последовательности. При проведении оценки по этому критерию можно рассматривать любые, а не только рядом стоящие случайные величины последовательности.
Более подробную информацию о подходах к оценке случайных последовательностей можно получить в литературе.
