"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.

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

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

Thanks for all the useful answers!

Michael

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

Spehro Pefhany wrote:

> On Mon, 29 Mar 2004 15:05:27 -0700, the renowned MikeM
> <trashcan@yahoo.com> wrote:
> 
> 
>>I just coded up another hack:
>>unsigned char foo;
>>unsigned int RPM;
>>    ...
>>   	LED = 1;				//begin scope loop
>>	foo = 1;
>>		
>>	while ((foo*foo) << RPM)
>>		foo++;
>>		
>>	LED = 0;				//end scope loop
>>		
>>		
>> With the processor running on a 49Mhz SYSCLOCK, it takes < 27us
>>for the worst case (answer = 255).
> 
> 
> how about something like: 
>  
> 
> unsigned char msqrt(unsigned int a)
>   {
>   if 
>   unsigned char m,n,s,i; 
>   if (a > 65024) return 255; 
>   m = 255; n=0;
>   for (i=0;i<8;i++)  /* binary search */
>     {
>     s = (m+n)/2;
>     if ((s*s) <=a) n = s; else m = s;
>     }
>   return s; 
>   }
> 
> 
> 
> Best regards, 
> Spehro Pefhany



7.3us at 49Mhz

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

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

>I just coded up another hack:
>unsigned char foo;
>unsigned int RPM;
>     ...
>    	LED = 1;				//begin scope loop
>	foo = 1;
>		
>	while ((foo*foo) << RPM)
>		foo++;
>		
>	LED = 0;				//end scope loop
>		
>		
>  With the processor running on a 49Mhz SYSCLOCK, it takes < 27us
>for the worst case (answer = 255).

how about something like: 
 

unsigned char msqrt(unsigned int a)
  {
  if 
  unsigned char m,n,s,i; 
  if (a > 65024) return 255; 
  m = 255; n=0;
  for (i=0;i<8;i++)  /* binary search */
    {
    s = (m+n)/2;
    if ((s*s) <=a) n = s; else m = s;
    }
  return s; 
  }



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

MikeM wrote:

> I just coded up another hack:
> unsigned char foo;
> unsigned int RPM;
>     ...
>        LED = 1;                //begin scope loop
>     foo = 1;
>        
>     while ((foo*foo) << RPM)
>         foo++;
>        
>     LED = 0;                //end scope loop
>        
>        
>  With the processor running on a 49Mhz SYSCLOCK, it takes < 27us
> for the worst case (answer = 255).
> 
> 
> 

Whoops, that should have been:
	while ((foo*foo) < RPM)

Now it takes 330us for the worst case...

I just coded up another hack:
unsigned char foo;
unsigned int RPM;
     ...
    	LED = 1;				//begin scope loop
	foo = 1;
		
	while ((foo*foo) << RPM)
		foo++;
		
	LED = 0;				//end scope loop
		
		
  With the processor running on a 49Mhz SYSCLOCK, it takes < 27us
for the worst case (answer = 255).

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?

Since there are only 256 roots, the table could be shorter.
I'd have a table of 256 squares and do a reverse binary search.

Rene
-- 
Ing.Buero R.Tschaggelar - http://www.ibrtses.com
& commercial newsgroups - http://www.talkto.net