Approximating Square Roots

sifukurt has asked for the wisdom of the Perl Monks concerning the following question:

I need some help. I'm trying to approximate the square roots of very large numbers. I wrote the code, but it isn't working right, so obviously I'm overlooking something. In brief, the method for approximating square roots works like this:

Guess at the square root
Divide the number you're trying to get the square root of by the number you just guessed.
Add the quotient to your original guess and divide by 2.
Treat this new number as your guess at the square root and go back to step #2.

Here's my original code:

use Math::BigFloat;

sub SqrRoot {
    my $num = Math::BigFloat->new( shift );
    my $iterations = shift || 50;
    my $guess = Math::BigFloat->new( $num / 2 );
    for ( 1..$iterations ) {
        $guess = (( $num / $guess ) + $guess ) / 2;
    }
    return $guess;
}
[download]

When I saw that this wasn't working, I broke the code down a little further to check the values during the whole process.

use Math::BigFloat;

sub SqrRoot {
    my $num        = Math::BigFloat->new( shift );
    my $iterations = shift || 50;
    my $guess      = Math::BigFloat->new( $num / 2 );
    my $temp       = Math::BigFloat->new();
    for ( 1..$iterations ) {
        $temp  = Math::BigFloat->new( $num / $guess );
        print ("$num / $guess = $temp\n");
        $temp += $guess;
        $guess = $temp / 2;
        print ("$guess\n----------\n");
    }
    return $guess;
}
[download]

In theory, this process should become more and more accurate, the more iterations it is run through. However, for reasons I don't know, the above code is dropping decimal places, and actually makes the result less accurate on each iteration. What am I missing?

Thanks in advance.
___________________
Kurt

Comment on Approximating Square Roots Select or Download Code

Replies are listed 'Best First'.
Re: Approximating Square Roots by suaveant (Parson) on Oct 05, 2001 at 21:26 UTC
I believe your problem is that though you are creating a bigfloat number, you are doing simple math operations in perl. You should probably be using Math::BigFloat's fdiv and the like for your math. I will point out that your code works for normal perl sized numbers... - Ant - Some of my best work - Fish Dinner	[reply]
Re: Re: Approximating Square Roots by sifukurt (Hermit) on Oct 05, 2001 at 21:36 UTC
There was an intermediate step where I was using bdiv() and badd() and the like. The results were the same. And with Math::BigFloat, once you've created a new() item, it isn't expressly necessary to use bdiv(), bpow(), etc. You can use standard math operators, which is what I chose to do in this most recent version simply for readability. It was easier (to me, at least) to follow the logic. ___________________ Kurt	[reply]
Re: Approximating Square Roots by Anonymous Monk on Nov 25, 2001 at 20:44 UTC
Sorry for the late answer, found your question by chance via Google. You probably stumbled over one of the many bugs in the old BigFloat package. There is a newer, much improved version on CPAN, and you should give it a try. It also has a bsqrt() function, that actually works ;) `use Math::BigFloat v1.22; $x = Math::BigFloat->new('1234.567'); print "square root of $x is ",$x->bsqrt(),"\n";` [download] HTH Tels If you have more questions, feel free to contact me at tels at bloodgate dot com. Thanxy!	[reply] [d/l]
Re: Approximating Square Roots by cLive ;-) (Prior) on Oct 06, 2001 at 00:44 UTC
I can't see off the top of my head, but maybe you'll find this node on the algorythm useful. cLive ;-)	[reply]


Come for the quick hacks, stay for the epiphanies.
	PerlMonks