2003-06-18, 20:31 | #1 |
Sep 2002
1226_{8} Posts |
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. |
2003-06-24, 20:18 | #2 |
Sep 2002
2·331 Posts |
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; |
2003-07-19, 17:17 | #3 |
Jul 2003
31 Posts |
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.. |
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 |