piclist 2001\03\14\022504a >
www.piclist.com/techref/microchip/math/index.htm?key=math
BY : Nikolai Golovchenko email (remove spam text)

Good idea. Usually this trick is not useful for integer division,
because the dividend is usually used for storing the result (dividend
and quotient sharing the same location). But here we have a separate
memory for output, so it works! Using the trick, 3 words / 3 cycles /
1 register are saved. I just had to correct the bit you set, it should
have been c0.1.

;-----------------------------------------------------------------------------
; Input:
;  a1:a0 - 10 bit dividend
;  b1:b0 - 15 bit divisor in 7Q8 format (b1 is integer, b0 is
;          fractional)
; Output:
;  c1:c0 - 15 bit quotient in 7Q8 format
;
; Size: 27 words
; Time: 2+3+3+15*(2+3+7+5)-1+2=264 instruction cycles
;
;-----------------------------------------------------------------------------
div_uint10_fxp7q8_fxp7q8

;left align the dividend
; (shift accumulator left 1 bit to get the first result bit weight
;  equal to 128)
clrc
rlf     a0, f
rlf     a1, f              ;carry is cleared here
;initialize registers
clrf c0                    ;clear result - it will be used
clrf c1                    ;to shift zeroes to dividend
bsf c0, 1                  ;15 iterations
div_loop
rlf a0, f                  ;and shift out next bit of dividend
rlf a1, f                  ;to remainder

movf b0, w                 ;load w with lower divisor byte
skpnc                      ;if remainder positive - subtract,
;subract
subwf a0, f
movf b1, w
skpc
incfsz b1, w
subwf a1, f
goto div_next
movf b1, w
skpnc
incfsz b1, w
div_next
;here carry has a new result bit
rlf c0, f                  ;shift in next result bit
rlf c1, f
skpc
goto div_loop
return
;-----------------------------------------------------------------------------

This routine uses a non-restoring algorithm. The nice thing about it
is that it doesn't require a comparison. Each iteration does either
addition or subtraction, but never both. Therefore, it is almost two
times faster comparing to the restoring algorithm.

First, divisor is subtracted from dividend (lets call it the
remainder). Depending on inputs/outputs types the divisor should be
aligned relative to the remainder, so that the first result bit has an
appropriate weight (128 in our case), but let's not go into that, this
is exactly how it is always done in a division.

If the remainder becomes negative after subtraction, the next result
bit should be zero. This is the value of carry after subtraction,
which is convenient. Next iteration we shift the remainder left and
add the divisor to it. This is equivalent to the restoring method,
where divisor is added to remainder to restore it, then remainder shifted
left, and divisor subtracted again. In both methods we add a divisor
in fact. The result of two iterations is:

1) Non-restoring: remainder = remainder - divisor + divisor/2 = remainder - divisor/2
2) Restoring:     remainder = remainder - divisor + divisor - divisor/2 = remainder - divisor/2

And carry flag is always set correct for addition and subtraction
(subtraction is performed as addition internally, I guess). Don't you
now love the way carry works in PICs!

The routine works, I checked :)

Thanks,
Nikolai

---- Original Message ----
From: Scott Dattalo <scottDATTALO.COM>
Sent: Wednesday, March 14, 2001 7:33:01
To: PICLISTMITVMA.MIT.EDU
Subj: [PIC]: math calibration algorithm ?

{Quote hidden}

;>>         movlw 15                   ;15 iterations
;>>         movwf count

>>         clrf c0                    ;clear result - it will be used
>>         clrf c1                    ;to shift zeroes to dividend

>           bsf  c1,2   ; use c0:c1 as the counter after 15 shifts, this
>                       ; bit will go to the carry.

>> div_loop

> move the c0:c1<<1 down below
;>>         rlf c0, f                  ;shift in next result bit
;>>         rlf c1, f

{Quote hidden}

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

<1442871396.20010314092544@yahoo.com> 7bit