Using Random Numbers for testing
and simulation
These tips were developed using Java(tm) 2 SDK, Standard Edition,
v 1.3.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
USING RANDOM NUMBERS FOR TESTING AND SIMULATION
The Java(tm) standard library provides a random number class,
java.util.Random. This tip examines some aspects of using random
numbers in Java programming. The tip starts with some fundamentals
of using random numbers, and then presents a longer example at the
end.
Random numbers, as found in programming languages, are really
"pseudo" random numbers. They're not random in the same sense as
physical phenomena such as thermal noise or background radiation.
However it's interesting to note that truly random number
generators, ones that are hardware-based, are starting to appear
on the market. Though software-generated random numbers are not
really random, it's possible to generate random numbers in such
a way that important statistical tests like chi square and serial
correlation are satisfied.
The Random class uses a random number generator of the form:
nextrand = nextrand * a + b;
where a and b are carefully chosen constants. As defined by
D. H. Lehmer and described by Donald E. Knuth in "The Art of
Computer Programming, Volume 2: Seminumerical Algorithms,"
section 3.2.1, this is a "linear congruential" random number
generator. The low-order bits of random numbers generated this
way tend not to be random, so internal calculation is done using
48 bits. But a Random method such as Random.nextInt uses only
the upper 32 bits of the current 48-bit random value.
A sequence of random values that is generated is deterministic.
This means that from a given starting point (a "seed"), the
sequence of values returned is predictable. When you set up
a random number generator, you can say:
Random rn = new Random(1234);
if you want to specify the seed (here, it's 1234), or:
Random rn = new Random();
if you want the generator to be seeded from the current time of
day (using System.currentTimeMillis). The first approach produces
a predictable sequence, and so this tip uses "Random(0)" in the
demo programs below.
The first random number program is a simple one that prints out
10 "heads" or "tails" values:
import java.util.Random;
public class RandDemo1 {
public static void main(String args[]) {
Random rn = new Random(0);
for (int i = 1; i <= 10; i++) {
System.out.println(rn.nextBoolean() ?
"heads" : "tails");
}
}
}
The nextBoolean method in RandDemo1 is implemented internally by
generating a 48-bit random value, and then checking whether the
high bit is 1 or 0.
The next example is slightly more complex:
import java.util.Random;
class RandUtils {
private static Random rn = new Random(0);
private RandUtils() {}
// get random number in range, lo <= x <= hi
public static int getRange(int lo, int hi) {
// error checking
if (lo > hi) {
throw new IllegalArgumentException("lo > hi");
}
// handle special case
if (lo == Integer.MIN_VALUE &&
hi == Integer.MAX_VALUE) {
return rn.nextInt();
}
else {
return rn.nextInt(hi - lo + 1) + lo;
}
}
// return true perc % of the time
public static boolean getPerc(int perc) {
// error checking
if (perc < 0 || perc > 100) {
throw new IllegalArgumentException("bad perc");
}
return perc >= getRange(1, 100);
}
}
public class RandDemo2 {
public static void main(String args[]) {
int accum[] = new int[10];
// generate random numbers in a range and tally them
for (int i = 1; i <= 10000; i++) {
accum[RandUtils.getRange(0, accum.length - 1)]++;
}
// display results
for (int i = 0; i < accum.length; i++) {
System.out.println(i + " " + accum[i]);
}
}
}
In this example, RandUtils is a utility class that implements
a couple of methods: getRange and getPerc. The getRange method
returns a random number in a specified range. The method is based
on Random.nextInt, which returns a random number between 0
(inclusive) and the specified argument (exclusive). What inclusive
and exclusive mean here is that if you call Random.nextInt as
follows:
Random rn = new Random();
int n = rn.nextInt(10);
n will have a value, 0 <= n < 10. In other words, 0 can be one of
the returned values, but not 10.
The other method is getPerc; it returns true the specified
percentage of the time. For example, you can say:
if (RandUtils.getPerc(75)) {
// block of code
}
and the block of code will be executed 75% of the time, on average.
You'll see a use for this method in the next example.
When you run the RandDemo2 program, you should get the following
result:
0 990
1 1011
2 952
3 1045
4 998
5 1005
6 1021
7 1009
8 1005
9 964
Note that the tally for each number in the range should be about
1000. The results in this example vary slightly from the expected
value. This is normal. If you want to check whether the variation
is statistically significant, use a chi square test. If you do,
you should find that the results observed here are well within
those expected from random fluctuations.
The final example is more complicated. Suppose that you're testing
some software, and one of the inputs to the software is calendar
dates, like this:
September 25, 1956
You'd like to generate random dates in this form, with some of the
dates being legal, and some illegal (such as "January 32, 1989").
How can you do this? One way is to use random numbers. Here's an
example:
import java.util.Random;
class RandUtils {
private static Random rn = new Random(0);
private RandUtils() {}
// get random number in range, lo <= x <= hi
public static int getRange(int lo, int hi) {
// error checking
if (lo > hi) {
throw new IllegalArgumentException("lo > hi");
}
// handle special case
if (lo == Integer.MIN_VALUE &&
hi == Integer.MAX_VALUE) {
return rn.nextInt();
}
else {
return rn.nextInt(hi - lo + 1) + lo;
}
}
// return true perc % of the time
public static boolean getPerc(int perc) {
// error checking
if (perc < 0 || perc > 100) {
throw new IllegalArgumentException("bad perc");
}
return perc >= getRange(1, 100);
}
}
class GenDate {
// names of months
private static final String months[] = {
"January", "February", "March", "April",
"May", "June", "July", "August",
"September", "October", "November", "December"
};
// days in month
private static final int days_in_month[] = {
31, 28, 31, 30,
31, 30, 31, 31,
30, 31, 30, 31
};
// return true if leap year
private static boolean isLeapYear(int year) {
if (year % 4 != 0) {
return false;
}
if (year % 400 == 0) {
return true;
}
return (year % 100 != 0);
}
// get the number of days in a given month
private static int getDaysInMonth(int month, int year) {
int m = days_in_month[month - 1];
if (month == 2 && isLeapYear(year)) {
m++;
}
return m;
}
// generate a random string
private static String getRandString() {
switch (RandUtils.getRange(1, 4)) {
// empty string
case 1: {
return "";
}
// random integer
case 2: {
return Integer.toString(
RandUtils.getRange(-100000, 100000));
}
// random characters
case 3: {
StringBuffer sb = new StringBuffer();
int n = RandUtils.getRange(1, 10);
for (int i = 1; i <= n; i++) {
char c = (char)RandUtils.getRange(32, 127);
sb.append(c);
}
return sb.toString();
}
// random number of spaces
case 4: {
StringBuffer sb = new StringBuffer();
int n = RandUtils.getRange(1, 10);
for (int i = 1; i <= n; i++) {
sb.append(' ');
}
return sb.toString();
}
}
// shouldn't get here
throw new Error();
}
// this class has only static methods, so
// can't create instances of the class
private GenDate() {}
public static String getRandDate() {
StringBuffer sb = new StringBuffer();
// generate year, month, day
int year = RandUtils.getRange(1500, 2100);
int month = RandUtils.getRange(1, 12);
int day = RandUtils.getRange(1,
getDaysInMonth(month, year));
// 50% of the time, return a valid date
if (RandUtils.getPerc(50)) {
sb.append(months[month - 1]);
sb.append(" ");
sb.append(day);
sb.append(", ");
sb.append(year);
}
else {
// generate a month or random string
if (RandUtils.getPerc(75)) {
sb.append(months[month - 1]);
}
else {
sb.append(getRandString());
}
// generate single space or random string
if (RandUtils.getPerc(75)) {
sb.append(" ");
}
else {
sb.append(getRandString());
}
// generate day of month or random number
if (RandUtils.getPerc(75)) {
sb.append(day);
}
else {
sb.append(RandUtils.getRange(-100, 100));
}
// generate , or random string
if (RandUtils.getPerc(75)) {
sb.append(", ");
}
else {
sb.append(getRandString());
}
// generate year or random string
if (RandUtils.getPerc(75)) {
sb.append(year);
}
else {
sb.append(getRandString());
}
}
return sb.toString();
}
}
public class RandDemo3 {
public static void main(String args[]) {
for (int i = 1; i <= 15; i++) {
System.out.println(GenDate.getRandDate());
}
}
}
The output of the program is:
May 21, 1778
June -83, 2006
September 51575
14, M%r
September 26, 1614
October 17, 1910
May 16, 1818
August 27, 1646
November 19, 2055
June 12, 1797
June 13, 1585
August 2, 1998
October 17,
September 14, 1545
June339628,
This technique is quite powerful and useful. Typically you start
with a description of what constitutes legal input, and then
systematically go through and generate "nearly correct" input, but
with some illegal variations thrown in, driven by random numbers.
A similar technique can be used for doing simulation.
To learn more about using random numbers, see Section 17.3 Random
in "The Java Programming Language, Third Edition," by Arnold,
Gosling, and Holmes
(http://java.sun.com/docs/books/javaprog/thirdedition/);
and Chapter 3 in Volume 2 of "The Art of Computer Programming"
by Knuth.
|
