# File Archive

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.