Distance timing out

Technical Programming
1

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?

2

square root calculations are the worst

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

3

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

4

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.

5

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;
}
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>

6

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.