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]

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]

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

Hey, cool problem, nysus... I'll throw out my code, first. Be forewarned, though -- I'm nowhere near the pro you asked for.

#!/usr/bin/perl -w
use strict;

sub sqroot {
   my $maxdiff = 1e-18;
   my ($value, $num) = (1, shift @_);
   my $i = '';   # Added
   $num *= -1 and $i = 'i' if ($num < 0);  # Added
   my $oldvalue = 0;
   while (abs($oldvalue - $value) > $maxdiff) {
      $oldvalue = $value;
      $value = $num / $value;
      $value = ($value + $oldvalue) / 2;
   }
 # return $value;  #  (old)
   return $value . $i;
}

my $num;
do {
   print "Please enter a number: "; # changed from "positive number"
   chomp ($num = <STDIN>);
# } until ($num =~ /^\d*[.\d]\d*$/);  #  (old regex)
} until ($num =~ /^-?\d+\.?\d*$/);

my $sqrt = sqroot $num;
print "Square root of $num: $sqrt\n";
[download]

Now, for a few comments:

1. IMO, your code was broken down perhaps a little too much. Of course, depending on what you'll want to do in the future, you may want to do that. But I'd suggest a name such as diff instead of get_accuracy, for two reasons: it is shorter (which I know can be a bad thing in some cases), and it's more descriptive of its function. You're only returning the difference between the two numbers, and I'd prefer something that I'd be able to easily recognize later on, so I could steal it and put it in another program.
2. Also, I moved the print statement out of the subs... once again, it's only my opinion, but I think those things should be outside of the sub (If I call "sqroot", I don't expect it to print anything out. "print_sqrt" on the other hand...)
3. You'll notice I also have a different regex and a do-until loop... the loop style is just personal preference, but I feel the regex is better, as it allows the user to enter in just the number (e.g. "10" vs. "10.0"), however, it may not be the most efficent. I'd like a little feedback from those who know more than I on that, actually...

Once again, considering that optimial is a relative term, you're free to call my ideas ridiculous, if you like. :) Once again, though, cool problem... made me think a good bit. (I'll probably still be thinking about it tomorrow...)

Update: I just couldn't leave well enough alone. Above are modifications to the original script that allow processing of negative numbers, as well as an improved (?) regex. Also changed $maxdiff as per ariels' suggestion.

His Royal Cheeziness

Yes, much better! I actually got the idea for this problem from Structure and Itnerpretation of Computer Programs. The problem in there for finding square roots is written in a language called LISP. I just wanted to try translating it into Perl.

$PM = "Perl Monk's";
$MCF = "Most Clueless Friar Abbot";
$nysus = $PM . $MCF;

Well, first up your regex fails on an integer.

Update:

And I usually shy away from ariels notation, because to me 1e-18 says e^-18 rather than 10^-18. That always bugged me. Personally I'd rather use 10**(-18).

/Update

As for your concern about calling new_guess twice, why not try this?

my $n=0;
Hahaha:


$guess = new_guess($guess, $x); # MAKE OLD GUESS THE NEW GUESS AND RUN
+ WHILE LOOP AGAIN

$n=new_guess($guess, $x);

goto Hahaha if get_accuracy($guess, $n)  > .000000000000000001 { # CHE
+CK DIFFERENCE BETWEEN OLD GUESS AND NEW GUESS
[download]

Actually this should work fine:

        my ($guess, $x) = @_;
 my $n=0;
        while ( get_accuracy($guess, $n)  > .000000000000000001) { # C
+HECK DIFFERENCE BETWEEN OLD GUESS AND NEW GUESS
                $guess = $n;
  $n=new_guess($guess, $x); # MAKE OLD GUESS THE NEW GUESS AND RUN WHI
+LE LOOP AGAIN
        }
[download]

____________________
Jeremy
I didn't believe in evil until I dated it.

Taking <var>x_n+1</var> = (<var>x_n</var>+<var>a</var>/<var>x_n</var>) is Newton's method for taking the square root! (But one should note the name of the method is the Babylonian square root algorithm).

Also, why is everyone saying ".000000000000000001" as the accuracy? Am I the only one who's having trouble counting? Isn't "1e-18" a bit easier on the eyes and the screen?

I remeber for One funny alogorith for fined square root from some numbers :-)

add together odd-numbers from 1 while total sum is greater or equal to input number :-). Count of numbers is root :-))

exam.
root from 9 : 1+3+5=9 number 3
root from 25 : 1+3+5+7+9=25 number 5
root from 100: 1+3+5+7+9+11+13+15+17+19=100 number 10 :-)
easy and funny but works :-)
It's usefull for locating starting number for iteration process.

This algorithm is very fast because use only adding and testing :-)
but today it's irelevant becuase processor are very fast and using math-coprocessor :-).

several years ago thas was easy to creat it for lots of ASM instructions :-))

Here's mine, did someone say GOLF!

cheers

tachyon

print sqroot(2,100);

# long version
sub sqroot {
    $number = shift;
    $iterate = shift;
    $guess = $number;
    for (0..$iterate) {
        $guess = (($number/$guess) + $guess)/2 ;
    }
  return $guess;
}

# golf at 44 strokes
sub sqroot {
    ($n,$i)=@_;$g=$n;$g=($n/$g+$g)/2for 0..$i;$g
}
[download]

well,

if we're golfing this, you can reduce that line a bit:

sub sqroot {
#23456789_123456789_123456789_123456
$g++;$g=($_[0]/$g+$g)/2for-1..pop;$g
}
[download]

At 29 characters. It seems to work correctly on perl5.6

jynx

update: d'oh, i was erroneously fooled by my browser when entering the snippet, it's actually 36 characters...

#!/usr/bin/perl
use strict;
my ($guess,$num);

# get number
while(<STDIN>) {
  $guess = $num = $_+0; last if ($num>0);
}

# iterate until within 1e-13
# go further and you need some math module, I think :)
while (abs($num - $guess**2) > 1e-13) {
    $guess = (($num/$guess) + $guess)/2;
}

# print our guess and what Perl says
print "My guess of square root of $num is $guess\n";
print "Perl says it's ".$num**.5."\n";
[download]

cLive ;-)

PS - golf version? :)

#!/usr/bin/perl
use strict;
my $n;

while(<STDIN>) { $n = $_+0; last if $n>0}

while (abs($n - $_**2) > 1e-13){ $_ = ($n/$_ + $_)/2}

print "Guess: $_\nperl: ".$n**.5."\n";
[download]

I tried your solution on very small numbers such as .000000000323 and the accuracy was way off. I believe it is because you compare the radicand to the square of the guess instead of comparing the last guess to the current guess. At any rate, that is a very short solution, for sure.

$PM = "Perl Monk's";
$MCF = "Most Clueless Friar Abbot";
$nysus = $PM . $MCF;

yep,

Sort of. I think I just mis-read my comparison (got confused coz I was using guess and next guess...)

Change this:

while (abs($num - $guess**2) > 1e-13) {
[download]

to the more accurate comparison (with 2 more decimal places of accuracy):

while (abs($num/$guess - $guess) > 1e-15) {
[download]

and it works fine :)

cLive ;-)

$a=25;
$b=$a**(1/2); # 25^0.5
print $b; # 5
[download]

$a=2;
$b=$a**(1/2); #2^0.5
print $b; #1.4142135623731
[download]

The interesting thing is that in my shading, iterating over a row of pixels, the result is probably very close to the result of the previous pixel, since the whole point of this is "smooth shading", right? So I used the previous call as the initial guess, and most often got the right answer after one iteration.

—John