Hi!
12-Mar-98 08:49 Scott Dattalo wrote about "Re: Divide by 3":

 >> Here's another routine that does the job just ever so slightly
 >> faster. (And it's been tested). It takes advantage of the
 >> often forgotten Digit Carry flag.
 >>
 >> ; Divide by 3
 >> ; Input in W  , Output W/3
    . . . . . . .
 >> 19 cycles/instructions

    Tricky code is good, but straightforward one could be better. :)


 >> It works on the same 'multiply by 0x55 and divide by 0x100' concept.
 >> It's kind of interesting to see how much error is incurred by this
 >> method. If you simply multiply by 0x55 and divide by 0x100 you'll
 >> discover that the result is often too low. That can be explained
 >> by the fact that an infinite series has been truncated. Or
 >> equivalently, 85/256 = 0.3320 and 1/3 = 0.33333... So my
 >> implementation of the algorithm has a slight modification:
 >>
 >>   n/3 ~ (n+1)*85/256
    . . . . .
 >> In fact, the approximation is exact for all values of n between
 >> -512 and 1023

    Sorry... :(
    Let us check.
    258=86*3
    ((258+1)*85)/256=85.996. And truncation gives 85. :(

    To use this algorithm for dividend>255 one should modify it
using more digits in binary representation of 3/256=0.0101010101...
For example         n/3 ~ (n+1)*0.0101010101
or n/3 ~ (n+1)*0x555/4096=(n+1)*0.010101010101


    Some code examples (of course, 0..255 only):

; Divide by 3
    clrf    tmp
        incf    tmp,f
        addwf   tmp,f   ; tmp=(W+1)*1   (flag C is OK)
        rrf     tmp,f   ; tmp=(W+1)*0.1
        clrc
        rrf     tmp,f   ; tmp=(W+1)*0.01
    incf    tmp,f
    addwf   tmp,f
    rrf     tmp,f
    clrc
    rrf     tmp,f       ; tmp=(W+1)*0.0101
        incf    tmp,f
        addwf   tmp,f
        rrf     tmp,f
        clrc
        rrf     tmp,f   ; tmp=(W+1)*0.010101
    incf    tmp,f
    addwf   tmp,f
    rrf     tmp,f
    clrc
    rrf     tmp,w       ; w=(W+1)*0.01010101
;;      21 words and 1(!!!) byte

;   The same, loop version:
    clrf    tmp
    clrf    count
    bsf     count,2     ; count=4
loop:
        incf    tmp,f
        addwf   tmp,f
        rrf     tmp,f
        clrc
        rrf     tmp,f
        decfsz  count
            goto    loop
    movf    tmp,w
;;      11 words and 2 byte

;   Divide by 5
    clrf    tmp
        incf    tmp,f
        addwf   tmp,f
        rrf     tmp,f
        incf    tmp,f
        addwf   tmp,f
        rrf     tmp,f
        clrc
        rrf     tmp,f
        clrc
        rrf     tmp,f
    incf    tmp,f
    addwf   tmp,f
    rrf     tmp,f
    incf    tmp,f
    addwf   tmp,f
    rrf     tmp,f
    clrc
    rrf     tmp,f
    clrc
    rrf     tmp,w
;;      21 words and 1 byte  (loop version: 16 words and 2 byte)

;   Divide by 10
    clrf    tmp
        incf    tmp,f
        addwf   tmp,f
        rrf     tmp,f
        incf    tmp,f
        addwf   tmp,f
        rrf     tmp,f
        clrc
        rrf     tmp,f
        clrc
        rrf     tmp,f   ; tmp=(W+1)*0.0011
    incf    tmp,f
    addwf   tmp,f
    rrf     tmp,f
    incf    tmp,f
    addwf   tmp,f
    rrf     tmp,f
    clrc
    rrf     tmp,f
    clrc
    rrf     tmp,f   ; tmp=(W+1)*0.00110011=W/5
    clrc
    rrf     tmp,w
;;      23 words and 1 byte

--

                                    Vladimir M. Klochko