The algorithm in your code is using the bisection method, which has some advantages. It emphasizes reliability over speed. Common algorithms for solving nonlinear equations of one variable are

• The bisection method
• Newton's method
• The secant method

There is a nice section on some of this in Mastering Algorithms with Perl.

Much of the work on numerical methods is published in fortran, most of which is easy to translate to perl. square root function in fortran from netlib shows a nice loop for iterating the approximation, which I translated to perl here:

while ($i++< $iterations)
{
  $sqrt = $sqrt + 0.5*($y - $sqrt**2) / $sqrt;
}
[download]

It would be interesting to compare this loop to yours.

The netlib code also includes a first guess for the square root function based on a polynomial approximation. This approximation only works for numbers within some range of values, so normalization is used to get within this range. For example, you might start with the number 1000, so you divide it by 4 until it is less than 2 but greater than 0.5. When done, you multiply the square root that you found by 2**(number_of_divides).

The other thing that the netlib code does is to calculate the number of iterations that are needed, based on your available machine precision. It also deals with error conditions, and the case where the normalization of the number involves making it larger instead of smaller. I'll leave that as an exercise for the student.

use strict;
my $i=0;
my $iterations=10;
my $y=1e6;
my $divs=0;
 
while ($y > 2)
{
  $y = $y/4;
  $divs++;
}
 
my $sqrt= 0.261599e0 + $y*(1.114292 + $y * (-0.516888 + $y * 0.141067 
+));
 
while ($i++< $iterations)
{
  $sqrt = $sqrt + 0.5*($y - $sqrt**2) / $sqrt;
  print $sqrt,"\n";
}
 
print $sqrt*(2**$divs),"\n";
[download]

This code converges very quickly, only two iterations are really needed in this example.

It's a fairly unusual hobby to work on numerical methods, but you can quickly pick up quite a bit of math while your at it, and you get to really understand what is going on in your computer. For instance, some modern processors have dedicated square root hardware that implements a square root algorithm directly in silicon.

The downside of numerical methods is that it requires exquisite attention to detail and testing. People spend years on this sort of thing, so it is a good idea to borrow known-good algorithms and code whenever possible. That's why the code tends to remain in fortran for so long.

It should work perfectly the first time! - toma