piclist 2001\03\14\022504a >
Thread: math calibration algorithm ?
face 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

;left align the dividend
; (shift accumulator left 1 bit to get the first result bit weight
;  equal to 128)
       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
       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,
        goto div_add              ;if negative - add
       subwf a0, f
       movf b1, w
        incfsz b1, w
         subwf a1, f
       goto div_next
       addwf a0, f
       movf b1, w
        incfsz b1, w
         addwf a1, f
;here carry has a new result bit
       rlf c0, f                  ;shift in next result bit
       rlf c1, f
        goto div_loop

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 :)


---- Original Message ----
From: Scott Dattalo <TakeThisOuTscottspamDATTALO.COM>
Sent: Wednesday, March 14, 2001 7:33:01
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

In reply to: <Pine.LNX.4.21.0103132312540.4446-100000@tempest2.blackhat.net>
See also: www.piclist.com/techref/microchip/math/index.htm?key=math
Reply You must be a member of the piclist mailing list (not only a www.piclist.com member) to post to the piclist. This form requires JavaScript and a browser/email client that can handle form mailto: posts.
Subject (change) math calibration algorithm ?

month overview.

new search...