Сборник по задачам и примерам Assembler

       

Умножение чисел размером N и М байт без учета знака



Умножение чисел размером 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 расположения операндов — младший байт по младшему адресу.


Содержание раздела