Identifing perfect squares and calculating square roots..

[dsouza123]

Does anyone know any tests to determine
if a number is the square of an integer (whole number) or
that the square root of the number will be an integer
without having to do the square root ?

Or any tests to eliminate the number ?

I believe numbers with this property ( the square root is whole number )
are called perfect squares.

For example 49 is 7 squared but 51 doesn't have a integer square root.
The numbers to be used are hundreds or thousands of digits long
so they are too large to fit in the types readily available
in most programming languages.

The following tests can rule numbers out or identify them as possible squares.

Tests I am aware of are:
given an integer n
(n mod 4) in [0,1]
that is n divided by 4 has a remainder of either 0 or 1
is a necessary test to have a whole number square root
( so it is a possible perfect square ),
but if the remainder is 2 or 3 it can be ruled out.

The four mod tests:
(n mod 4) in [0,1]
(((n mod 9) + 8) mod 9) + 1 in [1,4,7,9] or rewritten 1 + ((n - 1) mod 9) in [1,4,7,9]
(n mod 5) in [0,1,4]
(n mod 7) in [0,1,2,4]


Another is using the last four digits of n
if it is in a list of 1044 numbers, it is a possible square,
if not, then n is ruled out.

The list is computed as follows:
Take the integers 0 to 9999,
for each number square it, mod by 10000, add to the list.

For example if n ends in 6241 ( in the list ) it is a possible square,
but if it is 5347 ( not in the list ) it can be ruled out.

Using the list can rule out almost 90 percent of the numbers and is
very quick using a lookup on a precomputed list.

Using the four mod tests can get another 9 percent at best but it is much slower.

That still leaves at least 1 percent that have to have a square root done.

That brings up a second question, an efficient way of doing square roots.
I have one (inefficient) that needs 6 multiplies, compares, conversions
per digit of the resulting square root.

If the number is 50 digits long the square root is 25 digits long,
so the 25 digit number (or its earlier 25 digit approximations)
have been squared and compared and converted 150 times.

About 16 digits can be done by converting the first 15 or 16 digits
of the number to a floating point number and using the square root
function but then the previous technique has to be used.

[dsouza123]

Haven't found any more tests
(to eliminate or confirm a perfect square)
but have found another (better) square root algorithm.

Found a description of the algorithm on a page using lisp/scheme.

Doesn't need conversions, the result is already stored
in the large integer type.

n is the number to do the square root on
ub is the upper bound
lb is the lower bound
av is the average
sr is the square root

ub = n + 1;
lb = 0;

done = false;
repeat
av = (ub + lb) div 2;
if av*av == n then
sr = av;
done = true;
end
else
if av*av < n then
lb = av;
else
ub = av;

if not done then
if ub == (lb + 1) then
sr = lb;
done = true;
end;
until done;

[Annunaki]

i don`t know if it helps but if every n^2 that isn`t divisible by 2 is divisible by 8 if you substract 1..
or somone probably would say the same like this:
(((2n+1)^2)-1)==0 mod 8

but i think you allready had better test with mod 4..