Integer square root routine needed.

[Ken Johnson]

>In article <7415 at ecsvax.UUCP>, utoddl at ecsvax.UUCP (Todd M. Lewis) writes...
>> 
>>This may be the wrong place to post this, but I need C source
>>to a reasonably fast integer square root routine.
>>The wheel I'm inventing is a library of matrix operations for
>>3-D graphics for Yet Another Ultimate Space Game.

In article <68259 at yale-celray.yale.UUCP> leichter at CS.YALE.EDU (Jerry
Leichter) writes:

> computing Euclidean distances (sqrt(a^2 + b^2)), ...

If all you're doing is of the form

  if (distance_between(point1,point2) < threshhold)
  {
   ...
  }

  distance_between(point1,point2)
  struct point *point1, *point2;
  {
	return(sqrt((point1->x - point2->x)^2 + (point1->y - point2->y)^2));
  }

and the square root is only needed to compute distance_between
by Pythagoras, you may be able to substitute

  threshhold_squared = threshhold * threshhold;

  if (squared_distance_between(point1,point2) < threshhold_squared)
  {
   ...
  }

  squared_distance_between(point1,point2)
  struct point *point1, *point2;
  {
	return((point1->x - point2->x)^2 + (point1->y - point2->y)^2);
  }

and get around the problem that way. (If the numbers involved are big,
shift both X and Y differences before squaring.)
-- 
Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN
E-mail ken at aiai.ed.ac.uk, phone 031-225 4464 extension 212
`I have read your article, Mr.  Johnson, and I am no wiser than when I
started.' -- `Possibly not, sir, but far better informed.'