Searching \ for ' 24 bit square root on a 16f84' 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/devices.htm?key=16F
Search entire site for: '24 bit square root on a 16f84'.

No exact or substring matches. trying for part
PICList Thread
'[PICLIST] 24 bit square root on a 16f84'
2002\03\30@125616 by Giorgio De Nunzio

flavicon
face
Hi all!
From time to time this kind of questions are back...
I need a good 24 bit Square root (binary restoring) routine for the 16f84.
I have seen the one at
http://www.piclist.com/techref/microchip/math/sqrt/sqrt24.htm but it is
for the 17c43 and contains an instruction I am not understanding: movfp.
The other instructions are easily understandable even if I do not know the
17c43.
Can someone help, with a specific 16f84 routine or simply by explaining to
me what that instructions is used for, so that I can translate it in 16f84
language?
Thanks!
Ciao
Giorgio

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.


2002\03\30@144024 by John Dammeyer

flavicon
face
This works.  Bytecraft C has long equal to 16 bit integer so you can see
functions have a high 16 bit and a low 16 bit.  EQ32 sets up the
variables and eq32() does the subtration to test for equality.



long
sqrt32(void) {
 WORD r @ local6;
 WORD i;
       // Handle special cases.
   EQ32(ArgsqrtHi,ArgsqrtLo,0,0)
   if ( eq32() ) return(0);
   i = 0;
   r = 1;
   do {
           SUB32(ArgsqrtHi,ArgsqrtLo,0,r);
       r += 2;
       i++;
   }
   while (ArgsqrtHi >= 0);

   return(i);
}


Regards,

John Dammeyer


> {Original Message removed}

2002\03\31@003049 by Scott Dattalo

face
flavicon
face
On Sat, 30 Mar 2002, Giorgio De Nunzio wrote:

> Hi all!
> >From time to time this kind of questions are back...
> I need a good 24 bit Square root (binary restoring) routine for the 16f84.
> I have seen the one at
> http://www.piclist.com/techref/microchip/math/sqrt/sqrt24.htm but it is
> for the 17c43 and contains an instruction I am not understanding: movfp.
> The other instructions are easily understandable even if I do not know the
> 17c43.
> Can someone help, with a specific 16f84 routine or simply by explaining to
> me what that instructions is used for, so that I can translate it in 16f84
> language?

Andy David (the author of the routine to which you refer), based his
algorithm on the 16-bit routine I wrote for the midrange family:

http://www.dattalo.com/technical/software/pic/picsqrt.html

You can get some idea on the general algorithm here:

http://www.dattalo.com/technical/theory/sqrt.html

I'd like to say that extending the 16-bit routine to 24 bits is straight
forward. Unfortunately, I don't like to lie. If I extended it, I'd
probably go to 32-bits and optimize when needed for 24-bits.

Oh, and of no use to you..., I finally linked in my 18cxxx 16-bit square
root routine:

http://www.dattalo.com/technical/software/pic/sqrt18.asm

It had been sitting on the server collecting dust.

Scott

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


2002\03\31@025832 by Giorgio De Nunzio

flavicon
face
>>>>>>>>>>> John Dammeyer wrote
...

Thanks for your help, John! In point of fact I was looking for a (already
optimized) asm routine, not C, but as it seems that I will have to
convert/adapt/write down the routine myself, your C function may be
useful!
Thanks!
Giorgio


>>>>>>>>>>> Scott Dattalo wrote:

> Andy David (the author of the routine to which you refer), based his
> algorithm on the 16-bit routine I wrote for the midrange family:

Thanks, Scott! Sometime during the night I have found your useful pages,
and I was studying the routine. I admit that - having so little time to
play - I hoped to find a ready-to-use 24 bit routine, but I am sitting
down with pen and paper and I am trying to figure out how things can be
adapted to my problem.

> I'd like to say that extending the 16-bit routine to 24 bits is straight
> forward. Unfortunately, I don't like to lie. If I extended it, I'd
> probably go to 32-bits and optimize when needed for 24-bits.

OK, thanks for your advice.

Giorgio

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


2002\03\31@032413 by John Dammeyer

flavicon
face
Hi Giorgio,

Since the asmembler version of that algorithm can be extremely well
optimized to the point of not being readable the C version may help you
out.   I picked it up from a very old Embedded Systems magazine which I
no longer have.  It's much faster than the Newton Raphson method.

Cheers,

John


> {Original Message removed}

2002\03\31@222520 by Scott Dattalo

face
flavicon
face
On Sat, 30 Mar 2002, John Dammeyer wrote:

{Quote hidden}

I've always liked this algorithm for its simplicity. The sum of the first
N odd integers is equal to N^2... Unfortunately, this can be rather slow
if N is a large number. This though inspired me to dust off and polish
some old square root algorithms. Each of theses makes only one iteration
for each needed bit (e.g. 12 iterations for 12 bits in the result):


unsigned int isqrt1(unsigned int N)
{

 unsigned int s1 = 1<<(6+RESULT_SIZE);
 unsigned s2 = 0;

 do {

   if((s1 + s2) <= N) {

     N = N - s2 -s1;
     s2 = s2 | (s1<<1);
   }

   s1 = s1 >> 1;
   N  = N  << 1;

 } while(s1 > (1<<6));

 return(s2>>(4 + RESULT_SIZE/2));


}

This is the one I developed for the first 16-bit square root routine for
the PIC about 3 or 4 years ago. BTW, I don't claim to be the first to
discover this. Especially since shortly after writing this I came across a
book written in the '60's by Ivan (?) Flores. I don't even recall the
title of the book. But in there I came across the binary square root
algorithm. It was not too unlike the routine above, at least in concept.
This inspired the second square root routine I wrote for the PIC. Here it
is more or less in C:

unsigned int isqrt2(unsigned int N)
{

 unsigned int mask = 3<<(6+RESULT_SIZE);
 unsigned int root = 1<<(6+RESULT_SIZE);

 do {

   if(root <= N) {

     N = N - root;
     root |= mask;
   }

   mask >>= 1;
   root ^= mask;
   N  <<= 1;

 } while(mask > (1<<6));

 return(root>>(4 + RESULT_SIZE/2));


}

For reasons that are not completely obvious, these routines work :). The
hand written assembly code that implements these are fairly well
commented.

In each routine, RESULT_SIZE is a compile time defined constant (that must
be even...) that defines the size of the result in bits. So for a 12-bit
routine:

#define RESULT_SIZE 12


Here's a simple loop to run through all possible test cases.


int
main(int argc, char **argv)
{
 int i;

 printf(" An integer square root routine\n");
 for(i=0; i<((1<<RESULT_SIZE) - 1); i+=1)
   if(isqrt2(i) != isqrt1(i))
      printf(" %d %d %d\n", i,isqrt1(i),isqrt2(i));

 return 0;
}


FWIW, sdcc compiles isqrt1 to 0x47 instructions, and isqrt2 to 0x33
instructions. The hand written version is about 0x1c words. Hmm, I
need to work on sdcc some more...

Scott

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



'[PICLIST] 24 bit square root on a 16f84'
2002\04\01@170158 by Bob Barr
flavicon
face
On Sat, 30 Mar 2002 18:06:21 +0100, Giorgio De Nunzio wrote:

>Hi all!
>From time to time this kind of questions are back...
>I need a good 24 bit Square root (binary restoring) routine for the 16f84.
>I have seen the one at
>http://www.piclist.com/techref/microchip/math/sqrt/sqrt24.htm but it is
>for the 17c43 and contains an instruction I am not understanding: movfp.
>The other instructions are easily understandable even if I do not know the
>17c43.


The 'p' in the 'movfp' mnemonic indicates that it's a special-case
variation of the 'movf' instruction. The 'p' indicates that it is
using a data address of 0x1f or less. (The 16C43 allows register-to-
register moves using that low range for one of the addresses.) You can
safely substitute a 'movf' for these.


The rotate instructions used in the routine are the 17C43 versions
that perform the rotate through the carry bit. Since that's the way
the '84 always does its rotates, they'll work fine by substituting
'rlf' and 'rrf' for the 'rlcf' and 'rrcf' respectively. (The 17C43 has
'rlncf' and 'rrncf' instructions that allow you to rotate just the
register contents, bypassing the carry bit.)


The only two instructions that don't have straightforward
substitutions are the 'subwfb' and 'addwfc' instructions.

For 'subwfb' (subtract with borrow), you'll need to check for a
borrow from the first subtraction. If a borrow resulted from this
subtraction, you'll need to do a 'subwf', and then decrement that
result. If there was no borrow  generated from the first subtraction,
the subwf by itself will do the job for the second one.

Similarly, for the 'addwfc' (add with carry), you'll need to increment
the result of the second addition if the carry was set by the first
addition.

Oops, I almost forgot:

In either case, you may need to be careful regarding the final carry
that results.
Using a 'decf' or 'incf' to adjust the second result will leave the
carry bit set/cleared as it was by that second operation. The carry
state will be incorrect in some circumstances. If you 'decf' a 0 to
0xff, you won't get the borrow that you should. Similarly, if you
'incf' a 0xff result to 0, you won't get the carry that you should.


Regards, Bob

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


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