The goal of this homework is to "discover" an algorithm for finding integer roots, such as `floor root(3) 81` and `floor root(15) 74498`.
Note: In mathematics, the notation `floor *` denotes the "rounding down" (or "floor") function that "throws away" the fractional part of a real number. For example, `floor 18.432 = 18`, `floor 18.69 = 18`, and `floor 0.9934 = 0`. Similarly, `ceil *` denotes the "rounding up" (or "ceiling") function, and `ceil 18.432 = 19`, `ceil 18.69 = 19`, and `ceil 0.9934 = 1`.
Consider the following guessing game: one player picks an integer value, call it secret_number, such that 0 ≤ secret_number < 1001; the other player tries to guess the secret_number and after each guess the first player only tells the second player whether secret_number < guess_number. This is the only question the first player is allowed to answer and therefore the only piece of information the second player receives after each guess. What strategy would you follow to try and guess the secret_number in as few guesses as possible?
There are many different strategies that could be chosen, some better than others; with many strategies you will be lucky sometimes and find the secret_number in very few guesses, but you will find that more often than not you will need quite a few guesses. There is, however, one particular strategy that is guaranteed to always lead to the correct answer in no more than 10 guesses. Can you guess how it works?
Basically the idea is to start with a low bound, lowEnough, and a high bound, tooHigh, on the possible secret_number. In this case, clearly lowEnough = 0 and tooHigh = 1001. The first guess is the number in the middle of the [lowEnough, tooHigh) interval, i.e., (lowEnough + tooHigh) / 2 or 500 in the example. There are two possibilities: (1) secret_number < 500 (the guess_number), then the secret_number must be in the interval [0, 500), in other words, we update the high bound so that tooHigh = 500; (2) it is not the case that secret_number < 500 and secret_number must be in the interval [500, 1001), and we update the low bound so that lowEnough = 500. Note that with one guess we have reduced the space of possible answers to half of the original range. Let's say that indeed our first guess was too low, so we know the secret_number must be in the interval [500, 1001). Let's do it all over again. The next guess is the number in the middle of the new [lowEnough, tooHigh) interval, [500, 1001), i.e., 750. Depending on whether secret_number < 750 or not, we update tooHigh or lowEnough, respectively, and continue in the same fashion. Before long we'll find the secret_number, guaranteed.
This algorithm is an example of an interval halving or binary search strategy. Its efficiency comes from the property that at each step we eliminate half of the interval of possible solutions. In the following homework questions you will discover how interval halving can be used to efficiently find integer roots.
Carefully consider and answer the following questions.