Question: Recently, I came across a problem in someone's programming class. It asked them to compute a square root using only integers; they were to use one integer to represent the part before the decimal point and another integer to represent the part after the decimal point. The problem said that using floating point numbers was not allowed.

However, after thinking about it for some time, I can't seem to come up with a way of doing it without using floating point. I've Googled high and low and I can't seem to find an answer.

I jokingly suggested that my friend implement an FPU to do this, but he wasn't so amused.

Does anyone have any ideas about how to go about solving this?

Answer: 
Let's say your original number is `x`.

1. Finding part before decimal point is easy - just find the maximal number, which square is less or equal to the original number.
2. Multiply original number by 100 and the integer part of sqrt by 10. Add 1 to it until it's less or equal to `100x`. Do it `n` times and divide by `10^n` at the end to get the final answer truncated to `n` decimal places.
In pseudo-code it would be something like this:

```
int whole_ans = sqrt(num); //stores final answer integer part
int dec_ans; //stores final answer decimal part

int num_of_decimals = x   //x is equal to the number of decimal places you want the answer to be
int targetNum = (num - (whole_ans^2)) * 100;  //initialize target to residual * 100
int currAns = whole_ans; //initialize target to residual of num - the answer so far

for(int i=0;i<x;i++)
{
    x = get_next_digit(targetNum,currAns));
    dec_ans = append(dec_ans, x);  //append the new found digit to the right of the current decimal answer
    targetNum = (targetNum - (currAns * 20 + x) * x) * 100; //update target number to be residual + 2 zero digits
    currAns = append(currAns,dec_ans) //append the decimal part of the answer to the current total answer so far

}

func get_next_digit(targetNum,currAns)
{
int attempt=0;
int i=0;
   while(attempt <= targetNum)
   {
       i++;
       attempt = (20 * currAns + i) * i;
   }
i--;
return i;
}

```

This answer follows the steps on calculating a square root by hand: <http://www.wikihow.com/Calculate-a-Square-Root-by-Hand>