8051: square root of unsigned short

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?

Disclaimer:  I am *not* an algorthm expert and
this might be just plain silly to someone who it.

Turn the table inside out.  Make a 256 entry
array of 16-bit values. Make each entry equal
to the square root of it's address. Do a binary
tree search of the table to find the entry and
it's address is your square root.

On Mon, 29 Mar 2004 11:23:45 -0800, the renowned Jim Stewart
<jstewart@jkmicro.com> wrote:

>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?
>
>Disclaimer:  I am *not* an algorthm expert and
>this might be just plain silly to someone who it.
>
>Turn the table inside out.  Make a 256 entry
>array of 16-bit values. Make each entry equal
>to the square root of it's address. Do a binary
>tree search of the table to find the entry and
>it's address is your square root.

It might be just as silly to compute the square of each test number
and do a binary search between 0 and 255. Square is pretty fast on an
8051 because of the MUL instruction. 

One C compiler I just looked at produces run time code that just
starts at 0 and increments the number until the square matches.  8-( 

I'm not sure the old standard of Newton's method would be faster on an
8051 than either Jim's suggest or my first suggestion. 

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

> 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?

I've done it with successive approximation in assembly.
Everything can be done in registers and an 8x8 MUL to a 16-bits result is
only 4 machine cycles. Just remember to start with the MSB test first!

Regards,
Arie de Muynck

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?

I just happen to be banging on a Cygnal C8051F12X development
kit, using the Kiel C compiler.

I just coded up a the following using <math.h>:


unsigned char foo;
unsigned int RPM;
	...	
	LED = 1;
   	foo = sqrt(RPM);
	LED = 0;

With the processor running on a 49Mhz SYSCLOCK, it takes < 75us.
For certain degenerate cases, it returns in about 10us.

MikeM

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

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

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

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

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 */