Implement Square Root (Part II)

Problem:  Write a function which returns the square root of an integer.  Return an integer which is the floor of the integer closest to the value.  Implement an algorithm with efficiency better than O(sqrt(n))

int sqrtFlr(int x) {...}

In the last post, we implemented a solution to this problem, which was O(sqrt(n)).  While not a bad solution, this could get very slow as x becomes a very big number.  So, let's imagine how we could do better.

As a good guide, let's try an example.  Well, let's think of intuitively how we would find the square root of a big number, say 683,422.  (this really isn't that big for a computer, but, well, it's big for us).

In our algorithm, we would start with 1, and then increment, say 2 (which is squared to 4), then 3 (squared to 9)...  until we find the answer..

But, this isn't how we would intuitively do it.  

We would try a guess, say 1000.  Well, 1000 squared is 1,000,000.  Then, we try a smaller number, say 800.  800 squared is 640,000.  So, we now know that our answer is between 800 and 1000.  We could then try 900 squared, which is 810,000.  So, let's go down, to 850.  850^2 is 722,500.  Now, let's guess 820.  820^2= 672,400.  

We now know the number is between 820 and 850.  We're getting close.  

835^2= 697,225.  Let's now try 828^2= 685,584.  Now, we're very close.

827^2=683,929.  

So, if we go down 1,

826^2= 682,276.  And, well, this is the answer, 826, as we know 1 greater takes us to a larger number.

In this example, we tried 9 numbers to get the answer -- many, many fewer than 826, which our previous algorithm would have required.  And, note how this efficiency came.  We would jump forward and back in ever smaller increments, based upon whether our square was too high, or too low, continually adjusting the floor and ceiling, until the difference was 1.

This gives us a solution that looks like:

1.  Create a ceiling and floor, where the floor is 0 and the ceiling is x.

2.  Try the square of halfway between the ceiling and floor.

3.  Adjust the ceiling or floor based up on the result.

4.  Continue 2 and 3 and return the floor when the ceiling is one more than the floor.

And, what's the efficiency of this solution?  Well, as we reduce the range by 2 each time, this is a classic log solution, or O(log(n)).  

And, to give an idea of how fast O(log(n)) is, well, imagine a number like 2^256, which is more than the number of atoms in the universe.  log of 2^256 is 256, which is not so large!

We'll implement this in the next post!

/* Please send along any bugs or optimizations! */