The Heron Method for approximating the square root of a number states that if x is a guess for the square root of n then a better guess x' is:
x' = [x + (n/x)] / 2
Naturally this process can be repeated using x' in place of x the next time through the loop. The loop can stop when the difference between the previous and next guesses is small enough.
A programmer wrote the following code to implement the Heron Method to locate the square root of any number:
function heronSqrt(n)
{
var DELTA = 1.0E-10;
var nextGuess;
var prevGuess = n;
do
{
nextGuess = (prevGuess + (n/prevGuess))/2.0;
prevGuess = nextGuess;
} while (nextGuess-prevGuess > DELTA)
return nextGuess;
}
However, the code does not work properly. Fix the program so that it works. Also list a set of test cases that will thoroughly exercise the Heron Method List a set of test cases that will thoroughly exercise the Heron Method code above. Consider all possible kinds of square roots.
The following are some guidelines for choosing test cases:
• Have several test cases where the code is expected to work correctly on fairly standard input. These are positive tests and correspond to test cases 1 and 3 above.
• Have several test cases where the code is expected to work correctly on boundary input (input that is close to being "wrong"). These are positive boundary tests and correspond to test cases 9, 10, and 11.
- Have as many "special case" positive test cases as necessary, where the input is correct but requires accounting for special cases. These could be either positive or negative test cases, but in this example corresponds to test cases 4, 5, 7, 8, and 10.
Selecting test cases
Determining which inputs to use to create good test cases requires careful thought. Consider the following code for a RootFinder object that finds the integer root of a number. The algorithm is a binary search using a reversible function:
function RootFinder(number, root)
{
this.number = number;
this.root = root;
}
RootFinder.prototype.approxEqual = function(x, y)
{
var EPSILON = 1E-12;
return Math.abs(x - y) <= EPSILON;
}
RootFinder.prototype.pow = function(number, power)
{
var result = 1;
for (var i=0; i
{
result *= number;
}
return result;
}
RootFinder.prototype.getRoot = function()
{
// binary search for resultvar left = 0;
var right = this.number;
var mid;
do
{
mid = (left + right)/2.0;
if (this.pow(mid, this.root) < this.number)
left = mid;
else
right = mid;
} while (!this.approxEqual(left, right));
return mid;
}
|
(The source code is available for both RootFinder.js and RootFinder.html)
Consider test cases for this code; the only possible inputs are the number and the root desired. What inputs are valid? What inputs are invalid? What valid inputs will produce a good result in this version? What valid inputs will produce bad results? Clearly, some knowledge of the problem domain is required. The table below classifies some inputs:
|
Case
|
number
|
root
|
Valid?
|
Expected
|
Notes
|
|
1
|
25.0
|
2
|
Yes
|
5.00
|
Should work
|
|
2
|
-25.0
|
2
|
No
|
none
|
No even roots of negatives
|
|
3
|
27.0
|
3
|
Yes
|
3.00
|
Should work
|
|
4
|
-27.0
|
3
|
Yes
|
-3.00
|
Should work
|
|
5
|
0.25
|
2
|
Yes
|
0.500
|
Should work
|
|
6
|
-0.25
|
2
|
No
|
none
|
No even roots of negatives
|
|
7
|
0.125
|
3
|
Yes
|
0.500
|
Should work
|
|
8
|
-0.125
|
3
|
Yes
|
-0.500
|
Should work
|
|
9
|
1.00
|
2
|
Yes
|
1.00
|
Should work
|
|
10
|
-1.00
|
3
|
Yes
|
-1.00
|
Should work
|
|
11
|
0.0
|
2
|
Yes
|
0.00
|
Should work
|
Of these test cases, the presented code only passes cases test cases 1, 3, 9, and 11! The remaining test cases ended up in an infinite loop. The code presented above was written to work on all the "normal" cases; however, the assumptions were wrong for ranges of numbers in which the other test cases fell. For instance, the code assumes that all roots of a number will be found between 0 and the number itself. However, this assumption is false in test cases 5, 7, and 8. Cases 2 and 6 expose the lack of precondition checking. Finally, cases 4, 8, and 10 have left and right reversed.
Evaluating Test Cases
How does a programmer know when the output of a method is correct? Evaluating the correctness of test cases is another difficult issue. In the case of the RootFinder above, the algorithm's results can be predicted with known input, which is the way a majority of test cases are structured. For instance, if the expected answer is 10.0, then inputs of (1000.0, 3) or (100.0, 2) should yield 10.0 as the answer. Another powerful method is to use an oracle. An oracle is another method that is known to produce the correct result, and in the RootFinder example, that method is Math.pow(). The same inputs to Math.pow() can be provided to the constructor of RootFinder, and the results can be compared. One may ask why someone would wish to write a new method that does the same thing as an existing oracle. The answer is that the new method may be designed to work faster than the oracle or that an entire system is being re-written, yet the outputs of the systems should match.
• Have several test cases where the code is expected to check preconditions for bad input. These are negative test cases and correspond to test cases 2 and 6.