Talk:Calculate an integer square root

From CodeCodex

The Assembly version is pretty stupid - it doesn't say what kind of CPU it is assembly for, and it has nothing to do with the algorithm that the other versions are implementing. Do you not think that all the other languages cannot calculate an integer square root using a library square root function, followed by rounding it to an integer? How trivial is that? 24.205.91.162 16:17, 6 February 2007 (CST)

Good point on the assembly code. However, I don't think you fully understand what an Integer Square root actually is. You might read up on it at Wikipedia. The problem with your solution is that your code would calculate the integer square root of 35 as 6, when it is actually 5. At larger numbers, the error would be several integers away from the correct answer. -Nostromo 21:21, 6 February 2007 (CST)
As well as being slower, which is the whole point... martinwguy 04:18, 10 May 2008 (CDT)

Better basic algorithm[edit]

Hi! There is a better basic algorithm without all those multiplies.

unsigned int
sqrt(unsigned int x)
{
	register int op, res, one;

	op = x;
	res = 0;

	/* "one" starts at the highest power of four <= than the argument. */

	one = 1 << 30;	/* second-to-top bit set */
	while (one > op) one >>= 2;

	while (one != 0) {
		if (op >= res + one) {
			op = op - (res + one);
			res = res +  2 * one;
		}
		res >>= 1;
		one >>= 2;
	}
	return(res);
}

A smart compiler will spot that the (res + one) term is used three times, or some hand-twiddling may be necessary to clue dumb compilers in.

See [1] for implementations other languages.

Error in Java version[edit]

If isqrt() is called with the argument Integer.MAX_VALUE, then overflow will occur, as with the C version. A workaround is to calculate Integer.MAX_VALUE / 2 + 1 if n == Integer.MAX_VALUE, and (n + i/n) >> 1 otherwise. Here is my long version:

 static long sqrt(long n)
 {
   long x = 1;
   long x1;
   if (n == Long.MAX_VALUE) {
     x1 = Long.MAX_VALUE / 2 + 1;
   } else {
     x1 = (x + n / x) >> 1;
   }
   while (Math.abs(x1 - x) > 1) {
     x = x1;
     x1 = (x + n / x) >> 1;
   }
   while ((x1 * x1) > n) {
     x1 -= 1;
   }
   return x1;
 }

Colin <c.barker@orange.fr>

I replaced the code with a correct (and much, much faster) version that gives unsigned int outputs for all unsigned int and unsigned long inputs (extremely large long inputs will appear to give negative results if you treat them, as Java does, as signed ints). Olathe 19:46, 1 December 2010 (UTC)

Algorithm Improvement[edit]

The given algorithms can be improved by noting a few easy to prove math facts: define f(n,x) as the result of one integer Newton step, i.e. f(n,x) = [(x + [n/x])/2] where [a/b] denotes integer division. Then it is easy to show that

  • f(n,x) >= isqrt(n) for all positive integers n and x.
  • f(n,x) < x for any intger x satisfying x > isqrt(n)

So the Algorithm can be stated with a simpler stopping condition:

 Start with an x > isqrt(n)
 Perform x := f(n,x) until x no longer decreases.