A fast and simple method to compute a square root

The method is based on the well know fact that the difference between two consecutive squares is always two more than the distance between the previous two squares.

That is, for the sequence of numbers:

0 1 2 3 4 5 6 7

we have the squares of
0 1 4 9 16 25 36 49

The difference between each of these squares is: 1, 3, 5, 7, 9, 11, and 13 So it is very easy to figure out the root, with simply shifts, additions, and subtractions, with no multiplication or division.

So lets say we want the root of 64, all we do is add the sequency up until we hit 64, and the number of times we added, is the root.

Although this will work for numbers no matter how large they are, the amount of time adding in a loop until we get there can become overly cpu intensive. So what we do is shift the number until we only have one or two integer digits, use the above method to compute the root of that digit or two, then shift the number left by two, and the computed root by one, and repeat for the next digit.

Below is a perl script which does this. Notice that this can be used on a system with any base, and it only requires adding, subtracting, and shifting to get the answer. In the below example, you can enter any number for the base and it will still give the correct answer. To see how it works you can go to Example which is set for a base of 10:

#this square root algorithm is based on the fact that each square is found from 
#the previous square by a difference that increases by 2 each time
#ie. number :    0 1 2 3 4 5  6  7	(root below)
#    square:     0 1 4 9 16 25 36 49	(addon below)
#    difference:  1 3  5  7   9  11 13 (count below)
# we work on one pair of digits at a time, where the number we want the root of is between 1 and the base*base -1,
# ie. for a base 10 computation, 1 - 99, for binary 1 to 3
#after finding the root of that, we shift the number by 2 places, and the root by one, and computer again,
#until we have the precision we want

$start = 10000000;  #this is the number we want the square root of
$base = 10;	#when we divide by base it means shift right one digit, multiply by base left shift one digit, ETC, 
                #works equally well with decimal, hexadcimal, octal or binary bases

$basesquared = $base*$base;	#means two shifts left or right
$root2 = sqrt($start);
print "real square root = $root2\n";	#to easily verify the accuracy of the computation



$precision = 10;	#number of digits to the right of the decimal plus 1 integer digit

$addon = 1;	#amount the series of counts have added up to
$count = 1;	#series of 1,3,5,7,9,11
$root = 1;	#the series entry number
$decimal = $precision;

#shift right twice each time until there are one or two digits to left of decimal.
while ($start > $basesquared-1) {	#move decimal to where there are only 1 or 2 integer digits
  $start /= $basesquared;		#move decimal two points to the left
  $decimal++;
}

while ($decimal) {	#repeat until all signigicant digits are computed

while ($start >= $addon) {
  $root++;
  $count += 2;
  $addon += $count;
}

#it went over, so cancel out last iteration.  This can also be done by storing the values, then retriving them
$addon -= $count;
$root--;
$count -= 2;


#move everything by one or two places, orignal number by 2 places, root by one
$decimal--;	#move decimal point one place over
$addon *= $basesquared;	#square goes two places over (add 2 0's)
$start *= $basesquared;	#square goes two places over (add 2 0's)
$root *= $base;	#root goes one place over	(add 1 zero)
$count *= $base;	#count goes one place over (add 1 zero)
$count += $base-1;

}

$root /= $base**$precision;	#shift by the precision to put decimal back in correct place

print "computed root $root\n";

Marshall Dudley
mdudley@king-cart.com