[PIC] Division routines.

[David C Brown]

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: [phone]
Derbyshire eMail: ***@gmail.com
SK23 7ND web: www.bings-knowle.co.uk/dcb
<http://www.jb.man.ac.uk/~dcb>



*Sent from my etch-a-sketch*

[Neil]

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.

Post by David C Brown
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: [phone]
SK23 7ND web: www.bings-knowle.co.uk/dcb
<http://www.jb.man.ac.uk/~dcb>
*Sent from my etch-a-sketch*

[David C Brown]

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: [phone]
Derbyshire eMail: ***@gmail.com
SK23 7ND web: www.bings-knowle.co.uk/dcb
<http://www.jb.man.ac.uk/~dcb>



*Sent from my etch-a-sketch*

Post by Neil
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.

Post by David C Brown
I am trying to find some good 8 and 16 bit division routines for mid

range

Post by David C Brown
PICs. Most of the app notes I have found give algorithms which result

in

Post by David C Brown
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.

Post by David C Brown
__________________________________________
David C Brown
43 Bings Road
Whaley Bridge
High Peak Phone: [phone]
SK23 7ND web: 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
http://mailman.mit.edu/mailman/listinfo/piclist

[Bob Ammerman]

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-----
Of Neil
Sent: Tuesday, September 05, 2017 2:49 PM
Subject: Re: [PIC] Division routines.
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.

Post by David C Brown
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.

Post by David C Brown
__________________________________________
David C Brown
43 Bings Road
Whaley Bridge
High Peak Phone: [phone]
SK23 7ND web: 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
http://mailman.mit.edu/mailman/listinfo/piclist

[smplx]

Post by David C Brown
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

[smplx]

On Tue, 5 Sep 2017, smplx wrote:

enhancement to my own code follows

Post by smplx
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;

Post by smplx
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

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

Post by smplx
return res;
}

Regards
Sergio Masci

[William Westfield]

Post by David C Brown
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!

[Walter Banks]

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;
  }

[smplx]

Post by Walter Banks
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

[Walter Banks]

Post by smplx

Post by Walter Banks
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?

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;
  }

Post by smplx
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.

Post by smplx
Regards
Sergio Masci

[David C Brown]

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: [phone]
Derbyshire eMail: ***@gmail.com
SK23 7ND web: www.bings-knowle.co.uk/dcb
<http://www.jb.man.ac.uk/~dcb>



*Sent from my etch-a-sketch*

Post by Walter Banks

Post by smplx

Post by Walter Banks
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?

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;
}

Post by smplx
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.

Post by smplx
Regards
Sergio Masci

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

[smplx]

Post by David C Brown
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

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

[David C Brown]

__________________________________________
David C Brown
43 Bings Road
Whaley Bridge
High Peak Phone: [phone]
Derbyshire eMail: ***@gmail.com
SK23 7ND web: 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.

Post by smplx
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
http://mailman.mit.edu/mailman/listinfo/piclist

[smplx]

Post by David C Brown
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