Problem

Find the square root of a given number rounded down to the nearest integer, without using the sqrt function. For example, squareRoot of 9 should return 3, and squareRoot of 17 should return 4.

Solution

Let us consider what it means for a number x to be the square root of a number s. If x is the square root of s, x^2 is equal to s. Therefore, stated differently, the problem is to, given a number s, find a number x so that x is the biggest number for whichx^2 is either equal or smaller than s.

We may consider this to be a search problem. We have a number s, and we have to find a number 0 <= x <= s that satisfies certain conditions. Since the search space is the number line, which is already sorted, binary search is well-suited. We start our search with the full search space, with a number low := 0, and a number high := s. We then guess x to be in the middle of high and low, at (high + low) / 2. If x^2 is larger than s we narrow our search space by setting high to a lower value. If x^2 is smaller than s we do the same by setting low to a higher value. This is just like a normal binary search, except that instead of an array of integers, we are searching all integers between 0 and s.

The fact that we are only required to find an integer square root means that we do not need floating point calculations, which boosts efficiency. However, because the problem statement requires the square root be rounded down, we need to check two conditions:

• that the square of the x we have found is either smaller or equal to v, and
• that the square of x+1 is larger than v.

When these two conditions are met, we have found the square root of v, rounded down to the nearest integer.

Solution

Here is an implementation of the algorithm, written in Go:

func SquareRoot(v int) (i int, err error) {
    // use Newton's method to narrow in on the nearest
    // integer x where x*x is closest to v.
    var low, high int = 0, v

    // we have special cases for 0 and 1
    if v == 0 || v == 1 {
        return v, nil
    }

    // if v is negative, return an error
    if v < 0 {
        return 0, errors.New("Cannot find the square root of a negative number")
    }

    // choose x to be in the middle of high and low
    x := (high + low) / 2
    xs := x * x // x squared

    // keep looping while x squared is not the nearest rounded
    // down integer of any squared integer
    for !(xs <= v && (x+1)*(x+1) > v) {
        if xs > v {
            // if x squared is bigger than v, set the value of high
            // to the middle of high and low, which is where x is now
            high = x
        } else if xs < v {
            // if x squared is smaller than v, set the value of low to x
            low = x
        }
        // set x to the middle of high and low
        x = (high + low) / 2
        // calculate and store x squared to save some cycles
        xs = x * x
    }

    return x, nil
}

Follow-up question

How would you adapt your integer square root algorithm from the problem above to return the floating point square root of a given number, instead of an integer?