Quick method for approximate integer square roots

I'm looking for an algorithm that -- given a positive integer $n$ -- outputs a positive integer $\bar{n}$ with the following two properties:

1. $(\bar{n}+1)^2>n$;
2. $(\bar{n}-1)^2<n$;

So we have $\bar{n}=\lfloor\sqrt{n}\rfloor$ or $\bar{n}=\lceil\sqrt{n}\rceil$ for every $n$. The point is that I don't care which it is, and it needn't be consistently the same one. As long as properties (1) and (2) are always true, it doesn't matter.

I'd like to find a fast algorithm, especially if there exists one faster than simply doing Newton's Method a fixed number of times. As an example, here's an algorithm always satisfying (1), but unfortunately fails (2) [starting at $n=480$.]

1. Take the first half of the binary representation of $n$ (call it $m$).
2. Compute $\bar{n}=(m + n/m) / 2$. (that's integer division.)

Here's an example with $n=7$:

1. $n=111_2$, so $m=11_2=3$.
2. $\bar{n}=(3+7/3)/2=(3+2)/2=2$.
• I don't think your relaxation makes the problem any easier. If you had an oracle for your problem, you could compute general integer square roots by considering $4n$ instead of $n$, and then dividing the result by $2$. – Yuval Filmus Oct 30 '14 at 22:03
• I agree with Yuval's comment, but I'd like to add one important point which is worth considering: when it comes to numeric analysis, what constitutes a "fast algorithm" partly depends on what operations you allow. Almost every CPU these days have a priority encode instruction. On Intel 386, it's called "bit scan reverse", on ARM and MIPS it's called "count leading zeroes", and so on. This gives you a quick way to estimate the base-2 logarithm of a word. Since $\sqrt{n} = 2^{\frac{1}{2}\log_2{n}}$, this can give you a very accurate estimate with only a few instructions. – Pseudonym Oct 30 '14 at 22:51
• @YuvalFilmus, Pseudonym: Thanks for the comments. I think this pretty much shows: (1) there won't be an algorithm sufficiently better than finding the integer square root, and (2) there is already (on modern CPUs) a very efficient way to find that integer square root. – Steve D Oct 30 '14 at 23:16
• There is actually an extension to the "fast inverse square root" which is fast and yet less cumbersome than having to be processor-specific. Consider reading this post: h14s.p5r.org/2012/09/0x5f3759df.html – Francesco Gramano Nov 5 '14 at 20:29