As an exercise, I converted an old method I learned for calculating square roots on a rotary decimal hand calculator to binary.
I'm sure this is not original; can anyone provide a reference?
// All arithmetic is truncating unsigned integer arithmetic
// Actual implementation uses bit shifts
// Indention level defines statement scope
def sqrt(r) // r is an unsigned integer
residue = r // residue will be the 'remainder'
root = 0 // root will be the integer square root (floor(r**0.5))
onebit = 2**(bitlength(r)-2) // onebit is a moving 'bitpicker'
while onebit > r
onebit = onebit / 4 // find highest bitpicker less than r
while onebit > 0
x = root + onebit // Current root plus onebit
if residue >= x // Room to subtract?
residue = residue - x // Yes - deduct from residue
root = x + onebit // and step root
root = root / 2 // Slide evolving root 1 bit down the residue
onebit = onebit / 4 // Slide the bitpick 1 bit down the root
assert(root**2 + residue == r)
assert((root+1)**2 > r)
return root, residue
