A small program that finds the perfect square root that is closest to but not over the root of the provided integer.

sqrt.c

#include <stdio.h>
#include <stdlib.h>

void main(int argc, char **argv) {
  unsigned int n;          // Input number
  unsigned int n2;         // Duplicate of input number to be worked with
  int s = 0;               // Shift counter
  unsigned int a = 0;      // Answer
  unsigned int c = 0;      // Carry number
  n = atoi(argv[1]);       // Read the first parameter provided and convert it to int
  n2 = n;

  /* Get the far left pair of bits and identify the index of that pair from the right */
  while ( n2 & ~3 ) {
    s += 2;
    n2 = n >> s;
  }

  do {
    c = a << 2;            // Carry becomes answer * 2 plus an extra digit
    a = a << 1;            // New answer is old answer with an extra digit
    if ((c | 1u) <= n2) {  // If Carry + 1 isn't greater than the remainder:
      a = a | 1u;          //   Add 1 to answer
      n2 -= c | 1u;        //   Subtract carry + 1 from remainder
    }
    n2 = n2 << 2;          // Shift remainder 2 digits
    s -= 2;                // Deincriment shift counter
    n2 += (n >> s) & 3;    // Add the next pair of digits to remainder for next round
  } while (~s & -2);       // Repeat until shift counter reaches 0, then one more time

  printf("%u\n", a);       // Print the result
}