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

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_OUTrsf5335TakeThisOuTviars.com.br
.....benvenutKILLspam@spam@conex.com.br
=======================================================================
1996\06\06@214151
by
Steve Hardy
> From: Ronald Luis Benvenutti <rsf5335KILLspamPRO.VIARS.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

Hi folks,
Here's another square root routine for you: it takes a 16bit
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 (2n1) < 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
Email: .....daveKILLspam.....daveltd.co.uk
1996\06\09@112042
by
fastfwd

David Knell <EraseMEPICLISTspam_OUTTakeThisOuTMITVMA.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 previouslyposted 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  fastfwdspam_OUTix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499
1996\06\09@115021
by
fastfwd

Ronald Luis Benvenutti <@spam@PICLISTKILLspamMITVMA.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 preconditioning. The following is the
QuickBASIC version of the squareroot 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" SquareRoot Finder.
rem 26 July 1994.
rem
rem For 16bit 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 16bit subtract (with a test for negative result), an 8bit
rem increment, and an "add 2".
rem
rem For 16bit radicands, "root" will always be in the range [0255]
rem and "s" will always be in the range [1511].
start:
input "Radicand (065535): ";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  KILLspamfastfwdKILLspamix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499
1996\06\11@044736
by
fastfwd

Dudes:
Just a quick note... David Knell and I have been discussing the
squareroot 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
completelywrong 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 fullycorrected 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  RemoveMEfastfwdTakeThisOuTix.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...