Distance timing out

[bludstayne]

I have a problem. Whenever I try to find distance between two points the robot controller times out due to the square root calculations. We have a coordinate system of approximately 768x1280 units. Do you think a lookup table would be too large?

[KenWittlief]

square root calculations are the worst

can you leave the number squared and work with it that way?

[Astronouth7303]

How about having it go to, say, 1 decimal point? with such a large system, you don't need it that precise. And the field is 24' by 48'.

[Joe Ross]

Yes, that would be to big for a standard lookup table. That would be almost a megabyte, if you only looked up a single byte. If you were doing it with floats, it would be even bigger.

[seanwitte]

Here you go. This based on an algorithm I found on Microchip's web site. It is supposedly optimized for the PIC series chips and will always loop 9 times.

//return the square root of an unsigned 16 bit integer
//based on sample from microchip.com
unsigned int Sqrt16(unsigned int val)
{
	unsigned int mask = 0x100;
	unsigned int result = 0x80;
	
	while (mask > 0)
	{
		if ((result * result) > val)
		{
			result &= ~mask;
		}
		mask >>= 1;
		result |= mask;
	}
	return result;
}

<edit>
Sorry, I wasn't paying attention. You need a 32-bit version:

//Return the square root of value x where x is an integer. This
//is based on the fast square root algorithm from microchip.com. 
unsigned long sqrt32(unsigned long x)
{	
	unsigned long mask = 0x1000;
	unsigned long result = 0x800;

	while (mask > 0)
	{
		if ((result * result) > x)
		{
			result &= (~mask);
		}
		mask >>= 1;
		result |= mask;
	}
	return result;
}

</edit>

[Alan Anderson]

Originally Posted by bludstayne

I have a problem. Whenever I try to find distance between two points the robot controller times out due to the square root calculations...

Do you actually need to compute the square root, or can you do what you need to with the square of the distance? For instance, if you're comparing the distance to a constant value, you can change the constant to be the square of what it would otherwise be.