mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-06-18, 20:31   #1
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default Identifing perfect squares and calculating square roots..

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 is offline   Reply With Quote
Old 2003-06-24, 20:18   #2
dsouza123
 
dsouza123's Avatar
 
Sep 2002

10100101102 Posts
Default

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;
dsouza123 is offline   Reply With Quote
Old 2003-07-19, 17:17   #3
Annunaki
 
Jul 2003

31 Posts
Default

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..
Annunaki is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Ring Square Roots in NFS paul0 Computer Science & Computational Number Theory 4 2015-01-09 14:57
Perfect squares in NFS paul0 Computer Science & Computational Number Theory 2 2015-01-02 14:21
Perfect square or not? jnml Puzzles 12 2012-04-28 21:33
Calculating perfect numbers in Pascal Elhueno Homework Help 5 2008-06-12 16:37
Perfect roots grandpascorpion Puzzles 4 2006-10-01 13:57

All times are UTC. The time now is 07:32.

Fri Feb 26 07:32:39 UTC 2021 up 85 days, 3:43, 0 users, load averages: 1.51, 1.48, 1.60

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.