Rob Basler rambled on to All:

 RB> I need an algorithm for calculating square roots to 3 or 4
 RB> decimal places.  It must be fast, I don't care about
 RB> complexity as long as you can explain it to me well enough
 RB> for me to implement, and it only needs to calculate square
 RB> roots in the range 0 to 2M.

Well, if you can get a good first guess using some table look up, then
Newton's method will work just fine:

double sqrt(double a)
{
  double tol = 1e-10;
  double x = a; /* substitute a good guess here */
  int i;
  for (i=0;i<5;++i) x = (x + a/x)/2;
  printf("sqrt of %f is %f\n",a, x);
  return x;
}

For a crude good guess, take a number with half the number of digits + 1
(round up) and a leading term that is the sqrt of a's leading term.  eg
   

     a         guess for sqrt(a)     Actual sqrt (to 3 digits)
   1000              100                     31.6
   43209             200                     207
  2309824           2000                     1520

This should get about 1 digit of accuracy for the guess and so the above
algorithm should require, at most about 5 iterations to get 3 digits of 
accuracy.  If you can actually get one digit of accuracy with a table look
up (table size of about 40)

 RB> If you need incentive, this is going into an OS/2
 RB> shoot'em-up 3D video game. 

I look forward to hearing about your progress!

TTYL,

=--Ron  TeamOS2

Fidonet:  Ronald Van Iwaarden 1:104/338{at}fidonet.org
OS2net:   Ronald Van Iwaarden 81:313/1{at}os2net.ftn
Internet: rvaniwaa{at}carbon.denver.colorado.edu
--- timEd/2-B9