|
|
The division word /word
Analogous a multiply, the algorithm will be explain on unsigned division d16/16. Because the 8051's instruction set has only the instruction "div ab" for a division byte/ byte, normally has been used routine based on Booths algorithm with successive deduction of divisor from the remainder, that has all in all 17 of iterations in loop. Aggregate count of processor's cycles is greater as 300 cycles.
I offer a description of new solution for 8051's family with the usage of instructions "mul ab" and "div ab".. Let we have numbers in registers (in BIN inscription): DH (Hi byte ) and DL (Lo byte) - for a dividend and dih (Hi byte ) and dil (Lo byte) - for a divisor. The operation of their division we can write in manner:
(256*DH + DL) / (256*dih + dil)
and now we make the analyse of possibilities, accordance to value divisor's Hi_byte:
A - for dih not equal to 0 we become:
AA - for DH equal to 0 the result is 0, because:
(256*DH + DL) < (256*dih + dil)
AB - for DH not equal to 0. In the first step when we remark, that 256*dih >> dil, therefore the error of this rounding is less than 1*256 or +/-1 according to dih, the expression we stylise in manner:
(256*DH + DL) / 256*dih = (DH / dih) + (DL/256* dih)
that is an entire part of result has only Lo_byte (DH / dih) with a possible offset -1 and the remainder less than divisor. For the case DH < dih is the result 0. The value of fraction we calculate direct with P= div (DH/dih). The remainder and the offset we determine by a deduction of product P*(256*dih + dil) from value (256*DH + DL) .It is of course the division w/w.
B - for dih not equal 0 we become:
BA - for DH equal to 0 we get direct:
* div (DL)(dil)
* it is the division By/By - the instruction "div ab".
BB - for DH not equal 0 we will get a division w/B the expression we can rewrite:
(256*DH + DL) / (dil)= div (DH)(dil) * 256 + div (DL)(dil).
The Hi_byte of result obvious is equal an entire part div (DH)(dil). When we mark with zb/dil - the remainder previous divide, then a Lo_byte of result we will calculate with the expression:
(zb/dil)*256 + (DL)/(dil) = (zb*256 + DL)/ dil.
Let we remark, that we divide by value in Byte range, moreover we would see, that all is identical with Booth's algorithm - the successive deduction of divisor from the remainder with a bit result 1 for a nonnegative sum. We know, that (zb/dil) < dil and the count of iteration is 8 ( dil is a Byte). Let we bring to notice, that (2*(zb/dil) + bit)/ dil have to give by usage of instruction "div ab" the only results 0 or 1 and a remainder in register B. The memorial of solution can you see in the printout past the label divBB1. For a divisor > 81H is necessary to handle an overflow pending the assembly of new dividend for instruction "div ab".
Note: The first step our algorithm must be of course a test on divide by zero !! Again for usage a likely sequence of mathematics operations isn't necessary a additional help registers for removal of intermediate data meanwhile enumeration.
Here is printout of program:
;*********************************************
; division 16b / 16b unsigned
;time of executive - min 7 cycles of processor for div by 0
; - w/w max 39 cycles of processor
; - w/B max 143 cycles of processor
; - B/B max 27 cycles of processor
; - average 70 cycles of processor
; code size (8051) - 93 byte
;*********************************************
;input in DH is byte_H and in DL is byte_L of dividend
;input in dih is byte_H and dil is byte_L of divisor
;output Cy =1 for div by 0, other Cy =0 and
; in DH is byte_H and in DL is byte_L - of remainder
; in dih is byte_H and in dil is byte_L - of quotient (the result)
;
; to change registers: Acc,DH,DL,dH,dL,b,Psw
; possibility to change work. registers **********
DH equ r3
DL equ r2
dih equ r5
dil equ r4
;*******
div16x16:
cjne dih,#0,divAA
cjne dil,#0,divBA
setb C
ret ;divide by 0
divAA:
mov a,DH
mov b,dih
div ab
jnz divAB ;result has H_byte
mov dih,a
mov dil,a
ret ;divide finalised, result=0
divAB:
push b ;store remainder
mov DH,a ;defer result_L in rp
mov b,dil
mul ab
xch a,DL
subb a,DL
xch a,DL
pop acc
subb a,b
jnc divABcont ;result positive, no correction
dec DH
xch a,DL
add a,dil
xch a,DL
addc a,dih
clr C
divABcont:
xch a,DH
mov dil,a
mov dih,#0
ret ;divide finalised
divBA:
mov b,dil
mov a,DH
div ab
mov dih,a ;store H_result
mov DH,b ;a new value of DH
cjne DH,#0,divBB
mov b,dil ;divide byte/byte
mov a,DL
div ab
mov dil,a
mov DL,b
ret
divBB:
mov DH,#8 ;divide word/byte
divBB1:
mov a,DL ;the shorted improved Booth's loop
rlc a
mov DL,a
mov a,dil
xch a,b
rlc a
jc divBB2 ;for divisors > 7FH
div ab
rrc a
djnz DH,divBB1
mov a,b
xch a,DL ;remainder -> DL, intermediate result_L-> acc
rlc a
mov dil,a
ret
divBB2: clr C
subb a,b
mov b,a
djnz DH,divBB1 ;a possibly end for divisors > 7FH
mov a,b
xch a,DL ;remainder -> DL, intermediate result_L-> acc
rlc a
mov dil,a
ret
;*******
Why we can see above is obvious that algorithm has been divided into three threads. Only the last (division word/byte ) has the short successive loop, but it has fix number of catwalk, therefore time of execution is non-constant, depending on values of input numbers. Its employment give us more triple shorter time of execution compared to classical manner of solving a problem. For the signed division word / word we have to append sign mathematics.
E-mail: 
info@telesys.ru
