Fast algorithm for computing integer square roots on machines that doesn't support floating-point arithmetic? 
Fast algorithm for computing integer square roots on machines that doesn't support floating-point arithmetic?

I'm looking for a fast algorithm for computing the integer square root of an integer $N \ge 0$, i.e., the smallest integer $m \ge 0$, s.t., $m^2 \le N < (m+1)^2$.
The reason is that I'm operating on a virtual machine that doesn't support floating-point arithmetic (real-numbers), so algorithms like Newton's cannot be implemented, right?
The naive solution for finding the square root of $N$ is to check for $m=0,1,\ldots$ whether $m^2 \le N < (m+1)^2$. Is this the best algorithm?
 A: I think the easiest method will Babylonians sqrt method and it works well with machine supporting only integer division.
def babylonian(n):
x = n
y = 1
while(x > y):
    x = (x+y)//2
    y = n//x
return x

A: A fast way to calculate the integer square root is to use a digit-by-digit algorithm in base2:
$$\text{isqrt(n)} =  \begin{cases}
      n & \text{if $n < 2$} \\
      2\cdot\text{isqrt(n/4)} & \text{if $(2\cdot\text{isqrt(n/4)} + 1)^2 > n$} \\
      2\cdot\text{isqrt(n/4)+1} & \text{otherwise}
\end{cases}$$
Making sure to calculate $n/4$ using bitshifts, and doing the above iteratively. An example for 16-bit integers can be found on Wikipedia.
A: For $1 \leq N \leq 15,$ suggest table lookup. $1 \leq N \leq 3,$ output $1.$ For $4 \leq N \leq 8,$ output $2.$ For $9 \leq N \leq 15,$ output $3.$
Otherwise,
 as far as finding a good starting point, I suppose you can begin with $1,4,16,..., 4^k$ until $4^k \geq N > 4^{k-1}.$ Then let the starting point be $$  x_0 = 2^k  $$
Newton's method with integers and the floor function, but at the very end prevent loops: $$ x_{j+1} = \left\lfloor \frac{x_j^2 + N}{2 x_j} \right\rfloor  $$
As soon as $$ |x_{j+1} - x_j| < 5, $$
switch to your one-at-a-time idea between those endpoints. Otherwise, an infinite loop is possible.
When I programmed this, I let Newton go until consecutive terms were very close together ($<5$). Then I set $m$ to  the smaller one, and increased $m$ by one until the square exceeded $N.$ Then I decreased $m$ by one until the square is no larger than $N.$
