2
$\begingroup$

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$.
$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Oct 30 '14 at 22:03
  • 4
    $\begingroup$ 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. $\endgroup$ – Pseudonym Oct 30 '14 at 22:51
  • 1
    $\begingroup$ @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. $\endgroup$ – Steve D Oct 30 '14 at 23:16
  • $\begingroup$ 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 $\endgroup$ – Francesco Gramano Nov 5 '14 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.