Figuring the Square Root

This week I was presented to a peculiar challenge: write a code that figures the square root of a real number N, without using any math libraries.

The solution that I thought is simple and elegant, and uses an algorithm/paradigm well known by computer scientists.

After trying to solve it by your own, click in the link below to see the solution.

Variation

If N was an integer, and we had for sure that it was a perfect square (an integer that has an integer square root), a naive algorithm would be to try all the possibilities between 1 and N:

int square_root(int n) {
    for(int i=1; i<=n; i++) {
        if(i*i == n)
            return i;
    }
    return 0;
}

Challenge

The challenge come up, therefore, when our N is a real number, and not necessarily has an integer square root. To test all the possibilities is impossible, because there are infinite real numbers between 1 and N, such as 1.01, 1.001, 1.0001, 1.00001, 1.000001, …, 1.000000000000000…0000000001, etc.

What to do, then? From where do I start?

Binary Search

For those who don’t know, binary search is a very elegant search algorithm. His most popular use is to search a number inside a sequence of numbers, given that this sequence is in someway ordered.
For more info: [link]

The binary search takes advantage of the fact that the sequence is ordered, and here is the connection to our problem.

Elaborating

If we can’t try the numbers in a naive way, we have to try the numbers in a smart way.

Let’s say that our N is 64 (to make it easy).

Let’s try. But instead of trying 1, 1.1, 1.01, let’s try something more plausible. What about N/2?

Weel, 32*32 is too high. Soon, 32 isn’t the square root of 64, and the best part is that no other number greater than 32 is the square root of 64 🙂

Let’s get down then. What about 32/2.

16*16 is alto too high, so no other number greater than or equal to 16 is the square root of 64. Notice that we have already eliminated infinite numbers (twice)!

Getting down a little more we come to our solution. 16/2 is equal to 8, and 8*8 is equal to 64.

Instead of infinite tries, we only needed 3.

Don’t be fooled, therefore. 64 is a perfect square, and purposively choosen because it’s easy. Some real numbers are not going to be so easy, and maybe even take thousands of tries until it’s found. Most of the algorithms stops after a defined number of tries, trading time by precision. The point here is that: thousands < infinite. Then, our algorithm is eficient.

Solution

Elaborating our algorithm, and following the model of the binary search, we have the following algorithm:

double square_root(double n) {
    double ini = 0, mid, end = n;
    
    for(int i=0; i<100; i++) { // we are going to do at most 100 tries.
         mid = (ini+end)/2.0;
         
         if(mid*mid == n) return mid;
         else if(mid*mid > n) end = mid;
         else ini = mid;
    }
    
    return mid;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.