Searching \ for 'SQRT ROUTINE' in subject line. ()
Help us get a faster server
FAQ page: massmind.org/techref/index.htm?key=sqrt+routine
Search entire site for: 'SQRT ROUTINE'.

Truncated match.
'SQRT ROUTINE'
1996\06\06@155107 by

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

rsf5335via-rs.com.br
benvenutconex.com.br
=======================================================================

> From: Ronald Luis Benvenutti <rsf5335PRO.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

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.

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
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: davedave-ltd.co.uk

David Knell <PICLISTMITVMA.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.

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 - fastfwdix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499

1996\06\09@115021 by
Ronald Luis Benvenutti <PICLISTMITVMA.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:

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 - fastfwdix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499
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:
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:
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 - fastfwdix.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...