Searching \ for '[PIC]: coding challenge: divide by 7' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/microchip/math/index.htm?key=divide
Search entire site for: 'coding challenge: divide by 7'.

Exact match. Not showing close matches.
PICList Thread
'[PIC]: coding challenge: divide by 7'
2004\03\10@154044 by Wouter van Ooijen

face picon face
Someone asked me for a fast yet not extremely large code snipped to
divide a one-byte value in memory by 7 (on a 14-bit core). I think I
have a straight-line (no loop) code that uses 33 instructions (2 less if
the source can be destroyed). Looping version would be 12 instructions,
but of course somewhat longer execution. Can anyone do it faster,
preferrably with fewer instructions? I know a table lookup will be
faster, but I think the 256+ size would be classified as 'extremely
large'.

Wouter van Ooijen

-- -------------------------------------------
Van Ooijen Technische Informatica: http://www.voti.nl
consultancy, development, PICmicro products

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email spam_OUTlistservTakeThisOuTspammitvma.mit.edu with SET PICList DIGEST in the body

2004\03\10@163519 by A.J. Tufgar

flavicon
face
part 1 1053 bytes content-type:text/plain; charset="ISO-8859-1" (unknown type 8bit not decoded)

Don't have time check it out but this is how I would do it.
Basically you divide by 8 and correct for the difference between 7.

There are VERY likely to be code errors.

movf orgional_num,w
movwf div_num
RRF div_num, f ; Divide by 8.
RRF div_num, f ;
RRF div_num, f ;

movf origional_num, w
sublw d'27'
BTFSC STATUS, C ; if origional_num is <= 27 we shouldn't add 1.
inc div_num,f

movf origional_num, w
sublw d'83'
BTFSC STATUS, C ; if origional_num is <= 83 we shouldn't add 1.
inc div_num,f

movf origional_num, w
sublw d'139'
BTFSC STATUS, C ; if origional_num is <= 139 we shouldn't add 1.
inc div_num,f

movf origional_num, w
sublw d'195'
BTFSC STATUS, C ; if origional_num is <= 195 we shouldn't add 1.
inc div_num,f

movf origional_num, w
sublw d'251'
BTFSC STATUS, C ; if origional_num is <= 251 we shouldn't add 1.
inc div_num,f

return

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email .....listservKILLspamspam@spam@mitvma.mit.edu with SET PICList DIGEST in the body




part 2 48165 bytes content-type:application/octet-stream (decode)

2004\03\10@170433 by Wouter van Ooijen

face picon face
> Don't have time check it out but this is how I would do it.
> Basically you divide by 8 and correct for the difference between 7.

nice, 25 instructions (but to be checked, just like my attempt,
actually)

Wouter van Ooijen

-- -------------------------------------------
Van Ooijen Technische Informatica: http://www.voti.nl
consultancy, development, PICmicro products

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email listservspamKILLspammitvma.mit.edu with SET PICList DIGEST in the body

2004\03\10@172715 by Ben Hencke

picon face
--- Wouter van Ooijen <.....wouterKILLspamspam.....VOTI.NL> wrote:
> Someone asked me for a fast yet not extremely large
> code snipped to
> divide a one-byte value in memory by 7 (on a 14-bit

Have you tried the code generator on the piclist site?
You can multiply by 1/7 to get what you are looking
for.
www.piclist.com/techref/piclist/codegen/constdivmul.htm
It came up with this:

==================================
; ACC = ACC * 0.142857
; Temp = TEMP
; ACC size = 8 bits
; Error = 0.5 %
; Bytes order = little endian
; Round = no

; ALGORITHM:
; Clear accumulator
; Add input / 8 to accumulator
; Add input / 64 to accumulator
; Add input / 512 to accumulator
; Move accumulator to result
;
; Approximated constant: 0.142578, Error: 0.195283 %

;     Input: ACC0, 8 bits
;    Output: ACC0, 6 bits
; Code size: 19 instructions

       cblock
       ACC0
       endc

;copy accumulator to temporary
       movf    ACC0, w


;shift accumulator right 3 times
       clrc
       rrf     ACC0, f
       clrc
       rrf     ACC0, f
       clrc
       rrf     ACC0, f

;add temporary to accumulator
       addwf   ACC0, f

;shift accumulator right 3 times
       rrf     ACC0, f
       clrc
       rrf     ACC0, f
       clrc
       rrf     ACC0, f

;add temporary to accumulator
       addwf   ACC0, f

;shift accumulator right 3 times
       rrf     ACC0, f
       clrc
       rrf     ACC0, f
       clrc
       rrf     ACC0, f
=================================

If you can spare another space on the stack, you can
get this smaller by calling for the 3 redundant
accumulator shifts. This cuts it down to 12
instructions. A quick run through looks like it takes
29 cycles with all those calls and returns and stuff
but also turns it into a useful function.


=================================
; MODIFIED div by 7 routine by Ben Hencke
; ACC = ACC * 0.142857
; Temp = TEMP
; ACC size = 8 bits
; Error = 0.5 %
; Bytes order = little endian
; Round = no

; ALGORITHM:
; Clear accumulator
; Add input / 8 to accumulator
; Add input / 64 to accumulator
; Add input / 512 to accumulator
; Move accumulator to result
;
; Approximated constant: 0.142578, Error: 0.195283 %

;     Input: ACC0, 8 bits
;    Output: ACC0, 6 bits
; Code size: 12 instructions, 29 cycles

       cblock
       ACC0
       endc

divby7:

;copy accumulator to temporary
       movf    ACC0, w

;shift accumulator right 3 times
       clrc  ; this was in the first shift
             ; but not the others
       call shiftacc3
;add temporary to accumulator
       addwf   ACC0, f
;shift accumulator right 3 times
       call shiftacc3
;add temporary to accumulator
       addwf   ACC0, f

       ;shift accumulator right 3 times
       ;for this last shift, we can just fall through
to our subroutine and our function will return from
there
       ;this is either an ugly hack or an elegent
space saving design ;-)

shiftacc3:
;shift accumulator right 3 times
       rrf     ACC0, f
       clrc
       rrf     ACC0, f
       clrc
       rrf     ACC0, f
       return

======================================

Enjoy,
 Ben Hencke

__________________________________
Do you Yahoo!?
Yahoo! Search - Find what you re looking for faster
http://search.yahoo.com

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email EraseMElistservspam_OUTspamTakeThisOuTmitvma.mit.edu with SET PICList DIGEST in the body

2004\03\10@173131 by John N. Power

flavicon
face
> From:         Wouter van Ooijen[SMTP:wouterspamspam_OUTVOTI.NL]
> Sent:         Wednesday, March 10, 2004 3:40 PM
> To:   @spam@PICLISTKILLspamspamMITVMA.MIT.EDU
> Subject:      [PIC]: coding challenge: divide by 7

> Someone asked me for a fast yet not extremely large code snipped to
> divide a one-byte value in memory by 7 (on a 14-bit core). I think I
> have a straight-line (no loop) code that uses 33 instructions (2 less if
> the source can be destroyed). Looping version would be 12 instructions,
> but of course somewhat longer execution. Can anyone do it faster,
> preferrably with fewer instructions? I know a table lookup will be
> faster, but I think the 256+ size would be classified as 'extremely
> large'.

> Wouter van Ooijen

1 / 7 = 9 / 63
To divide by 63, multiply by binary 0.000001000001000001 . . .
To multiply by 9, multiply by binary 1001

To combine the two, multiply by
0.001001001001001001 . . .

Repeatedly shift 3 places right and add.

John Power

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email KILLspamlistservKILLspamspammitvma.mit.edu with SET PICList DIGEST in the body

2004\03\10@175026 by Andrew Warren

flavicon
face
A.J. Tufgar <RemoveMEPICLISTTakeThisOuTspammitvma.mit.edu> wrote:

> Don't have time check it out but this is how I would do it.
> Basically you divide by 8 and correct for the difference between 7.

   Test your code with original_num set to 7.  Your routine should
   return 1, but it won't.  Try it with 14 or 15; should return 2,
   but won't... Etc.

   Nice thought, though.

   -Andy

=== Andrew Warren -- spamBeGoneaiwspamBeGonespamcypress.com
=== Principal Design Engineer
=== Cypress Semiconductor Corporation
===
=== Opinions expressed above do not
=== necessarily represent those of
=== Cypress Semiconductor Corporation

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email TakeThisOuTlistservEraseMEspamspam_OUTmitvma.mit.edu with SET PICList DIGEST in the body

2004\03\10@182216 by Djula Djarmati

flavicon
face
>Someone asked me for a fast yet not extremely large code snipped to
>divide a one-byte value in memory by 7 (on a 14-bit core). I think I
>have a straight-line (no loop) code that uses 33 instructions (2 less if
>the source can be destroyed). Looping version would be 12 instructions,
>but of course somewhat longer execution. Can anyone do it faster,
>preferrably with fewer instructions? I know a table lookup will be
>faster, but I think the 256+ size would be classified as 'extremely
>large'.

   The "divide by 8 and fix" method with the remainder. If you don't need
the remainder then it's 22 instructions (and it's fully tested!).

Enjoy!

Djula

;DIVIDE ONE BYTE BY 7
;Input dividend:    W
;Output result:     RESULT
;Output remainder:  REMAIND
;Trashes:           TEMP
DivideBy7       movwf   TEMP
               andlw   0x07
               movwf   REMAIND
               rrcf    TEMP,f
               rrcf    TEMP,f
               rrcf    TEMP,w
               andlw   0x1f
               movwf   RESULT
               addwf   REMAIND,w
               movwf   TEMP

               andlw   0x07
               movwf   REMAIND
               rrcf    TEMP,f
               rrcf    TEMP,f
               rrcf    TEMP,w
               andlw   0x1f
               addwf   RESULT,f
               addwf   REMAIND,f

               movlw   -D'7'
               addwf   REMAIND,w
               btfss   STATUS,C
               return
               movwf   REMAIND
               incf    RESULT,f
               return

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email RemoveMElistservspamTakeThisOuTmitvma.mit.edu with SET PICList DIGEST in the body

2004\03\10@185532 by Scott Dattalo

face
flavicon
face
On Wed, 10 Mar 2004, Wouter van Ooijen wrote:

> Someone asked me for a fast yet not extremely large code snipped to
> divide a one-byte value in memory by 7 (on a 14-bit core). I think I
> have a straight-line (no loop) code that uses 33 instructions (2 less if
> the source can be destroyed). Looping version would be 12 instructions,
> but of course somewhat longer execution. Can anyone do it faster,
> preferrably with fewer instructions? I know a table lookup will be
> faster, but I think the 256+ size would be classified as 'extremely
> large'.

Not particular accurate, but is a mystical 12 instructions:

; enter  with x
; exit with y ~= x/7

       swapf   x,w
       andlw   0x8f
       movwf   y
       rlf     y,w
       rlf     y,w
       rrf     y,f
       rrf     y,f
       xorwf   y,w
       xorwf   y,f
       xorwf   y,w
       andlw   3
       addwf   y,f

If you add:

       movlw   3
       addwf   x,f

to the beginning, then this improves the accuracy somewhat (but it's still
kind of bad). Since this IS a challenge, I won't bother with the comments.
But as a hint, sum( (1/8)^i) for i = 1 to infinity is 1/7.

Scott

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email listservEraseMEspam.....mitvma.mit.edu with SET PICList DIGEST in the body

2004\03\11@024849 by Wouter van Ooijen

face picon face
> 1 / 7 = 9 / 63
> To divide by 63, multiply by binary 0.000001000001000001 . . .
> To multiply by 9, multiply by binary 1001
>
> To combine the two, multiply by
> 0.001001001001001001 . . .
>
> Repeatedly shift 3 places right and add.
>
> John Power

A kind of power series :)

I tried this. For a byte input the third and following terms will be 0,
so the formula is

x = ( y >> 3 ) + ( y >> 6 )

This is a reasonable approximation, but not exact.

Wouter van Ooijen

-- -------------------------------------------
Van Ooijen Technische Informatica: http://www.voti.nl
consultancy, development, PICmicro products

--
http://www.piclist.com hint: To leave the PICList
EraseMEpiclist-unsubscribe-requestspammitvma.mit.edu

2004\03\11@024850 by Wouter van Ooijen

face picon face
> Have you tried the code generator on the piclist site?

I did, but I also looked at the generated code :(

Like you I specified a byte (8 bits) input, yet the code attempts to
divide it by 512. And I am after an exact result, not an approximation.

Wouter van Ooijen

-- -------------------------------------------
Van Ooijen Technische Informatica: http://www.voti.nl
consultancy, development, PICmicro products

--
http://www.piclist.com hint: To leave the PICList
RemoveMEpiclist-unsubscribe-requestEraseMEspamEraseMEmitvma.mit.edu

2004\03\11@041751 by dr. Imre Bartfai

flavicon
face
Hi,

I have similar approach but the correction may be different. See:

The needed correction is: 1/7-1/8 = 0.017857

To produce this, see: 1/512+1/64 = 0.017578 which differs only in 4th
decimal. As u have 1 byte only, the 512 factor is meaningless, so
calculate the following expression:

x >> 3 + x >> 6

The error should be less, than 1:448

I think this approach even faster. Remember, x >> 6 = x >> 4 >> 2, where

x >> 4 may be replaced by SWAPF and ANDWF then.

Regards,

Imre


On Thu, 11 Mar 2004, Djula Djarmati wrote:

{Quote hidden}

--
http://www.piclist.com hint: To leave the PICList
RemoveMEpiclist-unsubscribe-requestTakeThisOuTspamspammitvma.mit.edu

2004\03\11@044317 by Wouter van Ooijen

face picon face
> calculate the following expression:
> x >> 3 + x >> 6
> The error should be less, than 1:448

Probably true in the analog/floating point world, but in the binary
(integer) world 7 / 7 == 1, but 7 >> 3 == 0, so in this particular case
the error is rather large :(

Wouter van Ooijen

-- -------------------------------------------
Van Ooijen Technische Informatica: http://www.voti.nl
consultancy, development, PICmicro products

--
http://www.piclist.com hint: To leave the PICList
EraseMEpiclist-unsubscribe-requestspamspamspamBeGonemitvma.mit.edu

2004\03\11@050845 by dr. Imre Bartfai

flavicon
face
Hi,

you have right, of course. Truncation may be a big challenge, but I did
not compute the error using worst-case scenario. Maybe a small script
would be sufficient regarding to the limited number of dividends. Even a
lookup table could be considered, if ROM is not a concern.

Regards,
Imre

On Thu, 11 Mar 2004, Wouter van Ooijen wrote:

{Quote hidden}

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-requestSTOPspamspamspam_OUTmitvma.mit.edu

2004\03\11@073015 by redtock8

flavicon
face
Ben,
How did you download that code from the code generator

--
http://www.piclist.com hint: To leave the PICList
spamBeGonepiclist-unsubscribe-requestSTOPspamspamEraseMEmitvma.mit.edu

2004\03\11@073225 by Byron A Jeff

face picon face
On Thu, Mar 11, 2004 at 10:25:25AM +0100, dr. Imre Bartfai wrote:
> Hi,
>
> I have similar approach but the correction may be different. See:
>
> The needed correction is: 1/7-1/8 = 0.017857
>
> To produce this, see: 1/512+1/64 = 0.017578 which differs only in 4th
> decimal. As u have 1 byte only, the 512 factor is meaningless, so
> calculate the following expression:
>
> x >> 3 + x >> 6
>
> The error should be less, than 1:448
>
> I think this approach even faster. Remember, x >> 6 = x >> 4 >> 2, where
>
> x >> 4 may be replaced by SWAPF and ANDWF then.

Seems interesting. I already saw Wouter's objection to x=7. I decided to test
with a random value x=177

177 >> 3 + 177 >> 6 = 22 + 2 = 24

177/7 = 25

So how do you resolve this error. I think the problem is that the 1/512 error
actually accumulates. So you reach a point where it does become significant
enough to affect the outcome. i.e. 177/512 is enough to cause damage.

So some thoughts:

1) You'll need to compute this to 16 significant bits in the intermediate
computation. For example 177/64 = 2.76572. You can't truncate the 2.76572
until after you've added it to the sum.

2) You need to account for the x/512 term.

So let's take these two into account for 177 -> 10110001

x/8   = 00010110 00100000
x/64  = 00000010 11000100
x/512 = 00000000 01011000   Note you don't have to worry about the upper byte
-----------------------------
       00011001 00111100

So as you can see the 177/512 term is required in order to get the x/8+x/64
over the hump from 24 to 25. It must be accounted for.

You'll have to left shift to get the lower byte terms for x/8 and x/64 and
right shift to get the others. It does work, but no clue as to how much it'll
cost. BTW it should satisfy the problem with x=7 too.

x/8   = 00000000 11100000
x/64  = 00000000 00011100
x/512 = 00000000 00000011   Note you don't have to worry about the upper byte
-----------------------------
       00000000 11111111

Nope. The error still kills you here.


BAJ

{Quote hidden}

--
http://www.piclist.com hint: To leave the PICList
@spam@piclist-unsubscribe-request@spam@spamspam_OUTmitvma.mit.edu

2004\03\11@085431 by Djula Djarmati

flavicon
face
>Someone asked me for a fast yet not extremely large code snipped to
>divide a one-byte value in memory by 7 (on a 14-bit core). I think I
>have a straight-line (no loop) code that uses 33 instructions (2 less if
>the source can be destroyed). Looping version would be 12 instructions,
>but of course somewhat longer execution. Can anyone do it faster,
>preferrably with fewer instructions? I know a table lookup will be
>faster, but I think the 256+ size would be classified as 'extremely
>large'.

   I improved my version slightly - now it's 19 instructions. Wouter, you
didn't say do you need the remainder or not?
   This is the same method, divide by 8, fix the dividend and then do the
division again.

Djula

;DIVIDE ONE BYTE BY 7
;Input dividend:    W
;Output result:     RESULT
;Trashes:           TEMP, REMAIND
DivideBy7       movwf   TEMP
               andlw   0x07
               movwf   REMAIND
               rrf    TEMP,f
               rrf    TEMP,f
               rrf    TEMP,w
               andlw   0x1f
               movwf   RESULT
               addwf   REMAIND,f
               rlf    REMAIND,f
               swapf   REMAIND,w
               andlw   0x0f
               addwf   RESULT,f
               rrf    REMAIND,f
               bcf     REMAIND,3
               addwf   REMAIND,f
               incf    REMAIND,f
               btfsc   REMAIND,3
               incf    RESULT,f
               return

--
http://www.piclist.com hint: To leave the PICList
spamBeGonepiclist-unsubscribe-requestspamKILLspammitvma.mit.edu

2004\03\11@103758 by Daniel Serpell

flavicon
face
Hi!

El Wed, Mar 10, 2004 at 09:40:28PM +0100, Wouter van Ooijen escribio:
> Someone asked me for a fast yet not extremely large code snipped to
> divide a one-byte value in memory by 7 (on a 14-bit core). I think I
> have a straight-line (no loop) code that uses 33 instructions (2 less if
> the source can be destroyed). Looping version would be 12 instructions,
> but of course somewhat longer execution. Can anyone do it faster,
> preferrably with fewer instructions? I know a table lookup will be
> faster, but I think the 256+ size would be classified as 'extremely
> large'.

You could try coding:

 div = (x*8 + x + x/4 - x/16 - x/64)/64

It gives correct results up to x=285. But it needs an 11-bit
acumulator.

I think that it's faster coding using 12bit acumulator:

 div = (x*16 + x*2 + x/2 - x/8 )/128    (acurate only up to 201)

or
 div = (x*16 + x*2 + x/2 - x/8 - x/16) / 128  (acurate up to 663)

The later has x*16 and x/16, that are easily obtained by swap's.

Other formulas can be derived easily...

   Daniel.

--
http://www.piclist.com hint: To leave the PICList
.....piclist-unsubscribe-requestspam_OUTspammitvma.mit.edu

2004\03\11@150048 by Ben Hencke

picon face
--- Wouter van Ooijen <TakeThisOuTwouter.....spamTakeThisOuTVOTI.NL> wrote:
> > Have you tried the code generator on the piclist
> site?
>
> I did, but I also looked at the generated code :(
>
> Like you I specified a byte (8 bits) input, yet the
> code attempts to
> divide it by 512. And I am after an exact result,
> not an approximation.

The algorithm doesn't product exact results becuase of
rounding errors, but its not as bad as to divide 8
bits by 512 ;-)


This part is a little misleading
; Add input / 8 to accumulator
; Add input / 64 to accumulator
; Add input / 512 to accumulator


It doesn't really divide the input by 512 (zero) and
add that to anything.

The algorithm is really:
input -> acc
clear carry
acc >>= 3
acc += input
acc >>= 3    (and 1 bit from carry)
acc += input
acc >>= 3    (and 1 bit from carry)

The last steps come in when you have a large input
(but still <= 255).

take 255 for example
input = 255
acc = input
;acc = 255
clear carry
acc(255) >>= 3
;acc = 31
acc += 255
;acc = 30 and C is set
acc >>= 3
;acc = 35
acc += 255
;acc = 34 and C is set
acc >>= 3
;acc = 36


This algorithm has problems because of the error of
rouding down a divide by 8. You can temper than error
a little by adding 3 to the input. If you want to do
that then you need to move the clear carry instruction
before the add by 3 instead of before the first
shifts.

It is still not perfect though.
- Ben Hencke

__________________________________
Do you Yahoo!?
Yahoo! Search - Find what you re looking for faster
http://search.yahoo.com

--
http://www.piclist.com hint: To leave the PICList
TakeThisOuTpiclist-unsubscribe-requestKILLspamspamspammitvma.mit.edu

2004\03\11@150709 by Ben Hencke

picon face
--- redtock8 <.....redrock8spamRemoveMEALLTEL.NET> wrote:
> Ben,
> How did you download that code from the code
> generator
>

Copy & paste ;-)

- Ben Hencke

__________________________________
Do you Yahoo!?
Yahoo! Search - Find what you re looking for faster
http://search.yahoo.com

--
http://www.piclist.com hint: To leave the PICList
RemoveMEpiclist-unsubscribe-requestspamspamBeGonemitvma.mit.edu

2004\03\11@165811 by Wouter van Ooijen

face picon face
>     I improved my version slightly - now it's 19
> instructions. Wouter, you
> didn't say do you need the remainder or not?

I did not explicitly say, but no, I don't need the reminder.

Wouter van Ooijen

-- -------------------------------------------
Van Ooijen Technische Informatica: http://www.voti.nl
consultancy, development, PICmicro products

--
http://www.piclist.com hint: To leave the PICList
spamBeGonepiclist-unsubscribe-request@spam@spamspam_OUTmitvma.mit.edu

2004\03\11@170224 by Koen van Leeuwen

flavicon
face
On Thu, 2004-03-11 at 08:48, Wouter van Ooijen wrote:
> Like you I specified a byte (8 bits) input, yet the code attempts to
> divide it by 512. And I am after an exact result, not an approximation.
>
> Wouter van Ooijen

This loop version is also 11 instructions, but perhaps the loop is
shorter/faster(?) than yours, or you see an instruction which can be
erased:

;division by 7 by Koen van Leeuwen
;number to be divided in divisor
;Trashed: w, divisor
       clrc
       clrf    outcome         ;start with clean reg
       movlw   b'11100000'     ;7 <<5
loop:
       movwf   powerof7
       subwf   divisor,w       ;check whether its too big
       rlf     outcome,f       ;shift in carry(/borrow)
                               ;(=whether outcome is negative or not)
                               ;and clear carry since leftmost bit of                          ;outcome is always zero
       btfsc   outcome,0       ;If carry was 1, subtraction succeeded.
       movwf   divisor         ;so this should be our next divisor
       rrf     powerof7,w      ;next bit, clear carry
       btfss   STATUS,C        ;If we have a carry here, we have                               ;shifted the 7
out.
       goto loop
                               ;and here is the result in outcome

--
http://www.piclist.com hint: To leave the PICList
TakeThisOuTpiclist-unsubscribe-requestspamspammitvma.mit.edu

2004\03\12@033910 by hael Rigby-Jones

picon face
{Quote hidden}

I wrote almost the same function before I left work last night, but didn't
have time to test it so didn't post.  Your's has one less instruction and it
easier to understand though.

If you unroll this loop, you get a good saving in execution time (executes
in 40 cycles including call and return), and it's still reasonably compact
(37 instructions).

Regards

Mike Rigby-Jones



div7
       clrc
       clrf    outcome         ;start with clean reg
       movlw   b'11100000'     ;7 <<5

       movwf   powerof7
       subwf   divisor,w       ;check whether its too big
       rlf     outcome,f       ;shift in carry(/borrow)
       btfsc   outcome,0       ;If carry was 1, subtraction succeeded.
       movwf   divisor         ;so this should be our next divisor
       rrf     powerof7,w      ;next factor

       movwf   powerof7
       subwf   divisor,w       ;check whether its too big
       rlf     outcome,f       ;shift in carry(/borrow)
       btfsc   outcome,0       ;If carry was 1, subtraction succeeded.
       movwf   divisor         ;so this should be our next divisor
       rrf     powerof7,w      ;next factor

       movwf   powerof7
       subwf   divisor,w       ;check whether its too big
       rlf     outcome,f       ;shift in carry(/borrow)
       btfsc   outcome,0       ;If carry was 1, subtraction succeeded.
       movwf   divisor         ;so this should be our next divisor
       rrf     powerof7,w      ;next factor

       movwf   powerof7
       subwf   divisor,w       ;check whether its too big
       rlf     outcome,f       ;shift in carry(/borrow)
       btfsc   outcome,0       ;If carry was 1, subtraction succeeded.
       movwf   divisor         ;so this should be our next divisor
       rrf     powerof7,w      ;next factor

       movwf   powerof7
       subwf   divisor,w       ;check whether its too big
       rlf     outcome,f       ;shift in carry(/borrow)
       btfsc   outcome,0       ;If carry was 1, subtraction succeeded.
       movwf   divisor         ;so this should be our next divisor
       rrf     powerof7,w      ;next factor

       movwf   powerof7
       subwf   divisor,w       ;check whether its too big
       rlf     outcome,f       ;shift in carry(/borrow)

       return




=======================================================================
This e-mail is intended for the person it is addressed to only. The
information contained in it may be confidential and/or protected by
law. If you are not the intended recipient of this message, you must
not make any use of this information, or copy or show it to any
person. Please contact us immediately to tell us that you have
received this e-mail, and return the original to us. Any use,
forwarding, printing or copying of this message is strictly prohibited.
No part of this message can be considered a request for goods or
services.
=======================================================================
Any questions about Bookham's E-Mail service should be directed to
@spam@postmasterRemoveMEspamEraseMEbookham.com.

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

2004\03\12@163317 by Koen van Leeuwen

flavicon
face
Unrolled, some things can be simpified so the whole thing is 31
instructions/cycles:

;division by 7 by Koen van Leeuwen
;number to be divided in divisor
;Trashed: w, divisor
       clrc
       clrf    outcome         ;start with clean reg
       movlw   b'11100000'     ;7 <<5
       subwf   divisor,w       ;check whether its too big
       rlf     outcome,f       ;shift in carry(/borrow)
                               ;(=whether outcome is negative or not)
                               ;and clear carry since leftmost bit of                          ;outcome is always zero
       btfsc   outcome,0       ;If carry was 1, subtraction succeeded.
       movwf   divisor         ;so this should be our next divisor


       movlw   b'01110000'     ;7 <<4
       subwf   divisor,w       ;check whether its too big
       rlf     outcome,f       ;shift in carry(/borrow)
                               ;(=whether outcome is negative or not)
                               ;and clear carry since leftmost bit of                          ;outcome is always zero
       btfsc   outcome,0       ;If carry was 1, subtraction succeeded.
       movwf   divisor         ;so this should be our next divisor

       movlw   b'00111000'     ;7 <<3
       subwf   divisor,w       ;check whether its too big
       rlf     outcome,f       ;shift in carry(/borrow)
                               ;(=whether outcome is negative or not)
                               ;and clear carry since leftmost bit of                          ;outcome is always zero
       btfsc   outcome,0       ;If carry was 1, subtraction succeeded.
       movwf   divisor         ;so this should be our next divisor

       movlw   b'00011100'     ;7 <<2
       subwf   divisor,w       ;check whether its too big
       rlf     outcome,f       ;shift in carry(/borrow)
                               ;(=whether outcome is negative or not)
                               ;and clear carry since leftmost bit of                          ;outcome is always zero
       btfsc   outcome,0       ;If carry was 1, subtraction succeeded.
       movwf   divisor         ;so this should be our next divisor

       movlw   b'00001110'     ;7 <<1
       subwf   divisor,w       ;check whether its too big
       rlf     outcome,f       ;shift in carry(/borrow)
                               ;(=whether outcome is negative or not)
                               ;and clear carry since leftmost bit of                          ;outcome is always zero
       btfsc   outcome,0       ;If carry was 1, subtraction succeeded.
       movwf   divisor         ;so this should be our next divisor

       movlw   b'00000111'     ;7
       subwf   divisor,w       ;check whether its too big
       rlf     outcome,f       ;shift in carry(/borrow)
                               ;(=whether outcome is negative or not)
                               ;and clear carry since leftmost bit of


       return                  ;and here is the result in outcome

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

2004\03\12@165429 by John N. Power

flavicon
face
{Quote hidden}

1/7 is exactly equal to 0.001001001 ... if the series is carried to
infinity. To get a reasonable result with finite number of terms,
it is necessary to carry the fractional part for at least some
reasonable number of iterations. The lack of a fractional part
causes the error you are referring to. The first shift of 3 bits
will create a fraction which is lost in integer arithmetic. The
second shift does likewise. If those fractional parts were
retained, their sum would sometimes increment the quotient,
giving the right answer in those cases where the formula fails
as given.

John Power

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

2004\03\12@175036 by William Chops Westfield

face picon face
On Friday, Mar 12, 2004, at 13:34 US/Pacific, Koen van Leeuwen wrote:

> Unrolled, some things can be simpified so the whole thing is 31
> instructions/cycles:
>
> ;division by 7 by Koen van Leeuwen
> ;number to be divided in divisor
> ;Trashed: w, divisor
>         clrc
>         clrf    outcome         ;start with clean reg
>         movlw   b'11100000'     ;7 <<5
>         subwf   divisor,w       ;check whether its too big
>         rlf     outcome,f       ;shift in carry(/borrow)
>                                 ;(=whether outcome is negative or not)
>                                 ;and clear carry since leftmost bit of
>                          ;outcome is always zero
>
(etc)

This is pretty much a standard generic division algorithm, only doing
the divisor shift manually, right?  (and also terminating early since
you know how many bits are in the divisor.)  As such, it's nicely
relevant to other division problems, but surely we ought to be able to
do better since we know that we're dealing with SEVEN, after all?

Does anyone have the relevant macro to produce the code above for any
constant divisor?

BillW

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

2004\03\12@195949 by Scott Dattalo

face
flavicon
face
On Fri, 12 Mar 2004, William Chops Westfield wrote:

>                                  ...  but surely we ought to be able to
> do better since we know that we're dealing with SEVEN, after all?

You mean something like this:

divby7_looped:

       clrf    y2
       comf    y2,f
       movlw   -7

L1:
       incf    y2,f
       addwf   x,f
       skpnc
        goto   L1

Not time-wise efficient. ~183 cycles worse case.

Scott

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

More... (looser matching)
- Last day of these posts
- In 2004 , 2005 only
- Today
- New search...