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.
I believe a modified form of binary search is what will help you achieve that.
Let me elaborate that in c code.

`int square_number = findSquareRootFloor(GivenValue);`

```c
int findSquareRootFloor(int number)
{
    int low = 0;
    int high = number;
    int mid = 0;
    while (low <= high)
    {
        int mid = (high + low) / 2;
        int target = mid * mid;
        if (target > number)
            high = mid - 1;
        else if (target < number)
            low = mid +1;
        else
           // exact match
           return mid;
    }

    // if we have come here mid stores the floor of the square root
    return high;
}

```