|
Testing Monte Carlo Algorithmic Systems
By: Frank Erdman
A Monte Carlo system uses non-deterministic algorithms to approximate a solution, and generally the more iterations of
the algorithms that are run, the better the approximate solution will be. A classic simple example of this type of program is one
estimating PI. If one pictures a unit circle inside a square, with radius of 1, then the area of the circle is PI*r^2 and the area of the
square is (2r)^2, or 4. The area of the circle divided by the area of the square then comes to (PI*r^2) / (2r)^2, or PI / 4. If this ratio is
computed, one can multiply it by 4 to get PI. A “Monte Carlo” approach to this would be to randomly select points on the square. If
these points lie within the unit circle, it counts as a “hit”, so the equation would be:
Pi ~ 4 * (Number of Hits) / (Number of Iterations).
As an example, say we ran the program with 10 iterations, and got 8 “hits”, i.e. 8 of the points lay within the unit circle (i.e. point p
satisfies condition: p = x^2 + y^2 <= 1). Then the equation would be:
Pi = (4 * 8) / 10 = 32 /10 = 3.2
The more iterations are input to the program, the closer one can get to a value for PI (defined as being 3.1415…).
Example source code for an implementation of such a program in c can be found at:
http://www.dartmouth.edu/~rc/classes/soft_dev/C_simple_ex.html
Now there are many types of solutions in enterprise software which use this basic strategy, the so-called “Monte Carlo”
strategy, because, for example in the situation of computing PI, random numbers are being used to generate selected points within
the square containing the unit circle, and Monte Carlo is the name of a famous casino, casinos being examples of the use of random
numbers. A “Monte Carlo” type of solution will have two essential characteristics:
1) Each input / output pair is predicated on random or non-determinist processes
2) Increasing the number of input/output pair cycles for the same inputs during program execution (should) lead to better
(more accurate) output.
How would one go about testing this sort of application? One would have to fit two factors into account: the non-determinism
associated with the outputs, and the expected behavior that, despite this non-determinism, better or more accurate outputs should be
obtained by increasing the number of iterations in execution. Here, for example, we could have 3 test scenarios, one with 10
iterations (Test Case 1), one with 100 iterations (Test Case 2), and one with 1000 iterations (Test Case 3). We could run these 3
simple scenarios each, say, 100 times. Now, we could put the outputs for the 100 runs of Test Case 1 into a spreadsheet, the outputs
for the 100 runs of Test Case 2 into its own spreadsheet, and the outputs for Test Case 3 into a third spreadsheet. Looking at say, the
spreadsheet for the results of Test Case 1, we can expect that (probably) each run will have a different output value, and the same
with the other two test cases, due to the indeterminist nature of the algorithm under test. However, looking at the results of Test Case
1 in a spreadsheet, we can calculate the standard deviation from what we know (from talking to development or the requirements
team) is a good result. So, for example, in preparing this article, I implemented a c version of the Monte Carlo example, and found
that if I input 10 iterations then my output could vary widely from 3.14, which is known as a good approximation for PI. Say, for the
sake of argument, that the standard deviation should be less than or equal to plus or minus 0.5 from 3.14, so anywhere from 2.64 to
3.64 would be the expected results for Test Case 1 (10 iterations). However, Test Case 2 (100 iterations) should have a smaller
standard deviation, say, for the sake of argument, around 0.25, so the results could be anywhere from 2.89 to 3.39. Test Case 3 (1000
iterations) could have a still smaller standard deviation, say, 0.12, so the expected results could be anywhere from 3.02 to 3.26.
(Incidentally these numbers are generally in the ball park of what I observed testing my own c implementation of the “Monte Carlo
PI” problem.)
To test these types of applications, a test engineer needs to obtain what the expected “standard deviation” for a given number of
iterations might be, and then, test for that expected standard deviation for that given number of iterations. The test engineer needs to
further obtain what the expected reduction in the standard deviation of results should be when increasing the number of iterations by
a certain reasonable amount (such as in this case, increasing by powers of ten). Then the tester’s expected results are, for a given test
case or number of iterations, that the standard deviation from multiple runs of that test case is not greater than the one expected.
Full article...
Other Resource
... to read more articles, visit http://sqa.fyicenter.com/art/
|