Implement Square Root in log n time (part III) -- the trilogy ends!

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(log(n)).

The solution was:

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

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.

Now, let's implement this is code:

int sqrtFlr(int x) {
  
   int floor = 0;
   int ceiling = x;
   int halfway;
   
   while (floor != (ceiling - 1)) {
       halfway = floor + (ceiling - floor) / 2);
       if ((halfway * halfway) > x) {  // halfway is the ceiling!
           ceiling = halfway;
       } else if ((halfway * halfway < x)) {//halfway is the floor!
           floor = halfway;
         else {   //we have a perfect square
           return halfway;
       }

  return floor;
}


Let's try an example now, say 284.

When we start:
floor = 0
celing = 284.

we enter the while loop.
Now, halfway is 142.
142^2 is much bigger than 284, so we get:
floor = 0;
ceiling = 142

continuing through the while loop:
floor = 0;
ceiling = 142;
halfway = 71;
71^2 is still much bigger than 284, so we get:
floor = 0;
ceiling = 71;

staying in the while loop, we continue:
floor = 0;
ceiling = 71;
halfway = 35;  (35^2 is much bigger still)

staying in the while loop, we continue:
floor = 0;
ceiling = 35;
halfway = 17;  (17^2 is much bigger still)

staying in the while loop, we continue:
floor = 0;
ceiling = 17;
halfway = 8;  (8^2 = 64, which is smaller)

staying in the while loop, we continue:
floor = 8;
ceiling = 17;
halfway = 12;  (12^2 = 144, which is smaller)

staying in the while loop, we continue:
floor = 12;
ceiling = 17;
halfway = 14;  (14^2 = 196, which is smaller)

staying in the while loop, we continue:
floor = 14;
ceiling = 17;
halfway = 15;  (15^2 = 225, which is smaller)

staying in the while loop, we continue:
floor = 15;
ceiling = 17;
halfway = 16;  (16^2 = 256, which is smaller)  and we set floor to 16.

Now, when we go to the while loop, it fails and we fall out, and return 16.

16 is the correct answer here.

So, this solution seems to work.

Let's think of edge cases here.  Try a perfect square, say 16.  
floor = 0;
ceiling = 16;
halfway = 8;  (8^2 = 64, which is larger).  

Continuing through the for loop:  
floor = 0;
ceiling = 8;
halfway = 4;  (4^2 = 16, which is equal, trigger the else in the if statement, and returns true, so this works).  

Ok-- any edge cases.  Well, we could try 0 and 1, and this works.  How about negative numbers.  Well, let's return -1 in this case, and then we're done.

int sqrtFlr(int x) {
  
   int floor = 0;
   int ceiling = x;
   int halfway;
  
  if (x < 0) return -1;  //error case. 
  
   while (floor != (ceiling - 1)) {
       halfway = floor + (ceiling - floor) / 2);
       if ((halfway * halfway) > x) {  // halfway is the ceiling!
           ceiling = halfway;
       } else if ((halfway * halfway < x)) {//halfway is the floor!
           floor = halfway;
         else {   //we have a perfect square
           return halfway;
       }

  return floor;
}

And there is is.  An O(log n) solution to returning square root floor!

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

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! */

Implement Square Root (Part I)

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.

int sqrtFlr(int x) {...

Solution:

Let's start off by doing an example:

Let's enter 75.  The square root of 75 is between 8 and 9.  Therefore, we would return the floor, or 8.

Now, let's think of how we determined the answer was 8.  Effectively, we knew squares until we found one that was just below (64) and just above (81) of 75.  Then, we returned the lesser.  We could imagine turning this into a relatively straight forward implementation of the problem, where we would try every number, until we found one that was just greater, and the return one below.

If we thing of this as an algorithm:

  - Start at 1

  - Iterate through numbers, squaring each

  - Stop when you are greater than your number

  - Return one less than the number you squared.

Now, if we code this, we get:

int sqrtFlr(int x) {

   

    int i = 0;

 

    while((i * i) < x) {

        i++;

    }

   return i-1;

}

Now, let's try an example, 80.  We then start with i at 0, and end the while loop when i = 9.  And then, we correctly return 8.

Now, let's try some other cases.  Let's consider when x is itself a perfect square, say 36.  In this case we would stop the while lop when i = 6, as 36 is not less than 36.  So, this is a bug.  We would need to make the correct state i <= 6 to catch this case.

Also, let's imagine negative numbers.  As negative numbers require the imaginary number, i, we can just return -1 (or throw an error).  

Also, let's think of 0.  0 is in fact a perfect square, so this will work if we change the < than sign to <=.

Ok, making these changes we get:   

      

int sqrtFlr(int x) {

   

    int i = 0;

    if (x < 0) return -1; /* error case */

 

    while((i * i) <= x) {

        i++;

    }

   return i-1;

}

Let's consider the efficiency of this algorithm.  We go through every integer up to the square root ceiling (or one past for a perfect square), so this is an O(sqrt(n)) algorithm. 

This is efficient, by O(sqrt(n)) is still quite big if x is big.  Consider that the sqrt of a massive number, like 2^256, is 2^128.

We can do much better.  That's next week's problem.

/* Please send me any bugs or optimizations.*/

Sorting n elements into pairs (generic version of sorting socks)

Question:  Generalize sorting socks.  Assume that you have n objects where every object has potentially one or more pairs.  Sort the objects into pairs.

Answer:  This is a question where the assumptions really matter.  In the sock question, 

  - we struggled with the notion of order, e.g., given two socks, which one is greater?  

  - Also, we optimized by knowing that the human mind can compare more than two objects at once -- or at least pick out a like-object from a larger set quickly.  

  - We also assumed some element of memory, or that humans would remember, "The blue, striped sock was on the end."

So, let's assume that we have integers that we're trying to pair.  This is probably a reasonable assumption as a machine could assign some unique number to each element in our set.  Then, let's also assume that our comparison is confined to two elements at a time, and there is no memory.

In this case, the most obvious answer would be to sort the set.  This would yield an nlogn solution and we could then easily go through and would have our pairs set.

However, this actually does more than we need.  We would end up with a sorted set, which is not required.  Only paired elements must be together.

Ok, let's do better.

Imagine what we want to do.  We want to go through our set and put each element in a unique spot, then at the end, each 'spot' would consist of like pairs.

And, getting into spots must be a fast, or constant time operations, or else we're no faster than the sorting solution.

If you do an example, this quickly looks like putting each element into a hash table with n/2 hash buckets.  

Then, the total algorithm is clear:

  - Create a hash table with n/2 hash buckets.

  - Go through the list and hash into the hash table.

  - At the end, look at every hash bucket and sort if there are more than 2 elements.

  

Each hash table should be mostly unique and can quickly be ordered if not unique.

Well, this works.  

This is a good example of how machines often do things differently than the human brain, and potentially an example of where a machine might not be good, especially if comparison took a long time -- e.g., comparing two socks is a relatively complex operation if given two photos given orientation, folds, minor wear differences, yet it is something that humans can do intuitively.  But, that's another discussion!

/* Please send me any bugs or optimizations */

Question: How do you sort socks most efficiently from a pile?

Question:  How do you sort socks most efficiently from a pile?

Solution:  There are a bunch of assumptions here, so let's start listing them.  First, 
  - let's not assume that all pairs are distinct (e.g., you could have multiple pairs of the same socks).  
  - also, let's assume that there is no distinction between left foot/right foot for socks, (initially)   - that the number of socks pairs is a reasonable number of socks, (e.g., less than thirty),
  - the socks can quickly be compared for distinctness
  - you have sufficient table space for many piles

Let's start by thinking about how we do this in real life.  What I do when comparing socks, is I pick up one, and then go through the remaining socks to find the match.  In worst case, this requires:  (n-1) comparisons, then another (n-3) comparisons, then (n-5)...

Well, this is an O(n^2) algorithm.  So, this seems pretty slow.  But, when I do it, it certainly isn't this slow, as the algorithm has a few optimizations which aren't captured here.  

When I think of going through my socks, I somewhat remember my socks after the first pass through.  For example, I might remember that my blue sock was at the end, so I don't really have to look at all of the socks to figure out where this one goes.

Also, a comparison isn't really going through each sock one-by-one.  My vision/brain lets me look at many socks at once, say 10, and quickly find the match.  Some socks even stick out.  So, the problems is in reality, much faster than n^2, given these optimizations.

So, if I include these optimizations into the way that I sort socks, you could imagine that it's the same algorithm:
  - Prepare your sorting by moving the socks into subpiles of 10, with all socks visible
  - Pick up a sock, compare it until you find the match

With this optimization, the number of potential lookups is reduced by a factor of 10 (socks divided into 10s), and probably more given our memory of where socks are.  Given that we assume that we have fewer than 30 pairs of socks, finding a match is fewer than 6 look-ups, even not including memory.  If we include a 2x improvement with memory, this probably makes it under 3.  

This is almost constant time for each sock, and it goes down as we pair socks.  This is pretty darn good.

Now, let's imagine any other optimizations that might exist.  First, we could look to speed up the set-up process, by potentially spreading our socks out quickly and not being too rigorous on the number of socks in each pile.  

Or, we could consider moving socks into subpiles if they can easily be divided into distinct groups (e.g., blue vs. white) to reduce the lookup set.  

Perhaps we could get out of the problem all together, by doing something like using sock-clips when we wash our socks.

Also, some people have suggested 'sorting' the socks in order to solve this problem, but this is a challenging problem as socks have no clear, easily observable order (unlike numbers).  So, it's very hard to know if a red sock goes before blue, or after red.  And, even normal ways of comparing (e.g., some sort of color or length) gets difficult given real-world conditions like lots of white or dark blue socks of similar size, which makes the comparison operator complex and time-consuming.

In it's more generic form, the problem is something like, given n objects where each object in the set has a distinct pair, how can you most quickly sort the objects into pairs.  

We'll do this generic form next time.

<Please send bugs or optimizations!>

Thank you to Greg D. for suggesting this problem.

Triangular manhole cover -- can it fall in?

Question:  

Can a triangular manhole cover fall into a triangular shape pipe that it covers?  Assume that the triangle covers it perfectly (e.g., not bigger than the pipe)

Solution:

Well, this is an interesting problem.  We could imagine a triangular shaped pipe, and now we want to see if a triangle can fall into it. 

As an example, we can try the easiest case, which is an equilateral triangle (all sides the same) on the end of an equilateral pipe.  In this case, we can imagine putting a pin through the middle of the triangle and turning it.  

Well, it won't fall in here, and some basic math around edges being longer than the width of the triangle can convince of that.

But, that only proves that the simple solution does not work.

Now, let's try some other options, and some math.  

Each edge of an equilateral triangle is of length x, however the height of the triangle is (3^.5/2)*x which is less than x.  Therefore when oriented vertically with along one edge, it can be rotated so as to fall in.

This is also true of a regular pentagon, and hexagon for which you can also work out a proof.  I believe that it is true for any regular polygon -- and only circles do not exhibit this.  I haven't proved it but I think that it's true for any convex polygon (I'll leave that to the mathematicians)  But, this is a good reason to make manhole covers round!

Here is a general test:

Imagine that you place a stick through the middle of the lid.  Next pick it up and look at it from the edge so all you see is a line.  Now as you look at if from the edge, spin it on the stick through the central axis. If the projected line length changes over a rotation, it can fall in.

Thank you to Wayne L. for help with this problem!!