Daeblog

Sun, 19 Dec 2010

I'll just leave this code here - my solution to a problem posed earlier on today.

limitedsqrt.c
#include <stdio.h>

/*
 * Calculate the square root of a number with the following restrictions:
 * - only use integers
 * - no division, just multiplication and addition
 * - no function calls, just do it all in main
 */

#define TEST_RANGE_HIGH 1000

int main(int argc, char *argv[])
{
  int result;
  int n;
  int sqrtOfNumber;
  int offset;
  int previousOffset;

  for (n = 1; n < TEST_RANGE_HIGH; n++)
  {

    sqrtOfNumber = 1;
    
    for(;;) 
    {
      if (  (sqrtOfNumber * sqrtOfNumber <= n)
         && ((sqrtOfNumber+1) * (sqrtOfNumber+1) > n)
         ) 
      {
        break;
      }
      
      offset = 1;
      previousOffset = 1;
      
      while ((sqrtOfNumber + offset) * (sqrtOfNumber + offset) <= n)
      {
        previousOffset = offset;
        offset *= 2;
      }

      sqrtOfNumber += previousOffset;
    }

    printf("%d -> %d\n", n, sqrtOfNumber);

  }
  return 0;

}

I think this is a reasonable compromise between simple and efficient.