Efficient way to determine if a number is Perfect Square

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.

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.)

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.