Умножение чисел размером 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