Technique for finding integer square roots for arbitrarily large integers in Perl

From Ajswiki

This article has been updated and re-posted as a blog entry on Aaron's Essays.

If you want to find integer square roots of arbitrary integers you can use this Perl code (or adapt it to your language of choice). I devised this, while working on the 2^2x+1 problem. So why is finding an integer square root interesting? Well other than the problem I was working on, you might be trying to find prime factors, and the highest number you have to test for a prime factor of a larger number <math>x</math> is <math>floor(\sqrt{x})</math> which just happens to be what this function will calculate.

The Babylonian method

The Babylonian method is used here. It's simply the process of iterating through this formula:

<math>x_{n+1} = \frac{x_{n} + S/x_{n}}{2}</math>

Where <math>S</math> is the number you want the square root of. The only question is: what do you start with for a value of <math>x_{0}</math>? The answer is any integer, but the closer you start to the actual square root, the faster this will work. In my example, I use 3 raised to the power of the number of digits in the integer you're trying to find the square root of. That works fairly well, but if your problem lends itself to a better initial approximation, you should use it.

The Perl code

use Math::BigInt;
our $two = Math::BigInt->new(2);
our $three = Math::BigInt->new(3);
sub integer_square_root {
       my $S = shift;
       $S = new Math::BigInt $S unless ref($S) eq "Math::BigInt";
       my $x = $three ** length($S);
       my $lastx=undef;
       for(;;) {
               $x = ($x + ($S/$x))/$two;
               last if defined $lastx && $x == $lastx;
               $lastx = $x;
       }
       return $x;
}

Simply call this like so:

my $sq_root_x = integer_square_root($x);

You can pass in any number or a Math::BigInt object. If you pass in a floating point value, it will be truncated before finding the square root. Passing in a negative number will result in an infinite loop, so you might want to guard against that.

Why not use Math::BigFloat

Perl provides a square root function in Math::BigFloat, so why not use it? Math::BigInt is arbitrary precision. You can use it to represent any integer that your computer has memory for. But, Math::BigFloat has a precision that you must choose before using it, or you get a default, and that can cause all sorts of problems, even if your number is just very large, and doesn't need lots of precision after the decimal point. It's always best to just avoid floating point numbers whenever you can, unless you're willing to take on the extra overhead of managing precision.