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.
- Create a new Eclipse project by copying ProjectTemplate.
Name the new project IntegerRoot.
- 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.
- 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.
- 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
- 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.)
- 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
- 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?
- Note the requires clause for the power
method, specifically the following assertion:
- What happens if the client violates this precondition?
- Is it possible that a legal call to the root
method will violate the requires clause for the power
method?
- How could the client check the precondition of power?