8051: square root of unsigned short

On Mon, 29 Mar 2004 17:03:17 -0700, the renowned MikeM
<trashcan@yahoo.com> wrote:

>Spehro Pefhany wrote:
>

>7.3us at 49Mhz

Okay. 

>minor nit:
>    for (i=0;i<8;i++)  /* binary search */ should be:
>    for (i=0;i<=8;i++)  /* binary search */

Yes, or <9. 

Best regards, 
Spehro Pefhany
-- 
"it's the network..."                          "The Journey is the reward"
speff@interlog.com             Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog  Info for designers:  http://www.speff.com

Thanks for all the useful answers!

Michael

Michael Koch wrote:
> 
> For a 8051 controller, I need a fast algorithm for
> calculating the square root of an unsigned 16-bit word. The
> result is unsigned 8-bit.
> I know the fastest method would be a 64kB lookup table, but
> unfortunately I have only 32kB available. Any ideas?

At most you have 256 possible roots, thus a table of 256
boundaries will suffice, occupying at most 512 bytes.  You can
even do a binary search of that table.  You create the table by
squaring values from 0 through 255.

-- 
fix (vb.): 1. to paper over, obscure, hide from public view; 2.
to work around, in a way that produces unintended consequences
that are worse than the original problem.  Usage: "Windows ME
fixes many of the shortcomings of Windows 98 SE". - Hutchison

Since your results are in the range 0-255 simply create a table of those 
results and use a binary search to find the closest value.

Al

Michael Koch wrote:

> Hi,
> 
> For a 8051 controller, I need a fast algorithm for
> calculating the square root of an unsigned 16-bit word. The
> result is unsigned 8-bit. 
> I know the fastest method would be a 64kB lookup table, but
> unfortunately I have only 32kB available. Any ideas?
> 
> Thanks,
> Michael

-- 
Please remove capitalised letters to reply
My apologies for the inconvenience
Blame it on the morons that spam the net

"onestone" <onestoneXYZ@ABCbigpond.net.au> wrote in message
news:epxdc.1579$ED.834@news-server.bigpond.net.au...
> Since your results are in the range 0-255 simply create a table of those
> results and use a binary search to find the closest value.
>
> Al
>
> Michael Koch wrote:
>
> > Hi,
> >
> > For a 8051 controller, I need a fast algorithm for
> > calculating the square root of an unsigned 16-bit word. The
> > result is unsigned 8-bit.
> > I know the fastest method would be a 64kB lookup table, but
> > unfortunately I have only 32kB available. Any ideas?
> >
> > Thanks,
> > Michael

> Michael Koch wrote:
>
> > Hi,
> >
> > For a 8051 controller, I need a fast algorithm for
> > calculating the square root of an unsigned 16-bit word. The
> > result is unsigned 8-bit.
> > I know the fastest method would be a 64kB lookup table, but
> > unfortunately I have only 32kB available. Any ideas?
> >
> > Thanks,
> > Michael
There's a REALLY simple algorithm for integer square roots, its not the
fastest in the world, but may fit in well with the 51's arithmetic
capabilities, and would be really compact code. Consider this series
n     int(sqrt(n))     n     int(sqrt(n)
0     0                 10     3
1     1                 11     3
2     1                 12     3
3     1                 13     3
4     2                 14     3
5     2                 15     3
6     2                 16     4
7     2
8     2
9     3

So there's 1 occurrence of 0
                3                   of 1
                5                   of 2
                7                   of 3
etc. etc.
So you could subtract 1,3,5,7 and so on from your original value until you
got a negative result. Count the number of subtractions, and that gives you
the square root.

I'm sure you could cut the average time down by precalculating a starting
position for if the original value is more than say, 32767.

Sorry if anyone has already posted this - I missed the original posting.

Peter.