Optimized Integer Table Square Root Function

From Agar

This routine is used to optimize common square roots. You can adjust the size, bigger means more stored solutions. It is used by some of the other user-submitted code samples, and can be replaced by any of the other similar routines found on other websites. This one is favored for its simplicity. You must call init_isqrt() before using isqrt().

#define MAX_SRT 1000000
float SRT[MAX_SRT];
bool SRT_initialized = FALSE;
 
void
init_isqrt()
{
   int i;
   for (i = 0; i < MAX_SRT; i++ ) {
       SRT[i]=sqrt(i);
   }
   SRT_initialized = TRUE;
}
 
float
isqrt (int i)
{
   i = abs(i);
   if (i > MAX_SRT-1) { return sqrt(i); }
   return SRT[i];
}
 
#define sqrt(x) isqrt(x)

Something like this is commonly used for optimizing distance equations, and should be used whenever possible to increase performance.

Here is an example distance calculation using the above routines:

#define DISTANCE(a,b,c,d)  ( isqrt( (a-c)*(a-c) + (b-d)*(b-d) ) )
 
bool
NEAR(int ax, int ay, int bx, int by, int mindist)
{
    int dx = ax-bx;
    int dy = ay-by;
    return (isqrt(dx*dx + dy*dy) < mindist);
}