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.
Suppose you want to compute the square root of 123.4567.

Then all you have to do is shift the decimal point far enough to the right to get an integer radicand -- in this example, four places -- and so, the following is true:

`sqrt(123.4567) = (1/100) * sqrt(1234567)`

That is, all you need to know is how to find the square root of an integer. For this, consider the following code (in C):

```
unsigned int int_sqrt (unsigned int n) {

    unsigned int result = 0;
    unsigned int count  = 1;

    for (; count*count <= n; count += 1) {

        result = result + 1;

    }

    return result;

}

```

If you want to do away with the multiplication, you can also do this:

```
unsigned int int_sqrt (unsigned int n) {

    unsigned int result = 0;
    unsigned int odd    = 1;
    unsigned int oddsum = 1;

    while (oddsum <= n) {

        result = result + 1;
        odd = odd + 2;
        oddsum = oddsum + odd;

    }

    return result;

}

```

These are clearly not the fastest ways to do it -- but they use integers only, and they do not rely on characteristics of particular CPUs such as word length.