Answer 1—The function computes the integer square root of its argument, using a bitwise successive-approximation technique. The big advantage to this technique is that it requires only addition, shifting and logical or operations, and no multiplication or division. Rewritten with better variable names, it looks like the following:

uint16 SquareRoot (uint16 Number)
{
uint16 Root;
uint16 RootSquared;
uint16 Mask;
uint16 MaskSquared;
uint16 Test;
uint16 Power;
	
Root = 0;
RootSquared = 0;
Mask = 1 << (Precision - 1 );
MaskSquared = 1L << ( ( Precision - 1 ) << 1 );

for (Power = Precision; Power > 0; --Power) {
    Test = RootSquared + MaskSquared + ((uint16)Root << Power);
     if (Test <= Number) {
          RootSquared = Test;
          Root |= Mask;
    	}
    	Mask >>= 1;
    	MaskSquared >>= 2;
  	}

  	return Root;
}

Mathematically, it takes an initial guess, Root, and attempts to add an incremental value, Mask, to it. In order to see whether or not this new guess will exceed the given number, it’s necessary to square it. In symbolic terms, you need the result: 

(Root + Mask)² 

Multiplying this out, you get: 

Root² + Mask² + 2 × Root × Mask  

Note that the relationship between Mask and Power is initialized to: 

Mask = 2^{Power  – 1} 

which is maintained as the loop executes. Therefore, 

2 × Mask = 2^Power 

You can substitute this directly into the squaring operation: 

Root² + Mask² + Root × 2^Power 

which is exactly what the "Test = ..." line in the code implements.

Contributor: David Tweed