IN JAVA.

Objective

The goal of this homework is to "discover" an algorithm for finding integer roots, such as 381813 and 15744987449815.

Note: In mathematics, the notation denotes the "rounding down" (or "floor") function that "throws away" the fractional part of a real number. For example, 18.432=1818.432=18, 18.69=1818.69=18, and 0.9934=00.9934=0. Similarly, denotes the "rounding up" (or "ceiling") function, and 18.432=1918.432=19, 18.69=1918.69=19, and 0.9934=10.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 382=4823=4. How would you verify whether 382=4823=4 using powers of 4 and powers of 5? Is 382=4823=4?
2. Suppose that n, r, and root denote integer values where n 0 and r > 0. Further, suppose that (root)rn<(root+1)r(root)rn<(root+1)r. Can we conclude that root=rnroot=nr? 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 rnnr. When finding rnnr 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 rnnr < tooHigh. Explain based on your answer to the previous question.
5. Suppose you would like to know 547226472265. Explain how you could find 547226472265 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:

   /**

   * Returns {@code n} to the power {@code p}.

   *

   * @param n

   * the number to which we want to apply the power

   * @param p

   * the power

   * @return the number to the power

   * @requires Integer.MIN_VALUE <= n ^ (p) <= Integer.MAX_VALUE and p >= 0

   * @ensures power = n ^ (p)

   */

   private static int power(int n, int p) {...}

   Use your answers to the previous questions to implement the root method specified below. Be sure to use the idea of interval halving.

   /**

   * Returns the {@code r}-th root of {@code n}.

   *

   * @param n

   * the number to which we want to apply the root

   * @param r

   * the root

   * @return the root of the number

   * @requires n >= 0 and r > 0

   * @ensures root ^ (r) <= n < (root + 1) ^ (r)

   */

   private static int root(int n, int r) {...}

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.