Homework: Interval Halving


Objective

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`.

A Fast Algorithm for Searching

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.

The Questions

Carefully consider and answer the following questions.

  1. Suppose someone claims that `floor root(3)(82) = 4`. How would you verify whether `floor root(3)(82) = 4` using powers of 4 and powers of 5? Is `floor root(3)(82) = 4`?
  2. Suppose that n, r, and root denote integer values where n ≥ 0 and r > 0. Further, suppose that `(mit"root")^r <= n < (mit"root"+1)^r`. Can we conclude that `mit"root" = floor root(r)(n)`? Carefully justify your answer.
  3. Suppose that n and r denote integer values where n ≥ 0 and r > 0. Further, suppose you would like to know `floor root(r)(n)`. When finding `floor root(r)(n)` by a guess and verify method, is there any reason to try a guess, say g, where g < 0? Explain your answer. Similarly, is there any reason to try a guess g where g > n? Explain.
  4. Again, suppose that n and r denote integer values where n ≥ 0 and r > 0. What are two "simple" values, say lowEnough and tooHigh, such that lowEnough ≤ `floor root(r)(n)` < tooHigh. Explain based on your answer to the previous question.
  5. Suppose you would like to know `floor root(5)(47226)`. Explain how you could find `floor root(5)(47226)` using a guess and verify method. Note: Explain your answer by relating this problem to the number guessing game described earlier. Think about what would be an appropriate question to use in place of "Is secret_number < guess_number?" and think about good choices for the starting values of lowEnough and tooHigh.
  6. Assume you are given the power method specified as follows:
    Use your answers to the previous questions to implement the root method specified below. Be sure to use the idea of interval halving.

Additional Questions

  1. In the number guessing game, how many guesses at most will be needed to guess a secret number in the interval [0, n) where n > 0 when using the interval halving strategy discussed above?
  2. Explain how you answered the previous question.