Searching \ for 'SQRT ROUTINE' 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/index.htm?key=sqrt+routine
Search entire site for: 'SQRT ROUTINE'.

Truncated match.
PICList Thread
'SQRT ROUTINE'
1996\06\06@155107 by Ronald Luis Benvenutti

flavicon
face
Hi all:

To solve the problem of SQRT calculation, I'm sending the following simpe
routine I've been using for years.
The code is in C, but is easily convertible to PIC or another microcontroller.
This routine extracts a SQRT of a integer (16 bits), but can be easily converted
to more bits.

#include <stdio.h>
void main(void)
{
unsigned int n, odd, sqrt, sum;
clrscr ();
while (1)
       {
       printf("\nnumber : ");
       scanf("%d", &n);
       if (n == 0)
               return;
       sum = 0;                       //
       sqrt = 0;                      //
       odd = 1;                       //
       while (sum < n)                //  sqrt routine
               {                      //  input = 16 bits in n
               odd += 2;              //  output = result in sqrt
               sum += odd;            //
               sqrt++;                //
               }                      //
       printf("sqrt(%d) = %d", n, sqrt);
       }
}

The routine does the following:

It sums all odd numbers until the sum reaches the number 'n'. The number of
iterations
(sums) is the integer sqrt of 'n'.

Is there something so simple ?

I hope it can help.

======================================================================
Ronald Luis Benvenutti
Porto Alegre - RS - Brazil

spam_OUTrsf5335TakeThisOuTspamvia-rs.com.br
.....benvenutKILLspamspam@spam@conex.com.br
=======================================================================

1996\06\06@214151 by Steve Hardy

flavicon
face
> From: Ronald Luis Benvenutti <rsf5335spamKILLspamPRO.VIA-RS.COM.BR>
>
> Hi all:
>
> To solve the problem of SQRT calculation, I'm sending the following simpe
> routine I've been using for years.
[program deleted]
> It sums all odd numbers until the sum reaches the number 'n'. The number of
> iterations
> (sums) is the integer sqrt of 'n'.
>
> Is there something so simple ?
>

It's OK, but a bit slow.  Worst/average case is about 2**8/2**7
iterations which is way over to 150 or so cycles needed for the other
algorithms presented.  However, being simpler it probably takes up a
bit less ROM space.  Why don't you code it up in snappy PIC assembler?

Regards,
SJH
Canberra, Australia

1996\06\09@072746 by David Knell

flavicon
face
Hi folks,

Here's another square root routine for you: it takes a 16-bit
number in inlo, inhi and ends up with its square root in W.
It uses 11 program words and destroys the input but otherwise
uses no file registers.  Execution time is something like
5+7r cycles, where r is the result.

It's algorithmically about equivalent to:

int sqrt(int in)
{
       int result = 0;
       in >>= 1;
       do {
               result ++;
               in -= result;
       } while (in > 0)
       return result;
}

The value returned is an integer which is loosely defined as
about the square root of the number presented.  The error
comes from it effectively finding the highest n such that
n
sum n < input/2, rather that
1

n
sum (2n-1) < input
1

I guess I could claim that it makes a better job of returning
the nearest integer to the square root of the number than the
previous routines posted.

sqrt:   MOVLW   0
       CLRC
       RRF     inhi
       RRF     inlo
       INCF    inhi
loop:   ADDLW   1
       SUBWF   inlo
       SKPC
       DECF    inhi
       SKPZ
       GOTO    loop

I think it's OK - I ran it quickly on the simulator and the
results are as expected.

Dave
------------------------------------------------------------
David Knell
Tel: 01843 846558
Fax: 01843 846608
E-mail: .....daveKILLspamspam.....dave-ltd.co.uk

1996\06\09@112042 by fastfwd

face
flavicon
face
David Knell <EraseMEPICLISTspam_OUTspamTakeThisOuTMITVMA.MIT.EDU> wrote:

> The value returned is an integer which is loosely defined as
> about the square root of the number presented.  The error
> comes from it effectively finding the highest n such that
> n
> sum n < input/2
> 1
> ....
> I guess I could claim that it makes a better job of returning
> the nearest integer to the square root of the number than the
> previous routines posted.

David:

It certainly does not.  It finds NEARBY integers; not "the nearest"
integer.  All the previously-posted solutions, on the other hand, DO
find the nearest integer.

Of course, I could be misunderstanding your claim (your initial
comment that your routine finds a number "loosely defined as about
the square root" would tend to support this hypothesis).  Are you saying,
perhaps, that your routine finds the integer nearest to the integer
nearest to the square root of the input?

-Andy

Andrew Warren - fastfwdspamspam_OUTix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499

1996\06\09@115021 by fastfwd

face
flavicon
face
Ronald Luis Benvenutti <@spam@PICLISTKILLspamspamMITVMA.MIT.EDU> wrote:

> To solve the problem of SQRT calculation, I'm sending the following
> simpe routine I've been using for years.
> ....
> The routine does the following:
>
> It sums all odd numbers until the sum reaches the number 'n'. The
> number of iterations (sums) is the integer sqrt of 'n'.
>
> Is there something so simple ?

Ronald:

As Steve Hardy has pointed out, the routine as written is quite slow.
However, it can be improved (at the expense of a little extra code
space) by performing a little pre-conditioning.  The following is the
QuickBASIC version of the square-root routine I posted here about a
year and a half ago; it uses the same algorithm as your routine, with
a few additional "if x = ...." lines at the start.

--------------------------------------------------------------------
rem Andy Warren's "Two Adds and a Subtract" Square-Root Finder.
rem 26 July 1994.
rem
rem For 16-bit radicands, this algorithm will make a maximum of 127
rem passes through the "mainloop" loop.  On average, it'll make 60
rem passes.  This seems like a lot, but each pass involves just one
rem 16-bit subtract (with a test for negative result), an 8-bit
rem increment, and an "add 2".
rem
rem For 16-bit radicands, "root" will always be in the range [0-255]
rem and "s" will always be in the range [1-511].

start:

   input "Radicand (0-65535): ";x

rem The following 6 "if" statements are included only for speed of
rem execution (they approximately double the average computation
rem speed).  They can be removed if program size is more important.

       if x > 16383 then x = x - 16384: root = 128: s = 257: goto main
       if x > 4095  then x = x - 4096:  root = 64:  s = 129: goto main
       if x > 1023  then x = x - 1024:  root = 32:  s = 65:  goto main
       if x > 255   then x = x - 256:   root = 16:  s = 33:  goto main
       if x > 63    then x = x - 64:    root = 8:   s = 17:  goto main
       if x > 15    then x = x - 16:    root = 4:   s = 9:   goto main

       root = 0: s = 1

main:

   x = x - s: if x < 0 then goto done

       root = root + 1: s = s + 2

       goto main

done:

   print "Square root = "; root: print

       goto start
-------------------------------------------------------------------

-Andy

Andrew Warren - KILLspamfastfwdKILLspamspamix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499

1996\06\11@044736 by fastfwd

face
flavicon
face
Dudes:

Just a quick note... David Knell and I have been discussing the
square-root routine that he posted last week, and a couple of
interesting points have come up.

David points out that all the routines that the rest of us have
posted find the highest integer not greater than the square root; his
algorithm finds the NEAREST integer.  For example, his routine will
return 6 as the square root of 35; all the rest return 5.

This is a useful property; anyone who can afford the time that his
routine requires should consider using it.

Ok... A couple other things have come up in our discussion.  Here's
David's routine as originally posted:

           MOVLW   0
           CLRC
           RRF     INHI
           RRF     INLO
           INCF    INHI

       LOOP:
           ADDLW   1
           SUBWF   INLO
           SKPC
           DECF    INHI
           SKPZ
           GOTO    LOOP

There's a minor coding error there:  Since the "SUBWF" affects the Z
flag as well as the "DECF" does, the routine will occasionally give
completely-wrong results.

Fortunately, the fix is real easy; the "DECF INHI, SKPZ" combination
merely has to be replaced with a "DECFSZ INHI".  This has the added
benefit of speeding up the code by 15%.

Also, the routine won't handle inputs above 65280 (FF00 hex), because
it tries to round the square roots of those numbers up to 256, which
won't fit in 8 bits.  Additionally, it gives "1" as the square root
of 0.  Each of these problems can be corrected with the addition of
only a few lines of code; correcting for 0 takes three instructions
and correcting for >65280 takes four.  The fully-corrected version of
the code is as follows:

           MOVF    INHI,W  ;CORRECT FOR 0.
           BZ      DONE    ;

           INCF    INHI,W  ;CORRECT FOR >65280.
           SWAPF   INHI,W  ;
           BZ      DONE    ;

           MOVLW   0
           CLRC
           RRF     INHI
           RRF     INLO
           INCF    INHI

       LOOP:
           ADDLW   1
           SUBWF   INLO
           SKPC
           DECFSZ  INHI
           GOTO    LOOP

       DONE:

With these changes, the routine works fine and still only requires 17
words of program space and no RAM other than the two registers which
hold the input.  It still isn't EXACTLY right when the square root is
something like x.49999, but this is a very minor issue; I mean, who
really cares whether the square root of 20022 (141.4991166) is
rounded to 141 or 142?

-Andy

Andrew Warren - RemoveMEfastfwdTakeThisOuTspamix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499

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