What is a fast algorithm for finding the integer square root?

Question

What is a 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$ such that $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?

Answer 1

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

Answer 2

A fast ($O(\log n)$) 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.

Answer 3

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

This algorithm runs in approximately $O(\log n)$ time. More details can be found on StackOverflow.