Searching \ for '[PIC] Division routines.' 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=division
Search entire site for: 'Division routines.'.

Exact match. Not showing close matches.
PICList Thread
'[PIC] Division routines.'
2017\09\05@133338 by David C Brown

picon face
I am trying to find some good 8 and 16 bit division routines for mid range
PICs.   Most of the app notes I have found give algorithms which result in
a quotient and remainder.

However in my case the divisor is always greater than the dividend so I
want a result that is conceptually between 0 and nearly 1 with an implied
binary point to the left.

I have written my own routines but I suspect that they are far from optimum..
__________________________________________
David C Brown
43 Bings Road
Whaley Bridge
High Peak                           Phone: 01663 733236
Derbyshire                eMail: spam_OUTdcb.homeTakeThisOuTspamgmail.com
SK23 7ND          web: http://www.bings-knowle.co.uk/dcb
<http://www.jb.man.ac.uk/~dcb>



*Sent from my etch-a-sketch*
-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2017\09\05@144856 by Neil

flavicon
face
Is this in C or assembly?

I still (even though PICs are more powerful nowadays) avoid floating-point calcs.  If I need say 2 decimal points, I multiply by 100 earlier, then do the division and insert the decimal point as appropriate.

Also, have you seen the routines here?... http://www.piclist.com/techref/microchip/math/index.htm

Cheers,
-Neil.



On 9/5/2017 1:33 PM, David C Brown wrote:
{Quote hidden}

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

2017\09\05@153012 by David C Brown

picon face
Assembler of course.   It is nothing to do with floating point.  Those
routines will give me a lot tho think about.  Thansks.

__________________________________________
David C Brown
43 Bings Road
Whaley Bridge
High Peak                           Phone: 01663 733236
Derbyshire                eMail: dcb.homespamKILLspamgmail.com
SK23 7ND          web: http://www.bings-knowle.co.uk/dcb
<http://www.jb.man.ac.uk/~dcb>



*Sent from my etch-a-sketch*

On 5 September 2017 at 19:48, Neil <.....picdude3KILLspamspam.....narwani.org> wrote:

{Quote hidden}

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

2017\09\05@153215 by smplx

flavicon
face


On Tue, 5 Sep 2017, David C Brown wrote:

> I am trying to find some good 8 and 16 bit division routines for mid range
> PICs.   Most of the app notes I have found give algorithms which result in
> a quotient and remainder.
>
> However in my case the divisor is always greater than the dividend so I
> want a result that is conceptually between 0 and nearly 1 with an implied
> binary point to the left.
>
> I have written my own routines but I suspect that they are far from optimum.

I'll give an example in C and I'll leave it to you to convert:

int frac_div(int x, int y)
{
       // divide x by y where x is always <= y
       // x and y are always positive

       unsigned int        res, mask;

       mask = 0x8000;
       res = 0;

       while (true)
       {
               x = x - y;

               if (x < 0)
               {        // on a PIC simply check the sign bit of x
                       x = x + y;
               }
               else
               {
                       res = res | mask;
               }

               mask = mask >> 1;

               if (mask == 0)
               {        break;
               }

               x = x << 1;
       }

       // BEWARE: MSB of res is int 0 or 1,
       // the remaining 15 bits are the binary fraction

       return res;
}

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

2017\09\05@191222 by William Westfield

face picon face
On Sep 5, 2017, at 10:33 AM, David C Brown <dcb.homespamspam_OUTgmail.com> wrote:

> in my case the divisor is always greater than the dividend so I
> want a result that is conceptually between 0 and nearly 1 with an implied
> binary point to the left.

It’s equivalent to multiplying your dividend  by 256 or 65536 and using 16/32bit division, right?  Except that you know you’ll run out of 1 bits comparatively early, and might be able to optimize away the extra registers.  Hmm.  An interesting problem!


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

2017\09\06@085006 by Bob Ammerman

flavicon
face
I am pretty sure something like the following will work...

Let's say you have a number of bits 'N', typically 8 or 16.

Then, many division routines will have a dividend of 2N bits, and a divisor
of N bits.

So, say you want to divide a N-bit number by another N-bit number with an
implied binary point on the left...

Simply extend your N-bit dividend by N zeros on the right and do the
division.

~ Bob Ammerman
RAm Systems

> {Original Message removed}

2017\09\06@115921 by Walter Banks

picon face

I depends how much you know about the numbers. This works as long as the
MSbit of x is 0.
No magic in this and not particularly fast.

w..

//
// divide x/y and return a fraction
// x < y always
//
// reference in 16 bits
//

uint16_t div_fract (uint16_t x,y)
  {
    char count = 16 ; // size of result in bits
    do
     {
      x <<= 1;
      if (x >= y)
       {
         x -= y;
         x |= 1;
       }
     }
    while(--count);
   return x;
  }



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

2017\09\06@130037 by smplx

flavicon
face
part 1 994 bytes content-type:text/plain; charset="utf-8" (decoded base64)



On Wed, 6 Sep 2017, Walter Banks wrote:

> I depends how much you know about the numbers. This works as long as the
> MSbit of x is 0.
> No magic in this and not particularly fast.
>
> w..
>
> //
> // divide x/y and return a fraction
> // x < y always
> //
> // reference in 16 bits
> //
>
> uint16_t div_fract (uint16_t x,y)
>   {
>     char count = 16 ; // size of result in bits
>     do
>      {
>       x <<= 1;
>       if (x >= y)
>        {
>          x -= y;
>          x |= 1;
>        }
>      }
>     while(--count);
>    return x;
>   }

Hi Walter, I don't understand how the above is supposed to work.
Surely the "x |= 1" is wrong? Don't you need a seperate variable build the
result in?

On a mid range PIC the "(x >= y)" would need to be performed as
"(x - y >= 0)" so why not compute "x = x - y" and compare with 0?

Regards
Sergio Masci
part 2 197 bytes content-type:text/plain; name="ATT00001.txt"
(decoded base64)

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

2017\09\06@130811 by smplx

flavicon
face


On Tue, 5 Sep 2017, smplx wrote:

enhancement to my own code follows

> int frac_div(int x, int y)
> {
>        // divide x by y where x is always <= y
>        // x and y are always positive

       // where x is always < y
         // x and y are always positive
       x = x << 1;

{Quote hidden}

       // results is now 16 bit binary fraction with
       // binary point before the MSB

>
>        return res;
> }


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

2017\09\06@163936 by Walter Banks

picon face



On 2017-09-06 2:05 PM, smplx wrote:
{Quote hidden}

Quite correct. Optimization is throw all the code you don't need and no
more.
moral. don't post untested code.

//
// divide x/y and return an _Fract
// x < y always
//
// reference in 16 bits
//

uint16_t div_fract (uint16_t x,y)
  {
    char count = 16 ; // size of result in bits
    uint16_t result = 0;
    do
     {
      x <<= 1;
      result <<= 1;
      if (x >= y)
       {
         x -= y;
         result |= 1;
       }
     }
    while(--count);
   return result;
  }

>
> On a mid range PIC the "(x >= y)" would need to be performed as
> "(x - y >= 0)" so why not compute "x = x - y" and compare with 0?
That is essentially my compiler does.
>
> Regards
> Sergio Masci
>
>

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

2017\09\07@091719 by David C Brown

picon face
Perhaps I have been selling myself short !  Whist I thank you for your
suggestions at the risk of sounding sarcastic which is not my intent, there
is nothing there that I couldn't get from my 1967 university textbook..  Or
from experienced engineers in my first job at International  Computers Ltd
in 1969.

The basic non restoring algorithm must have been developed by Turing or
Wilkes or one of there contemporaries back in the fifties.   For interest,
or not, This my take on it. - 55 memories, 2 working registers,  worst case
156 instructions.  Please criticise to your hearts content

..;=============================================================================;
; This Routine divides DIVIDEND BY DIVISOR for numbers less than 1. That is
 ;
; numbers with an implied binary point aat the extreme left.   The divisor
  ;
; must be greater than the dividend so thaat the quotient remains less than
1 ;
; ENTRY: Dividend in REGA.  Divisor in REGB
 ;
;  EXIT: Quotient in REGAX,REGA  W is 0
 ;
;        (IF Dividend > Divisor W is -1  and REGAX,REGA = REGA -REGB)
 ;
;  USES: REGQ, DCNT
 ;
;=============================================================================;

DIV88 MOVLF 8,DCNT
CLRF REGQ
CLRF REGAX

SUB21 REGAX,REGA,REGB ; REGA = REGA - REGB
BTFSC _C ; initial subtraction should be negative
RETLW -1 ; if Divisor is  greater than dividend

D880 RLF REGA ; REGA = 2* REGA + carry from previous operation
RLF REGAX ; so that carry is in A0

BTFSC REGA,0 ; skip if negative
GOTO D881

RLF REGQ ; Negative result
BCF REGQ,0 ; zero shifted into quotient
BCF REGA,0 ; clear saved carry from dividend
ADD21 REGAX,REGA,REGB ; REGA = REGAA + REGB
GOTO D882

D881 RLF REGQ ; Positive result
BSF REGQ,0 ; one shifted in
BCF REGA,0 ; clear saved carry
SUB21 REGAX,REGA,REGB ; REGA = REGAA - REGB

D882 DECFSZ DCNT
GOTO D880

RLF REGQ,W
MOVWF REGAX
BTFSC REGAX,0
RETLW 0
ADD11 REGA,REGB
RETLW 0



__________________________________________
David C Brown
43 Bings Road
Whaley Bridge
High Peak                           Phone: 01663 733236
Derbyshire                eMail: @spam@dcb.homeKILLspamspamgmail.com
SK23 7ND          web: http://www.bings-knowle.co.uk/dcb
<http://www.jb.man.ac.uk/~dcb>



*Sent from my etch-a-sketch*

On 6 September 2017 at 21:39, Walter Banks <KILLspamwalterKILLspamspambytecraft.com> wrote:

{Quote hidden}

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

2017\09\07@103408 by smplx

flavicon
face


On Thu, 7 Sep 2017, David C Brown wrote:

{Quote hidden}

Next time how about you cut straight to the chase, present your code and say something like "hey does anybody know how to do division better than this".

And here's a tip for you, if you think you might be sounding sarcastic (and in this case it comes across in spades) then just do yourself a favour and leave the comment out.

BTW "there contemporaries" should be "their contemporaries"

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

2017\09\07@110339 by David C Brown

picon face
__________________________________________
David C Brown
43 Bings Road
Whaley Bridge
High Peak                           Phone: 01663 733236
Derbyshire                eMail: RemoveMEdcb.homeTakeThisOuTspamgmail.com
SK23 7ND          web: http://www.bings-knowle.co.uk/dcb
<http://www.jb.man.ac.uk/~dcb>



*Sent from my etch-a-sketch*


I didn't have solid code at the  time I first asked the question and didn't
want to spend hours testing if someone had a better algorithm.

If I had taken your advice and to leave the comment out because of fear of
sarcasm I would have failed to make the wonderful point about how clever
those early computer pioneers were.
 Thank you for your correction to my grammar which you are well aware was
a typographical rather than a grammatical error.


{Quote hidden}

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

2017\09\07@131644 by smplx

flavicon
face


On Thu, 7 Sep 2017, David C Brown wrote:

> The basic non restoring algorithm must have been developed by Turing or
> Wilkes or one of there contemporaries back in the fifties.   For interest,
> or not, This my take on it. - 55 memories, 2 working registers,  worst case
> 156 instructions.  Please criticise to your hearts content

I belive you meen something like the following:

int frac_div(int x, int y)
{
       int        res;

       res  = 0;

       x -= y;

       for (int j=16; j>0; j--)
       {
               res <<= 1;

               if ((x & 0x8000) != 0)
               {
                       // x < 0  i.e. x is < y

                       // x = (x - y) * 2
                       // i.e. x = (x * 2) - (y * 2)
                       x <<= 1;

                       // x = (x * 2) - (y * 2) + y
                       // i.e. x = (x * 2) - y
                       x += y;
               }
               else
               {
                       // x >= 0 i.e. x >= y

                       // x = x * 2
                       x <<= 1;

                       // x = (x * 2) - y
                       x -= y;

                       res |= 1;
               }
       }

       return res;
}

I misunderstood. From your original post I thought you were having difficulty forming a fraction from two integers.

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

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