Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!mcvax!ukc!etive!aiai!ken
From: ken@aiai.ed.ac.uk (Ken Johnson)
Newsgroups: comp.lang.c
Subject: Re: Integer square root routine needed.
Message-ID: <660@skye.ed.ac.uk>
Date: 2 Aug 89 10:39:10 GMT
References: <68259@yale-celray.yale.UUCP>
Reply-To: ken@aiai.UUCP (Ken Johnson)
Organization: AIAI, University of Edinburgh, Scotland
Lines: 48

>In article <7415@ecsvax.UUCP>, utoddl@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@yale-celray.yale.UUCP> leichter@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@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.'