File Archive

 
Output of file : CHAP13.DOC contained in archive : ASMTUT3.ZIP




129
CHAPTER 13 - MULTIPLE WORD ARITHMETIC II


We have just done multiple word addition and subtraction, which
are easy. Now we have multiplication and division. We are going
to multiply and divide long numbers by a one word (2 byte)
number. Multiplying multiple-word numbers by multiple-word
numbers is complex and time consuming but can be done. Dividing
by a multiple-word number is an entirely different ballgame.{1}

We'll do unsigned numbers first, then in a later chapter add the
code we need for signed numbers. The core routine is the same.


UNSIGNED MULTIPLICATION

If you multiply an n digit number by an m digit number, there is
a possibility of n+m digits in the result. 863 is 3 digits, 4975
is 4 digits, 863 X 4975 = 4,293,425 is 7 digits = 4 + 3. We will
be multiplying an 8 byte number by a 2 byte number, so we'll need
10 bytes for the possible maximum result. Here's the code:

; - - - - - - - - ENTER DATA BELOW THIS LINE
multiplicand dq ?
multiplier dw ?
result db 10 dup (?)

; - - - - - - - - ENTER DATA ABOVE THIS LINE

; - - - - - - - - ENTER CODE BELOW THIS LINE

outer_loop:
lea ax, multiplicand ; load multiplicand
call get_unsigned_8byte
call print_unsigned_8byte
call get_unsigned ; unsigned word to multiplier
mov multiplier, ax


lea si, multiplicand ; load pointers
lea bx, result

mov cx, 4 ; number of words
sub di,di ; clear di

mult_loop:

____________________

1 For those of you with a hankering for large multiplication
and division, I have included subroutines which can multiply and
divide numbers of any length in a file called MISHMASH.DOC. It is
in \EXTRAFILE. You will need to finish all the chapters before
looking at it, since it uses things that you don't know about
yet.

______________________

The PC Assembler Tutor - Copyright (C) 1989 Chuck Nelson




The PC Assembler Tutor 130
______________________

mov ax, [si] ; multiplicand to ax
mul multiplier ; {2}
add ax, di ; high word from last multiplication
jnc store_result
inc dx ; {3}
store_result:
mov [bx], ax ; store 1 word of result.
mov di, dx ; save high word for next multiplication
add si, 2 ; increment pointers
add bx, 2
loop mult_loop

mov [bx], di ; move last word of result

mov ax, [bx]
call print_hex
lea ax, result
call print_unsigned_8byte
jmp outer_loop

; - - - - - - - - ENTER CODE ABOVE THIS LINE

There are two different input calls, an 8 byte one and a 2 byte
one. Inside the loop we store the high word from the
multiplication in DI and then add it to the next result. This is
the same as when you multiply single digits in base 10 (9 X 7 =
63 carry the 6). Note that when you add DI, there can be a carry
from AX to DX, but there can be no carry out of DX. After we drop
out of the loop, we need to put the last word in result. We take
it from DI, but we could take it from DX if we wanted. Finally,
the printing. Print_unsigned_8byte can't print the whole result,
so we are printing the high word in hex form. If those top two
bytes are non zero, what 'print_unsigned_8byte' prints will be
incorrect because it is missing the top 2 bytes. Note once again
that the only thing constraining this program to an 8 byte number
is the 4 that we put in CX - change that number and you can do
any size number that you want.

Run a bunch of numbers through this, including a couple that have
more than a 20 digit result.


UNSIGNED DIVISION

Division is done the same way in the software as it is done with
pencil and paper, starting at the left and working right. On the
computer, this means starting with the high order word and
working down.
____________________

2 It would be about 3% faster to have this in a register, but
unfortunately we are out of registers.

3 Do we need to check DX for a carry here? No. The maximum
multiplication is FFFFh X FFFFh. The result is FFFE 0001h. That
means that DX is a maximum FFFEh. If you add one, that's FFFFh,
and no carry occurs.




Chapter 13 - Multiple Word Arithmetic II 131
________________________________________


; - - - - - - - - ENTER DATA BELOW THIS LINE
dividend dq ?
divisor dw ?
quotient dq ?
remainder dw ?
; - - - - - - - - ENTER DATA ABOVE THIS LINE

; - - - - - - - - ENTER CODE BELOW THIS LINE

outer_loop:

lea ax, dividend ; get dividend
call get_unsigned_8byte
call print_unsigned_8byte
call get_unsigned ; get divisor
mov divisor, ax

lea si, dividend + 6 ; start at the top
lea bx, quotient + 6
mov di, divisor
mov cx, 4 ; number of words
sub dx, dx ; clear dx for first division

division_loop:
mov ax, [si] ; dividend word to ax
div di ; {4}
mov [bx], ax ; word of result to quotient
sub si, 2 ; decrement the pointers
sub bx, 2
loop division_loop

mov remainder, dx
mov ax, remainder
call print_unsigned
lea ax, quotient
call print_unsigned_8byte

jmp outer_loop

; - - - - - - - - ENTER CODE ABOVE THIS LINE

That's it? Yup. The division instruction is designed to work
effeciently and simply. We start with the most significant
digits, divide, put the quotient in the variable "quotient",
____________________

4 After this division, the quotient is in AX and the remainder
is in DX. Say, aren't we going to do anything with the remainder?
There's nothing in the code about DX until we get out of the
loop. In fact, we ARE doing something with the remainder. Just
like division with pencil and paper, when you have a remainder,
you bring it down to the left of the next digits you are going to
divide. These get divided the next time around. But we don't need
to move the remainder because it's already in the right place.
Pretty snappy, huh? You don't need to move anything; it all takes
care of itself.




The PC Assembler Tutor 132
______________________

DECREMENT the pointers, and get the next word for division.
After the final division, we have the remainder left in DX, so we
move it to the variable "remainder". The final instructions print
the remainder and the quotient.

Notice that we don't need to touch the remainder during the
entire operation. The 8086 leaves it exactly where it needs to be
for the next division. Using the DX register when you have single
word division seems screwy, but using DX for multiple word
division is both natural and elegant. The Intel people made one
instruction do the work of both.

Remember from the earlier chapter on division that you can get a
zero divide error if the quotient is larger than 65535. Is it
possible to get a quotient larger than 65535 in this routine? NO.
It is impossible to get a zero divide on anything other than a
zero.{5}

Run the program and do several examples. You can even do a 0
divide if you feel like interrupting the program.


SIGNED NUMBERS

For byte or word signed multiplication and division, the 8086
changes the signed numbers into unsigned numbers, does unsigned
multiplication/division, then adjusts for sign. For long numbers,
we have to do these operations ourselves, so we need three
sections of code. (1) change the numbers into unsigned numbers,
(2) do unsigned multiplication/division and (3) adjust the signs.
The routines that we have here are part two of this scheme. It
will be easier to implement this once you know about subroutines,
so signed division and multiplication will have to wait till
later.



____________________

5 This is technical, so if you start getting lost, don't worry
about it. How do we know that it's impossible? What we are
putting in DX is the remainder (R). R is always less than the
divisor (D). Let Q be the number in AX the next time around. What
we are dividing is:
((R*65536) + Q ) / D <= (( R*65536 ) + 65535 ) /D
since Q is less than to or equal to 65535. This is the maximum.
( ((R*(65535 + 1)) + 65535 ) /D = (((R+1) * 65535) + R)/D (huh?)
= ((R+1) * 65535)/D + R/D
Let's do a few examples: if D = 1, R < D so R = 0 max.
= (1*65535)/1 + 0/1 = 65535 rem 0
where rem = remainder. If D = 2, R < D so R = 1 max.
= ((1+1)*65535)/2 + 1/2 = 65535 rem 1
If D = 3, R < D so R = 2 max.
= (2+1)*65535)/3 + 2/3 = 65535 rem 2
See a pattern here? R/D < 1, so the quotient can never be 65536.
The maximum will always be 65535 with the remainder 1 less than
the divisor. If you aren't a techie, ignore all this.




Chapter 13 - Multiple Word Arithmetic II 133
________________________________________

SUMMARY


For both signed and unsigned numbers, multiple word division and
multiplication are based on an unsigned number routine. Signed
numbers are changed into unsigned numbers, the operation is
performed, and the signs of the results are adjusted.


Multiplication is done the same as for single words except that
the high word from one result is saved and added to the low word
of the next result, thus adding the two partial results. If this
addition gives a carry, DX must be incremented.

Division operates from left to right. For the first division, DX
is zeroed. After that it always contains the remainder from the
last division. The quotients in AX are moved to memory one by
one. At the end, the final remainder will be in DX.