Since there seems to be some confusion about this, here is the almost trivial pseudo-code to test for integer square roots in a language that has bigints, and integer division without remainder that I'll write div
(as /
might be confused with exact rational division):
boolean is_square(bigint n)
{ bigint a=n // or any value whose square is known to be at least n
; while a*a>n do a=div(a+div(n,a),2) od
; return a*a==n
}
No cycles are possible, no fuss (but negative numbers as input may cause it to loop forever, so that should be avoided). The outermost division is just a bit-shift, so it should be rather inexpensive. The clue to the correctness of this simple procedure it that, when the initial guess $a$ has $a^2>n$, then the exact value $b=\frac12(a+\frac na)\in\Bbb Q$ can be shown to also have $b^2>n$; if $\sqrt n$ is integer, then rounding down $b$ to an integer either gives exactly $\sqrt n$, or another too high estimate. If rounding down gives a too small value, then one can be sure that $\sqrt n$ is not integer. One also clearly has $b<a$, so the sequence (with rounding down at each step) is strictly decreasing and termination is assured.
For very large numbers the given code wastes a lot of time to get a ballpark-figure for the square root. This could be avoided by using a better initial guess for $a$, using for instance a logarithm, or basically anything that tells you the (approximate) number of bits in $n$ (there might well be a built-in function for that). But I think any pure integer arithmetic method to do this will suffer from the same problem.
As a numerical example, for a $999$-digit perfect square as input it took $1667$ iterations to find its square root. But just repeated halving would take about $\log_2(10^{499})\approx 1658$ iterations to get down to the proper order of magnitude, so that is what the algorithm is essentially doing most of the time. If instead of $n\approx10^{998}$ one takes an initial guess of $10^{500}$ (still about $10$ times larger than the square root) it takes only $13$ iterations to find the square root. The last iteration step hits the square root on the head from a distance of more than $10^{142}$ (that is, the error of the approximation goes from that gigantic number directly to $0$, which is a witness of how much Newton's method improves the approximation here).
By contrast, a binary search procedure even with a fairly good initial guess like $10^{500}$ would need as number of iterations at least $1658$, namely the number binary digits of the square root (since it adds one binary digit precision each iteration). For the record, the input used in the experiment was the square of $10^{499}+345674632452435$ (you can guess the type of "random generation" procedure I used for it).