In this lab, you'll be taking the kth root of a NaturalNumber using the interval halving technique we taught in a homework and a lab. Hopefully, any questions you had were brought up and answered by the instructor or graders. If not, be sure to ask about this quickly so you have time to comprehend and code the solution with NaturalNumbers!
We've done this exact problem with ints, but now we've gone and made it all difficult for you by making you use NaturalNumbers. This is on purpose, obviously! NaturalNumbers are difficult to use, but they teach a few things in your struggles.
Firstly, they teach you how references work and make you remember that the variable's object value is copied when the parameter is passed, but instead that the reference (memory location) value is copied. This is something you'll deal with in most languages.
Second, its good practice for using a specific piece of software given to you for use. Though I don't have precise examples off the top of my head (can you really blame me? I've only had a summer of experience with a large company), this is something you may encounter on the job in the real world. It might be nice and easy to use ints, but the software your company has (aka OSU components) may be more powerful/used company wide. In this case, NaturalNumber doesn't have a limit for the number it stores, so we can do the root finding on numbers higher than ints can go.
Here is a solution for the integer root using interval halving. As stated in the homework and lab linked above, we use lowEnough and tooHigh to create our "guess domain", where the answer can still reside in between [1,n+1). Every time, we'll take a guess right in the middle with (tooHigh+lowEnough)/2. Then, we check if guess^r is larger than our original number, n. If its larger, that means (equivalently) that guess > rth root of n, so we know our guess is tooHigh. Otherwise, we know it was either too low, or equal to the answer, so we update lowEnough. We continue this until the difference tooHigh-lowEnough is 1, because that means there is only one element it can be - lowEnough! That is because our range is inclusive on the low end, and exclusive on the high end: [lowEnough, tooHigh). That's also why we name them like we do, because tooHigh is literally, too high, but lowEnough could be the answer.
/**
* 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) {
int lowEnough = 1;
int tooHigh = n+1;
while(tooHigh-lowEnough>1){
int guess = (tooHigh+lowEnough)/2
if(power(guess,r)>n){
tooHigh = guess;
}
else{
lowEnough = guess;
}
}
return lowEnough;
}
Now your job is to convert this into NaturalNumber instead of ints. You can use any methods except for the instance method for root (recall the difference between an instance method and a static method? An instance method has a distinguished formal parameter, and methods are called like n.methodName(param1, param2), whereas static methods are called without that first "n.", and instead are just methodName(param1, param2)). As a hint, you'll probably only need methods that correspond to operations you see in the solution above, like incrementing, subtraction, adding, dividing, comparing (compareTo), instantiating, and copying values.