How to

When solving these problems, learning by doing is much better than learning by reading. I encourage to you read only as far in the solution as you need, then trying to solve the problem. If you get stuck, try reading a little further. And of course, let me know if you find a better solution!

Friday, February 28, 2014

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





19 comments:

  1. Nice! In computer science, we'd say this problem can be "reduced" to a Binary Search problem. Meaning, they're equivalent.

    ReplyDelete
  2. Nice, but doesn't work for x = 1, does it? It'll never enter the loop (because the floor is initially already one less than the ceiling), hence returning the initial floor, i.e. 0 ... so do we just make 1 a special case too?

    ReplyDelete
    Replies
    1. Nice catch Amir! I just noticed that very same flaw in my own solution

      Delete
  3. I noticed that if x is larger than 100,000, then there is an overflow issue, so I am thinking is there a way to lower down that upperbound first....

    ReplyDelete
  4. Watch your favourtie pinoy channel replays and all the pinoy flix tv tambyan replays online in hd.

    ReplyDelete
  5. Get your favourite Filipino tv shows online and all Teleserye Pinoy Channel Tv Get videos and download all Pinoy tv

    ReplyDelete
  6. Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work! Please visit webstagram

    ReplyDelete
  7. Bagi para penggemar yang ingin bermain Slot Online Deposit Pulsa Tanpa Potongan yang bisa dimainkan dengan sangat mudah dan dimanapun kapanpun kalian inginkan bisa langsung mengunjungi situs IDN89 yang sudah terpercaya melalui https://188.166.252.208/

    ReplyDelete
  8. Pinoy Channele bringing you best videos from all over Filipino entertainment, sports,
    news, politics, technology, music, covering all Latest Tv Replay Show of Pinoy Teleserye.

    Marry Me, Marry You

    ReplyDelete
  9. Dance + Season 6: Latest & Full Episodes of Dance + online on Disney+ Hotstar.
    Binge watch episodes of Dance + entire season 6 only on Disney+ Hotstar.

    Molkki

    ReplyDelete
  10. Today's episode starts with Kanta getting emotional. Anuj asks Kanta
    what happened. Devika asks Kanta if she said anything wrong. Anupama asks

    Anupama Online

    ReplyDelete
  11. Vivian D'Sena, who was last seen on the show Shakti - Astitva Ke Ehsaas Ki,
    is making a comeback to television with romantic drama Sirf Tum Hindi Serial.


    Sirf Tum

    ReplyDelete
  12. Watch and download Korean drama, movies, Kshow and other Asian
    dramas with english subtitles online free. Dramacool for everyone!

    DramaCool

    ReplyDelete
  13. Udaariyaan Serial is 2021 latest tv show of colors is the story of two sisters Jasmine and Tejo from a small pind in Punjab, and the dashing village boy Fateh.
    Anupama

    ReplyDelete
  14. I got to learn a few excellent stuff here. Certainly reading bookmarking
    for revisiting. I wonder how much efforts
    you place here to create this such magnificent informative content site.
    Naagin 6 Online

    ReplyDelete
  15. KissAsian is the best website to Korean dramas and movies online free with
    English Subtitles and Dubbed. This website Chris Gayle, movies of genres ...


    KissAsian


    [url=https://kissasian4u.com/]KissAsian[/url]

    ReplyDelete
  16. Kepala Bergetar Tonton Malasian Dramas dan Download Live Malay Telefilem, Dfm2u Malay Dramas. MyFlm4u Terkini Gempak Episode

    ReplyDelete