Lab: Integer Root With Interval Halving

Objective

In this lab you will implement an algorithm to compute integer roots using the fast interval halving (a.k.a. binary search) strategy developed in the homework.

Setup

Follow these steps to set up a project for this lab.

1. Create a new Eclipse project by copying ProjectTemplate. Name the new project IntegerRoot.
2. Open the src folder of this project and then open (default package). As a starting point you can use any of the Java files. Rename it IntegerRoot and delete the other files from the project.
3. Follow the link to IntegerRoot.java, select all the code on that page (click and hold the left mouse button at the start of the program and drag the mouse to the end of the program) and copy it to the clipboard (right-click the mouse on the selection and choose Copy from the contextual pop-up menu), then come back to this page and continue with these instructions.
4. Finally in Eclipse, open the IntegerRoot.java file; select all the code in the editor, right-click on it and select Paste from the contextual pop-up menu to replace the existing code with the code you copied in the previous step. Save your file.

Method

1. Complete the body of the root method using the interval halving algorithm you developed for the homework and the power method provided with the lab. (Note that the objective here is to use the fast interval halving strategy, so no other approach is acceptable.)
2. Run the program and modify your implementation of root until it passes all the test cases. If you are having trouble debugging your code, you should first systematically trace over your code on the specific input(s) where it fails. After that, if you still cannot find the bug(s), you may consider using the Eclipse debugger to help you figure out where things go wrong.

Additional Activities

1. The implementation of the power method provided with this lab is not very efficient. It is easy to see that to compute power(n, p)for some integer p > 0, the method has to perform p – 1 multiplications. Can you improve on this and come up with an implementation of power that requires significantly fewer multiplications?

2. Note the requires clause for the power method, specifically the following assertion:

   Integer.MIN_VALUE <= n ^ (p) <= Integer.MAX_VALUE
   

   1. What happens if the client violates this precondition?
   2. Is it possible that a legal call to the root method will violate the requires clause for the power method?
   3. How could the client check the precondition of power?