Fastest square root method with exact integer result?
You do not need an exact method, anything with error less than 1 is OK. Say you want to compute $\lfloor \sqrt{x} \rfloor$. This is the largest integer $y$ such that $y^2 \leq x$. Say you have an algorithm $\mathcal{A}$ which on input $x$ outputs $z = \mathcal{A}(x)$  such that $|z - \sqrt{x}| &lt; 1$. You can just:


Compute $z = \mathcal{A}(x)$
Let $z_0 = \lfloor z \rfloor$
Let $S = \{z_0 - 1, z_0, z_0 + 1\}$
Output  $y = \max\{y \in S: y^2 \leq x\}$ (in words: output the largest integer among $z_0 - 1$, $z_0$, $z_0 + 1$ whose square is at most $x$).


You can also verify you have the correct number by checking that $(y+1)^2 &gt; x$. 

Correctness follows from the fact that if $|z - \sqrt{x}| &lt; 1$, then $|\lfloor z \rfloor - \lfloor \sqrt{x} \rfloor| \leq 1$. 

I think Newton's method with a small number of iterations is the best thing you can do. Since you only need error smaller than 1, I believe a few iterations will indeed suffice. Doing extra three integer multiplications and comparisons at the end cannot slow you down so much.