mod a prime p it is easy. So try all primes \le n?

Thank you Patrick. Looks promising.

But "mod prime p" is almost equal to computing the actual square root, which we would like avoid. In fact, doing it over all primes

As far as I know, even theoretically this is not an easy problem. The only way to know if a number is a square is to check that the exponents of its prime decomposition (as in the Fundamental Theorem of Arithmetic) are even. The only practical "fast" way to compute the square root (of a float, though) is explained here:

http://blog.quenta.org/2012/09/0x5f3759df.html

Thank you Rachel. Our earlier attempts were on similar line - computing the square root and checking if it is integer or not.

However, it has this problem of "decide if any given number is integer or not" - which is equally complex problem and we could not find an accurate mathematical description of "how to verify if any given number is indeed integer or not" mathematically.

The programmatic tricks of "ceil(x) == floor(x), if x is integer" does not really fit. Because for an arbitrary precision math ceil and floor definitions are not really valid (or are there any really good mathematical definitions for ceil and floor for any precision?)

Thank you,

GK

http://gopalakrishna.palem.in/

The best way is check if 1 + 3 + 5 + 7 + ........+(2n-1) == m or not. If yes n is the sqrt.

@R. Mittal: Thank you - that's surprisingly simple - Will try it.

In that case, it looks like we are given "m" and we are trying to fit some "n" so that the formula 1+3+5+...(2n-1) ==m.

Are there any methods to quickly get some bounds on "n" for any given "m"?

Its really interesting: the way finding square root problem is converted to finding a series that fits a property of that squire root. Thanks much.

int m;

cin>>m;

int i=1, sum=0;

sum=i;

do

{ i +=2;

sum += i;

}while(sum

If you can do with log(n) multiplications, you could simply do a binary search on all numbers k less than, say, n/2, and check if k*k is exactly n.

There are 3 main solutions to this problem.

1. Simple to implement is binary search (as already mentioned). Given a pair of values (L,U) such that L^2 < n < U^2 (where n is the number to be tested), we compute ((L+U)/2)^2 and deduce that the solution is contained in an interval of half size. This is polynomial-time (unlike some of the other solutions already stated).

2. Optimal complexity is to use Newton interation. See Chapter 9 of the book by von zur Gathen and Gerhard. In particular, Section 9.5 talks of a 3-adic Newton iteration to compute integer square roots. This leads to a running time of O( M(n)) = O( \log(n) \log\log(n) \log\log\log(n)) the same as integer multiplication. But this is harder to implement.

3. A Monte-Carlo method is to reduce n modulo small primes p and compute the Legendre symbol (n/p) (which will always be 0 or 1 if n is an integer square). One would expect to test around log(n) primes to have good confidence that n is a square. I do not know a reference for a theoretical analysis of this algorithm.

@Steven Galbraith @Edgar Duenez-Guzman : Thanks for binary search model and pointers to the other models.

- GK (Gopalakrishna)

http://gk.palem.in/

I was thinking a little bit more about method 3 (testing Legendre symbols modulo small primes p). I guess the complexity is always worse than the Newton method. Recall that the Newton method has quasi-linear asymptotic complexity.

A naive implementation of method 3 would be expected to require at least log(N) trials (i.e., different choices for p), and each requires computing N (mod p), which requires at least log(N) time. So the method has at best quadratic complexity. (And this is ignoring the issue of finding suitable small primes p -- do we need primality testing?)

One can improve this using remainder trees, but I think the complexity would still be at least log(N) log(log(N))^2, which is worse than Newton's method.

A deterministic polynomial time algorithm presents in S.C. Coutinho The Mathematics of Ciphers. A. K. Peters Natick, Massachusetts. 1999. it is simpe to implement.

Input: integer n

output: integral part of the square root of n

1.X=:n, Y:=[(n+1)/2]

2. while X\ne Y

X:=Y

Y:=[(X^2+n)/2X]

3.return X

Thanks Frolov. Below is R version of your code (printing the loop counter also to verify its polynomial nature).

sq = function(n)

{

count

The algorithm in the reply by A. Frolov (from the book by S.C. Coutinho) is an integer version of Newton's method. The standard Newton iteration is to go from x to x - f(x)/f'(x). Taking f(x) = x^2 - n we get x - f(x)/f'(x) = (2x^2 - (x^2 - n))/(2x) = (x^2 + n)/(2x).

Thanks Steven Galbraith for simplest proof of algorithm from the S.C. Coutinho book!

There is a simple trick to do this:

It´s well known that

1+3+5+7...+(2k-1)=k^2

So if you consider the sequence S_k=1+3+5+7...+(2k-1), then you can check if S_k=n, if it is not then calculate S_(k+1) an check if it equals n. If S_k>n for some k then n is not a perfect square. (Realize that S_k is a monotonically increasing sequence).

The cost of this algorithm is O(n).

The algorithm proposed by Carlos Fernández (to compute the sum 1 + 3 + 5 + . . . + (2k-1)) requires exponential time. You need to go up to k = [sqrt(n)], so it takes O( sqrt{n} ) additions. This complexity is exponential as a function of log(n), so it is much worse than the other methods that have been discussed in this forum.

I didn't say it was the fastest way, I just said it was an easy way to do it.

I stated this method first where you have to check if next term k=k+2 is such that k*k == n. The moment k*k > n, n is not integer square. Of course its complexity is o(sqrt(n)).

You can build a Prime number greater than a specified number and take the Legendre symbol. There is no need to compute the square root.

Sorry, this is a wrong solution: Legendre symbol of 2 for 7 equals 1!

Now if you see 100 doors problem thread given by Joseph Issac, the solutions of the problem are perfect squares. Therefore can be used to check if the given number is a solution of the problem. If yes then the given number is a perfect square.

I don't see the problem with the algorithm by Carlos Fernández Sanz, only that he overestimated the complexity. It is O(sqrt{n}), which is better than O(n), because lim sqrt{n} over n = 0.

I suggest to apply Hasse principle: natural number N = n^2 then and only then when for every prime number p, (p,N) = 1, Legendre symbol (N,p) is equal to 1. So we try prime numbers one by one. If p|N, then write N = (p^k)*M, (M,p) = 1. If k is even then go on with M instead N. If k is odd, N is not full square. If Legendre symbol (N,p) is equal to -1, answer is no. If N = n^2, then it is sufficient to try all primes less or equal n. In negative case it is hard to estimate number of tested primes. I think it is not so big. In attached file we consider several examples.

First of all the last digit should not be 2,3,7,8.

Edit: my note is discussing fast filters, which should reject non-squares very quickly.  So only a fraction (75% to 0.08% depending on method) are left.  At some point to be sure you need to do the heavy lifting, typically by calculating the integer square root and seeing if its square is equal to the input.  But this is only done on numbers that are very likely to be a perfect square.  For native ints on most platforms, sqrt() is fairly cheap so we don't want to spend too much time filtering.  For large ints it is much more expensive so a good set of filters is important.  See mpn/perfsqr.c and mpn/sqrtrem.c from GMP 6.0 to see how they did it, for example.

Section 1.7.2 of Cohen's "A Course in Computational Algebraic Number Theory" discusses this, and he gives an algorithm using tables of residues modulo 64, 63, 65, and 11.  It's decent but there are ways that don't involve the tables.  John D. Cook's blog has a decent solution.  StackOverflow boffers a giant table solution that isn't fast for me, but others say it is.  I found using a simple bloom filter to be much faster than any of those.  See the functionspace link for code for that and other simple solutions, with benchmarks.

For code like SQUFOF or Hart's OLF the performance of this code is critical.  It's common to use in some primality tests though not in the critical path.

If you're using a large number package, see the mersenneforum link.  It not only gives working code, but it walks through the logic in detail.  Note that GMP's mpz_perfect_square_p works pretty well and is trivial to use though I have not compared performance vs. the bloom filter version.  It looks at a glance that GMP 6.0 uses a table mod 256 to start, followed by 91, 85, 9, and 97.  They indicate 99.62% rejection, vs. 99.92% for the full bloom filter set from merseneforum (but that requires one general modulo, where GMP has a lot of special internal code for their single mod so it could be faster).

http://functionspace.org/topic/3827/Fastest-way-to-check-if-a-number-is-a-perfect-square-or-not-

http://mersenneforum.org/showpost.php?p=110896

I agree with Srinath M. S. good answer.

Using A. Frolov's algorithm as written doesn't seem to work using integer math, as e.g. n=15 just loops alternating X,Y without them ever being equal.

Srinath's comment of reducing to first an odd number, then n-1 divisible by 8 is nice. The problem I see with trying to then check the triangular number predicate is that all the triangular predicate algorithms I've seen use the same relation, so we've circled back as it asks if some value is a perfect square.

You will definitely get better performance using a pre-test, whether it is something like Cohen's or Cook's modulos, or the more efficient Bloom filter(s). A trivial operation can knock out 82-96% of the inputs without having to calculate a square root. You can bump that up even more if desired, though at diminishing performance returns. Using the Jacobi symbols for small primes is a significantly more expensive way to do pretests, but of course also works.

We're still left with the issue of final decision (unless we're happy with a Monte Carlo solution, which seems dubious). The obvious and reasonably fast solution is just to get the integer square root at this point. That is what GMP's mpz_perfect_square_p does -- it does some modulo pretests then computes the square root+remainder

It seems many of the previous answers are integer square root algorithms. We'd be well served by reading Fredrik Johansson's post here: https://stackoverflow.com/questions/1623375/writing-your-own-square-root-function This will definitely converge and is entirely integer. For arbitrary precision, we might look at what GMP does: https://gmplib.org/manual/Square-Root-Algorithm.html (Karatsuba Square Root algorithm by Paul Zimmerman. His 1999 INRIA paper is interesting reading.

Dear Dana, thank you for your remark. Please, consider the following algorithm (in Python):

def intsqroot(n):

X=n

Y=(n+1)/2

while not X

Thanks! That does work, although one has to be careful of overflow with the X*X portion if working in a language like C that doesn't promote to bigints automatically. Pedantically for Python3, we need // instead of just / in both divides to keep things integer.

Thanks for reply! Now I prepared the proof of this algorithm improving Coutinho's proof. I need couple of days to be sure in its correctness. But you can use algorithm now. Algorithm and its proof will be given avoiding C++ or python notation.

Attached is a file with a proof of the corrected Coutinho,s algorithm, called the Discrete Tangent Newton Method

Only, a necessry condition. If an integer has square-root, then the last digit is either 0 (even number of zeros) or 1 or 9 ( and the tenth digit must be even) or 4 or 6 ( and the number consisting of the last two digits is divisible by 4) or 5 (and the tenth digit must be 2).