Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 9 down vote favorite
1

Is there an efficient method to determine if a very large number (300 - 600 digits) is a perfect square without finding its square root. I tried finding the square root but I realized that even for perfect squares, it wasn't efficient (I used newton's approximation method and it was coded in JAVA). I read somewhere about using modular arithmetic but I'm not quite sure how to do that. Can anyone give me a hint on how to proceed?

Thanks in advance.

share|improve this question
1  
You can efficiently compute the Jacobi symbol of $n$ relative to $q$ for any $q$ that is relatively prime to $n$; if the result is $-1$, then you know that $n$ is not a square, but if the result is $1$ then the test is inconclusive. Is this the kind of thing you might have read? – Arturo Magidin May 25 '11 at 19:12
1  
You need to define "efficient" algorithm. Are you seeking to minimize the maximum time to determine if it is a square, or the expected time, or something else? There are some quick observations that could tell you it is not a square, e.g. if the last digit is 2,3,7 or 8 then it is not a square. Using such methods you can reduce the expected time but probably not the maximum time. – Philip Gibbs May 25 '11 at 21:30

6 Answers

up vote 4 down vote accepted

Faster than binary search is to use an integer version of Newton's method: for $\sqrt{A}$ and an initial guess $x_0$ of the right order of magnitude, let $x_{n+1} = \left \lfloor \frac{x_n^2 + A}{2 x_n} \right \rfloor$. I tried a 1200-digit number for $A$, with $x_0$ a 600-digit number, and $x_{10}$ was already correct. In Maple 15 on a not-very-fast computer, the CPU time was given as 0.

share|improve this answer
2  
Are you sure it's faster? At each step you need to perform one division. – Yuval Filmus May 25 '11 at 21:23
1  
Once you get two consecutive equal values, you must repeat from there. The recursion only looks back one step! – David Speyer May 25 '11 at 22:00
2  
@Yuval Filmus: Yes, but that's pretty fast for numbers of this size. Maple uses the GMP library. An integer division of a 1200-digit number by a 600-digit number might take about .0001 second. @obinna: I actually tested for 2 consecutive equal values. Note that $x_n = x_{n-1}$ iff $x_n^2 \le A < x_n^2 + 2x_n$. You actually run into an infinite loop with $x_n$ alternating between $\lfloor \sqrt{A} \rfloor$ and $\lceil \sqrt{A} \rceil$ if $A+1$ happens to be a square, so I should really have checked for that, but I didn't bother. – Robert Israel May 25 '11 at 22:05
1  
@Robert: It may be fast, but the binary search might be faster yet. Or maybe it isn't, I have no idea. – Yuval Filmus May 26 '11 at 0:44
2  
When I wrote this in GMP (a C/C++ library Gnu Multiple Precision) I found it safer to stop when, say, $$ | x_{n} - x_{n-1} | \leq 5 $$ and then adjust what you have by increments of $\pm 1.$. The problem is that is is quite possible to get a period 2 cycle repeating forever. – Will Jagy May 26 '11 at 2:00
show 3 more comments
up vote 5 down vote

I agree with Yuval Filmus that you should use binary search, but in case you're still curious about the approach using modular arithmetic: a number $a$ is a square $\bmod p$ for $p$ a prime not dividing $a$ if and only if the Jacobi symbol $\left( \frac{a}{p} \right)$ is equal to $1$. You can efficiently compute the Jacobi symbol using quadratic reciprocity, and if you get an answer of $1$ for $n$ primes, then $a$ is square with probability about $1 - \frac{1}{2^n}$.

(Alternately, $a$ is a square $\bmod p$ if and only if $a^{ \frac{p-1}{2} } \equiv 1 \bmod p$. I don't know how the efficiency of computing this compares to the efficiency of computing the Jacobi symbol.)

share|improve this answer
3  
+1. Also, searching for small prime factors is worthwhile -- a number divisible by 2 but not 4, 3 but not 9, etc., can't be a square. Further, some residue classes like 2 mod 3 are impossible. It's often worthwhile to check mod a precomputed number and use a lookup table to see if the number is a possible square mod that number. Continuing along this path leads to pseudosquares and the research of Sorenson and such. – Charles May 25 '11 at 19:28
up vote 4 down vote

The square root can be found using binary search. The resulting algorithm should run very fast on a 600 digit number, my guess is under a second.

You can implement the binary search without repeated squaring - each step you're only shifting and adding. That's why it's so fast. But even if you were squaring at each step, it would still be very quick and certainly feasible.

Any reasonable bignum package will contain a function computing the square root, so you don't even need to code the binary search yourself.

share|improve this answer
Try mpz_sqrt() if you use gmp. – Yuval Filmus May 25 '11 at 19:14
JAVA's Big Integer package has no square root function. What do you mean by the phrase "shifting and adding". I mean how can I determine whether the test case is greater than or less than the number without squaring it? – obinna May 25 '11 at 19:23
1  
@obinna: until you get within a factor of $2$ or so you can compare your guess with the actual number just by comparing the floors of their base-$2$ logarithms (particularly easy to do on a computer). "Shifting and adding" refers to the process for generating new guesses: see www2.lv.psu.edu/ojj/courses/cmpsc-201/numerical/bisection.html . – Qiaochu Yuan May 25 '11 at 19:32
@Qiaochu Yuan: If you have convenient access to the floor of the base-2 logarithm you can get within a factor of 2 directly with just shifts: 1 << (L >> 1). – Charles May 25 '11 at 19:45
3  
@obinna: I'm afraid your comment reveals that you haven't really thought about the problem. If your number $n$ is even, just count the number $b$ of trailing binary zeroes. If $b$ is odd, then $n$ is certainly not a square. If $b$ is even, then $n$ is a square if and only if the (odd!) number $n/(2^b)$ is. So you gain nothing from the knowledge that $n$ is odd, because the even case can trivially be reduced to the odd case. – TonyK May 25 '11 at 21:06
show 3 more comments
up vote 3 down vote

There is direct analogue of algorithm mentioned here http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation for arbitrary big integer. For binary representation it is only needed subtractions, comparisons and shifts. So, despite it finding integer part of square root precisely, I doubt it is possible to find something faster - the complexity level of the algorithm is comparable with integer division of two numbers. I suspect that Yuval Filmus also mentioned something similar in note about “shifting and adding” - here instead of that is shifting and subtracting.

share|improve this answer
"For binary representation" only mean internal representation of big integer on computer. Example of the algorithm in wikipedia need only small modification to work with arbitrary size integers. – Alex 'qubeat' May 26 '11 at 9:31
up vote 1 down vote

One of the ways to quickly eliminate several possibilities upfront is to use the test whether the sum of the digits of the given number adds up to either 1,4,7,9. The number not satisfying this can't be a perfect square. If it does, then you can carry on with one of the efficient methods discussed in the responses to check whether the number is perfect square.

share|improve this answer
Just to clarify, if $n^2 \equiv p (\mathrm{mod}\ q)$, $p$ is called a quadratic residue modulo $q$. What Atharva is referring to is the fact that the only residues modulo $9$ are $0, 1, 4, 7,$ and $9$. The reason this is useful is that for a number $k$, $k \equiv m (\textrm{mod}\ 9)$ where $m$ is the sum of the digits of $k$. So if $k$ is a perfect square, then $m$, repeatedly reduced modulo $9$, will be one of the five quadratic residues. If you do this process and it is not one of these five numbers, $k$ is not a perfect square. – Michael Albanese Sep 22 '12 at 4:05
The reason why you need to include $0$ as one of the possible residues is that your potential perfect square might be divisible by $9$. For example, $81$ is a perfect square and the sum of its digits modulo $9$ is 0. – Michael Albanese Sep 22 '12 at 4:07
Thanks Michael for suggesting the improvement to my answer in your comments. – Atharva Patel Sep 24 '12 at 10:00
up vote 0 down vote

This is my way of finding square roots larger than $100$. Take $1089$ for example. You first find the closest number (without going over) that has a square root divisible by $10$. That would be $900$; $30 \times 30$. The tens digit is a $3$. Next subtract that number leaving me with $189$. Now take the square root of $900$. Take the $10$s digit, multiply from $20$, and add $1$. That would be $61$. Subtract that number from $189; 128$. Now subtract $63, 65, 67$, etc until you reach $0$. Including $61$, count the amount of numbers that you subtracted that is the units digit. For this problem it would be $189-61-63-65=0$, so the units is $3$. Your final answer is $\sqrt{1089}=33$.

share|improve this answer
As noted by Ross Millikan in a comment to this duplicate answer, this is just the standard digit-by-digit square root algorithm. The OP wanted a way without computing the square root. – robjohn♦ Apr 23 at 23:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.