Answer 2—This function also computes the integer square root of its argument, using a completely different technique. However, it still has the advantage of requiring only addition and shifting operations. Multiplication and division aren’t required. Rewritten with better variable names, it looks like the following:  

uint32 sqrt (uint32 n)
{
	uint32 root = 0, bit, trial;
	bit = (n >= 0x10000) ? 1<<30 : 1<<14;
	do {
  	trial = root + bit;
	if (n >= trial) {
    	n -= trial;
	root = trial + bit;
    }
	root >>= 1;
	bit >>= 2;
	} while (bit);
	return root;
}

The technique used here is the binary version of the long-division method of computing square roots you may have learned in school.

You start by finding the largest power of 2 squared that’s less than the given number. Then you must try to increase the trial root 1 bit at a time. Mathematically, as each iteration begins, you have a partial answer of the form: 

trial + bit 

and a remainder of the form: 

n – trial² 

If the next bit is going to be a 1, you subtract the quantity: 

(2 × trial + bit) × bit 

from the current remainder, which makes the new remainder: 

n – (trial² + 2 × trial × bit + bit²) 

This is equivalent to: 

n – (trial + bit)² 

which is exactly what it needs to be for the next iteration.

Contributor: David Tweed