- Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

[Ed Sutton-2]

Are there other ways to implement a divide by a 14 constant other than
cycle-chewing subtraction loops?

I want to use the PIC16F flash consisting of 14-bit words to store 8-bit
data.  I can implement the multiply-by-8 as a shift.  The crux of the
problem is basically the divide by a constant of 14.

Pseudo Code ( actual code will likely be assembly )

wordOffset = 8*byteOffset / 14;          // The integer result
wordBitOffset = 8*byteOffset % 14;   // The remainder result


Patterns:

The 14-bit words and 8-bit data have a common multiple of 56.
The wordBitOffset pattern { 0,8,2,10,4,12,6 } repeats every 7-bytes.
I can't see a solution but it is an interesting puzzle.

Thanks in advance for any tips or suggestions,

-Ed

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[Gordon Williams]

Did you look at:

http://www.piclist.com/techref/piclist/codegen/constdivmul.htm

It works quite well.

Regards,

Gordon Williams

----- Original Message -----
From: "Ed Sutton" <esutton@...>
To: <piclist@...>
Sent: Thursday, May 08, 2008 11:59 AM
Subject: [PIC] - Need fast divide by 14 constant routine? ( Random
access8-bit data in PIC16F flash )


: Are there other ways to implement a divide by a 14 constant other than
: cycle-chewing subtraction loops?
:
: I want to use the PIC16F flash consisting of 14-bit words to store 8-bit
: data.  I can implement the multiply-by-8 as a shift.  The crux of the
: problem is basically the divide by a constant of 14.
:
: Pseudo Code ( actual code will likely be assembly )
:
: wordOffset = 8*byteOffset / 14;          // The integer result
: wordBitOffset = 8*byteOffset % 14;   // The remainder result
:
:
: Patterns:
:
: The 14-bit words and 8-bit data have a common multiple of 56.
: The wordBitOffset pattern { 0,8,2,10,4,12,6 } repeats every 7-bytes.
: I can't see a solution but it is an interesting puzzle.
:
: Thanks in advance for any tips or suggestions,
:
: -Ed
:
: --
: http://www.piclist.com PIC/SX FAQ & list archive
: View/change your membership options at
: http://mailman.mit.edu/mailman/listinfo/piclist
:

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[Tamas Rudnai]

Hi Ed,

Could you explain a bit more what you are trying to do? 14 bit words means
each address addresses 14bit words, other words you do not need division or
whatever to pick up one byte. Or you are trying to split up the bytes to bit
streams to compress the data (and reading the flash with eeprom reading
method)?

Tamas



On Thu, May 8, 2008 at 4:59 PM, Ed Sutton <esutton@...> wrote:

> Are there other ways to implement a divide by a 14 constant other than
> cycle-chewing subtraction loops?
>
> I want to use the PIC16F flash consisting of 14-bit words to store 8-bit
> data.  I can implement the multiply-by-8 as a shift.  The crux of the
> problem is basically the divide by a constant of 14.
>
> Pseudo Code ( actual code will likely be assembly )
>
> wordOffset = 8*byteOffset / 14;          // The integer result
> wordBitOffset = 8*byteOffset % 14;   // The remainder result
>
>
> Patterns:
>
> The 14-bit words and 8-bit data have a common multiple of 56.
> The wordBitOffset pattern { 0,8,2,10,4,12,6 } repeats every 7-bytes.
> I can't see a solution but it is an interesting puzzle.
>
> Thanks in advance for any tips or suggestions,
>
> -Ed
>
> --
> http://www.piclist.com PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist
>

--
Rudonix DoubleSaver
http://www.rudonix.com
--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[David VanHorn-2]

Multiply by 9, then divide by 128?  (close..)

It's not really apparent what you're trying to optimize.
I had a problem once where I was trying to do bearing calculations,
and I did NOT want to do 16 bit math, and I was able to do it in 8
bit, forsaking degrees for "dilberts" where there are 256 dilberts of
angle in a circle
--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[Spehro Pefhany]

Quoting Ed Sutton <esutton@...>:

> Are there other ways to implement a divide by a 14 constant other than
> cycle-chewing subtraction loops?
>
> I want to use the PIC16F flash consisting of 14-bit words to store 8-bit
> data.  I can implement the multiply-by-8 as a shift.  The crux of the
> problem is basically the divide by a constant of 14.
>
> Pseudo Code ( actual code will likely be assembly )
>
> wordOffset = 8*byteOffset / 14;          // The integer result
> wordBitOffset = 8*byteOffset % 14;   // The remainder result

Since you need both the quotient and the remainder, and cannot tolerate
any error in either, I think a conventional shift-and-subtract  
division routine
will work pretty well and will generate both numbers at once. Did you  
check the PICLIST code library?

Best regards,
Spehro Pefhany
--
"it's the network..."                          "The Journey is the reward"
s...@...             Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog  Info for designers:  http://www.speff.com


--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[Mark Scoville]

Or mult by 18, then divide by 256. Will not be any more accurate than
*9/128, but Divide by 256 is simply dropping the least sig byte.

<Mumbling to self> now I gotta buy a new calculator that has "dilberts" :-)

-- Mark

> -----Original Message-----
> From: piclist-bounces@... [mailto:piclist-bounces@...]On Behalf
> Of David VanHorn
> Sent: Thursday, May 08, 2008 12:06 PM
> To: Microcontroller discussion list - Public.
> Subject: Re: [PIC] - Need fast divide by 14 constant routine? ( Random
> access8-bit data in PIC16F flash )
>
>
> Multiply by 9, then divide by 128?  (close..)
>
> It's not really apparent what you're trying to optimize.
> I had a problem once where I was trying to do bearing calculations,
> and I did NOT want to do 16 bit math, and I was able to do it in 8
> bit, forsaking degrees for "dilberts" where there are 256 dilberts of
> angle in a circle
> --
> http://www.piclist.com PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist
>
>

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[Jinx-4]

Ed, I have an 16F877 application that **has** to be accurate. Much
of program memory plus external flash is bit-mapped in a chance game

I had a look at some shift-type routines, but found that the remainder
was not always accurate, even with a 0.5 test. Perhaps not quite true,
but the more bits you use for the division, the more bits are in the
remainder fraction, and by the time you work through those it would
sometimes have been quicker to do the division the by subtraction

Can't describe the game itself in detail, but basically there are three
very large bit tables, all the same length. To access a number in each
eg 9,473 => 9473/14 => 676 whole bytes, remainder indicates the
position in the 677th byte

So, anyway, this isn't fast, but it's accurate. I'm sure it could be made
a little faster but it's sufficient for my application as is

Hope it helps (you or someone)

;================================================
;        Divide by subtraction,
;        Slow but guaranteed accurate remainder
;================================================

div14    bank0
         bcf     res_eq0      ;result=0 flag
         movlw   0x0e         ;divisor
         movwf   dsorl
         clrf    dsorm
         clrf    dsorh
         clrf    dendh
         clrf    resl         ;result low
         clrf    resh         ;result high
         clrf    rem          ;remainder

         movf    dendm,f      ;test dividend for < 14
         btfss   zero
         goto    dloop        ;dendm > 00, continue division

         movlw   0x0e
         subwf   dendl,w
         btfsc   status,c
         goto    dloop        ;dendl > 13, continue division
         movf    dendl,w      ;dendl between 1 and 13, exit
         movwf   rem
         return               ;exit with result=0 + remainder

;------- division loop for num > 13

dloop    btfsc   dendh,7      ;test for < 00 result
         goto    end_div

         bcf     status,c
         movf    dsorl,w      ;subtract divisor from dividend
         subwf   dendl,f

         movf    dsorm,w      ;ripple through high bytes
         btfss   status,c
         incfsz  dsorm,w
         subwf   dendm,f

         movf    dsorh,w
         btfss   status,c
         incfsz  dsorh,w
         subwf   dendh,f

         incfsz  resl,f
         goto    dloop
         incf    resh,f
         goto    dloop

end_div  decfsz  resl,f       ;return with address
         movlw   0x0e         ;in resh / resl
         addwf   dendl,w      ;and bit position in rem
         movwf   rem
         btfss   rem,7
         goto    test_0
         movlw   0x0e         ;correct any underflow
         addwf   rem,f

;------- test result for 0

test_0   movf    resl,w
         addwf   resh,w       ;add resl to resh
         btfsc   zero         ;if resl <> 00
         return               ;else exit with res_eq0 = 0
         bsf     res_eq0
         return               ;exit with res_eq0 = 1

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[William "Chops" Westfield]

On May 8, 2008, at 11:31 AM, Mark Scoville wrote:
> Or mult by 18, then divide by 256. Will not be any more accurate than
> *9/128, but Divide by 256 is simply dropping the least sig byte.
>>
>> Multiply by 9, then divide by 128?  (close..)

Not close enough.  Fails about 50 times over the range of 1..256, and is
off by more than 1 by starting at 910.

BillW

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[Ruben Jönsson]

>
> Can't describe the game itself in detail, but basically there are three
> very large bit tables, all the same length. To access a number in each
> eg 9,473 => 9473/14 => 676 whole bytes, remainder indicates the
> position in the 677th byte
>
> So, anyway, this isn't fast, but it's accurate. I'm sure it could be made
> a little faster but it's sufficient for my application as is
>

A shift-subtract division is also accurate. Always.

In your case you can multiply the dividend with 256 (just one more byte of
0's), run the shift-subtract division until you got 3 bits in the quotient
fraction part, right shift the 3 upper bits 5 times (to get them to the 3 lower
bits) and then you have the byte position in the integer quotient part and the
bit offset in the shifted fraction remainder part.

/Ruben
<http://www.rjjournal.net>
==============================
Ruben Jönsson
AB Liros Electronic
Box 9124, 200 39 Malmö, Sweden
TEL INT [phone]
FAX INT [phone]
ruben@...
==============================

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[Harold Hallikainen-2]

There's a nice code generator for multiply and divide by a constant at
http://www.piclist.com/techref/piclist/codegen/constdivmul.htm .

Harold


--
FCC Rules Updated Daily at http://www.hallikainen.com - Advertising
opportunities available!
--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[sergio masci-2]

Ok, so you need an array of bits stored in code space.

How big is this array?

For an array of upto 3584 bits you could encode the bit positions
differently to give you better performance.

e.g.

word_offset = (8 * byte_offset) & 0xff;
bit_offset  = (8 * byte_offset) >> 8;

so you use:
bit 0 if word 0 for bit_arr[0]
bit 0 if word 1 for bit_arr[1]
bit 0 if word 2 for bit_arr[2]
.
.
.
bit 0 if word 255 for bit_arr[255]
bit 1 if word 0   for bit_arr[256]
bit 1 if word 1   for bit_arr[257]
bit 1 if word 2   for bit_arr[258]
.
.
.
bit 1 if word 255 for bit_arr[511]
bit 2 if word 0   for bit_arr[512]
bit 2 if word 1   for bit_arr[513]
bit 2 if word 2   for bit_arr[514]
.
.
.


basically you use the top most 4 bit of the index to specify bit within
word ensuring that these 4 bits are always in the range 0..13 and the
remaining bits (to the right of these 4 bits) as the word index.

an array of 3584 would be 4+8 bits (256 14 bit words)
an array of 1792 would be 4+7 bits (128 14 bit words)
an array of 7168 would be 4+9 bits (512 14 bit words)

Regards
Sergio Masci

http://www.xcprod.com/titan/XCSB
Optimising PIC compiler free for personal
non-commercial use



On Thu, 8 May 2008, Ed Sutton wrote:

> Are there other ways to implement a divide by a 14 constant other than
> cycle-chewing subtraction loops?
>
> I want to use the PIC16F flash consisting of 14-bit words to store 8-bit
> data.  I can implement the multiply-by-8 as a shift.  The crux of the
> problem is basically the divide by a constant of 14.
>
> Pseudo Code ( actual code will likely be assembly )
>
> wordOffset = 8*byteOffset / 14;          // The integer result
> wordBitOffset = 8*byteOffset % 14;   // The remainder result
>
>
> Patterns:
>
> The 14-bit words and 8-bit data have a common multiple of 56.
> The wordBitOffset pattern { 0,8,2,10,4,12,6 } repeats every 7-bytes.
> I can't see a solution but it is an interesting puzzle.
>
> Thanks in advance for any tips or suggestions,
>
> -Ed
>
> --
> http://www.piclist.com PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist
>

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[Jinx-4]

> A shift-subtract division is also accurate. Always.

I have no doubt you're right Ruben, you have to be. Whether it
was the method I chose, I did something wrong or what, don't
know, but I did get results that I couldn't be confident in (and
more importantly should not happen in front of the client). These
days I *would* make shift-subtract division work. At the time,
the /14 was an important, but small, part of a quite large project
and the push was on to get it up and running, so you go with
what works first, even if it ain't pretty

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[William "Chops" Westfield]

On May 9, 2008, at 12:39 PM, Harold Hallikainen wrote:
> There's a nice code generator for multiply and divide by a constant at
> http://www.piclist.com/techref/piclist/codegen/constdivmul.htm .

The algorithm it produces does not seem to work very well in this  
case, even if I use extra bits to produce less error in intermediate  
steps.
I'm having trouble grasping why not :-(

It says:

; ALGORITHM:
; Clear accumulator
; Add input / 16 to accumulator
; Add input / 128 to accumulator
; Add input / 1024 to accumulator
; Add input / 8192 to accumulator
; Add input / 65536 to accumulator

The first error is at 14.  (ALL the factors are obviously zero.)
Even if I do:

        (i/2 + i/16 + i/128 + i/1024 + i/8192) / 8

The first error is still at 14.

Going at it backwards isn't going to work either:
        x/14 = x/8 - x/32 - x/64 - x/256...

BillW

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[John Coppens]

On Fri, 9 May 2008 17:14:47 -0700
"William \"Chops\" Westfield" <westfw@...> wrote:

>
> On May 9, 2008, at 12:39 PM, Harold Hallikainen wrote:
> > There's a nice code generator for multiply and divide by a constant at
> > http://www.piclist.com/techref/piclist/codegen/constdivmul.htm .
>
> The algorithm it produces does not seem to work very well in this  
> case, even if I use extra bits to produce less error in intermediate  
> steps.
> I'm having trouble grasping why not :-(
>
> It says:
>
> ; ALGORITHM:
> ; Clear accumulator
> ; Add input / 16 to accumulator
> ; Add input / 128 to accumulator
> ; Add input / 1024 to accumulator
> ; Add input / 8192 to accumulator
> ; Add input / 65536 to accumulator
>

Hi Bill...

I believe this is not a precise division. What is being done is multiply
really by 1/14 in decimal, or 0.071...  You selected a precision of 16
bits (?), so the error will probably be in the order of 1. It's quite
probable that the first one fails.

the 0.071 is approximated as 74896 (=16+128+1024+8192+65536) divided
by 1048576 (2^20) which gives 0.071426 instead of 0.0714286.
The algorithm is quite clever, but it's not for _exact_ division!

John
--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[John Coppens]

On Fri, 9 May 2008 22:27:26 -0300
John Coppens <john@...> wrote:

> You selected a precision of 16
> bits (?), so the error will probably be in the order of 1. It's quite
> probable that the first one fails.

That didn't come out right.

The error will always be +/- 1, but if you selected 16 bit precision,
that means only an error of 1 in 4000 or so (65536/14). Which, if you
look to replace fractional division by a simple algorithm, is quite good.

As stated in the other message, the division won't necessarily work for
you if you need exact results.

The 0.071... is approximated by

1/16 0.0625 +
1/128 0.0078125 +
1/1024 0.0009765625 +
etc

John
--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[William "Chops" Westfield]

On May 9, 2008, at 6:27 PM, John Coppens wrote:
> I believe this is not a precise division. What is being done is  
> multiply
> really by 1/14 in decimal, or 0.071...  You selected a precision of 16
> bits (?), so the error will probably be in the order of 1. It's quite
> probable that the first one fails.

Right, that's PART of it.  But multiplying (floatingpoint) by
        (1.0/16 + 1.0/128 + 1.0/1024 + 1.0/8192 + 1.0/65536)

over the input range (1..65535) gives only 1/3 the number of errors  
(about 7000) as adding the set of integer divisions. Note that this  
point is about as far as it makes sense to take the binary fractions;  
for the 16bit input, anything smaller than i/65536 is going to be  
zero anyway; that's one of the factors that led me to expect better  
results.  :-(

> The error will always be +/- 1, but if you selected 16 bit precision,
> that means only an error of 1 in 4000 or so (65536/14). Which, if you
> look to replace fractional division by a simple algorithm, is quite  
> good.


Sounds good, doesn't it?  But 14/14 = 0 is 100% error !

It seems like a similar algorithm ought to be able to do better.

BillW

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[Forrest W Christian-2]

Have you considered storing this in some sort of word-aligned manner...

I.E. let's assume you want to store 500 8 bit bytes...

Store the first 286 as bits 0...7 bits of each word (8 bits).
Store the next 143 as bits 8..11 of each word, but spread across 2 words.
Store the final 71 as bits 12 & 13 of eac word, and spread across 4 words.

Then your algorithm looks like (semi pseudo-code, in c ...  That is,
don't shoot me if I mangled something like & versus && or >>'d the wrong
way or too few/too many bits- I've had too long of a day today so I
might have messed up and I don't feel like looking it up.)

uint8 retrievebyte (uint16 address)
{
  if (address<286)
  {
     return flash[address]&&0xff;
  }
  else if (address<(143+286))
  {
     //return bits 8.11 of address*2 in lower 4 bits, and 8.11 of
address*2+1 in higher 4 bits;
     return (   (flash[address*2]>>8) && 0x0f) +
                   (flash[address*2+1]>>4&&0xf0)
               );
  }
  else if (address<(71+143+286))
  {
     return (   (flash[address*2]>>12) && 0x03) +
                   (flash[address*2+1]>>10&&0x0c) +
                   (flash[address*2+2]>>8&&0x30) +
                   (flash[address*2+3]>>6&&0xc0)
               );

   }
   else
   {
      /// Handle out of range error accordingly.
      return 0;
   }
}


Ed Sutton wrote:

> Are there other ways to implement a divide by a 14 constant other than
> cycle-chewing subtraction loops?
>
> I want to use the PIC16F flash consisting of 14-bit words to store 8-bit
> data.  I can implement the multiply-by-8 as a shift.  The crux of the
> problem is basically the divide by a constant of 14.
>
> Pseudo Code ( actual code will likely be assembly )
>
> wordOffset = 8*byteOffset / 14;          // The integer result
> wordBitOffset = 8*byteOffset % 14;   // The remainder result
>
>
> Patterns:
>
> The 14-bit words and 8-bit data have a common multiple of 56.
> The wordBitOffset pattern { 0,8,2,10,4,12,6 } repeats every 7-bytes.
> I can't see a solution but it is an interesting puzzle.
>
> Thanks in advance for any tips or suggestions,
>
> -Ed
>
>  

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist